堆排序的时间复杂度O(N*logN),额外空间复杂度O(1)，是一个不稳定性的排序

目录

一 准备知识

1.1  大根堆和小根堆

二 堆排序基本步骤

2.1 构造堆

2.2 固定最大值再构造堆

三 总结

四 代码

 

一 准备知识

堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆

1.1  大根堆和小根堆

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图



 我们对上面的图中每个数都进行了标记，上面的结构映射成数组就变成了下面这个样子



还有一个基本概念：查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：

大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

二 堆排序基本步骤

基本思想：

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

2.1 构造堆

将无序数组构造成一个大根堆（升序用大根堆，降序就用小根堆）

假设存在以下数组



主要思路：第一次保证0~0位置大根堆结构（废话），第二次保证0~1位置大根堆结构，第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构（每次新插入的数据都与其父结点进行比较，如果插入的数比父结点大，则与父结点交换，否则一直向上交换，直到小于等于父结点，或者来到了顶端）

插入6的时候，6大于他的父结点3，即arr(1)>arr(0)，则交换；此时，保证了0~1位置是大根堆结构，如下图：



                                     (友情提示：待交换的数为蓝色，交换后的数为绿色)

 插入8的时候，8大于其父结点6，即arr(2)>arr(0),则交换；此时，保证了0~2位置是大根堆结构，如下图



插入5的时候，5大于其父结点3，则交换，交换之后，5又发现比8小，所以不交换；此时，保证了0~3位置大根堆结构，如下图 



插入7的时候，7大于其父结点5，则交换，交换之后，7又发现比8小，所以不交换；此时整个数组已经是大根堆结构 



 

2.2 固定最大值再构造堆

此时，我们已经得到一个大根堆，下面将顶端的数与最后一位数交换，然后将剩余的数再构造成一个大根堆



                                    （友情提示：黑色的为固定好的数字，不再参与排序） 

 此时最大数8已经来到末尾，则固定不动，后面只需要对顶端的数据进行操作即可，拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于其左右孩子较大的数，则停止，如果顶端的数小于其左右孩子较大的数，则交换，然后继续与下面的孩子进行比较

下图中，5的左右孩子中，左孩子7比右孩子6大，则5与7进行比较，发现5<7，则交换；交换后，发现5已经大于他的左孩子，说明剩余的数已经构成大根堆，后面就是重复固定最大值，然后构造大根堆



如下图：顶端数7与末尾数3进行交换，固定好7，



剩余的数开始构造大根堆 ，然后顶端数与末尾数交换，固定最大值再构造大根堆，重复执行上面的操作，最终会得到有序数组



 

三 总结

到这里，大家应该对堆排序都有了自己的见解，我们对上面的流程总结下：

1、首先将无需数组构造成一个大根堆（新插入的数据与其父结点比较）

2、固定一个最大值，将剩余的数重新构造成一个大根堆，重复这样的过程

四 代码

代码中主要两个方法：

1、将待排序数组构造成一个大根堆（元素上升）

2、固定一个最大值，将剩余的数再构造成一个大根堆（元素下降）

    //堆排序
    public static void heapSort(int[] arr) {
        //构造大根堆
        heapInsert(arr);
        int size = arr.length;
        while (size > 1) {
            //固定最大值
            swap(arr, 0, size - 1);
            size--;
            //构造大根堆
            heapify(arr, 0, size);

        }

    }

    //构造大根堆（通过新插入的数上升）
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //当前插入的索引
            int currentIndex = i;
            //父结点索引
            int fatherIndex = (currentIndex - 1) / 2;
            //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
            //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
            while (arr[currentIndex] > arr[fatherIndex]) {
                //交换当前结点与父结点的值
                swap(arr, currentIndex, fatherIndex);
                //将当前索引指向父索引
                currentIndex = fatherIndex;
                //重新计算当前索引的父索引
                fatherIndex = (currentIndex - 1) / 2;
            }
        }
    }
    //将剩余的数构造成大根堆（通过顶端的数下降）
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while (left < size) {
            int largestIndex;
            //判断孩子中较大的值的索引（要确保右孩子在size范围之内）
            if (arr[left] < arr[right] && right < size) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            //比较父结点的值与孩子中较大的值，并确定最大值的索引
            if (arr[index] > arr[largestIndex]) {
                largestIndex = index;
            }
            //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
            if (index == largestIndex) {
                break;
            }
            //父结点不是最大值，与孩子中较大的值交换
            swap(arr, largestIndex, index);
            //将索引指向孩子中较大的值的索引
            index = largestIndex;
            //重新计算交换之后的孩子的索引
            left = 2 * index + 1;
            right = 2 * index + 2;
        }

    }
    //交换数组中两个元素的值
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

                                                              友情提示：手机观看，可以左右滑动 

 

 

 

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

  算法： 把未排序的数据一个一个放入堆里，然后再一个一个取出来。
  步骤： 1. 将待排序的数组调整为最大堆；

      2. 把堆首（最大值）和堆尾互换；

      3. 将堆的尺寸缩小1，再重新调整为最大堆，目的是把新的数组顶端数据调整到相应位置；

      4. 回到步骤 2，直到堆的尺寸为 1。
  例如： 使用堆排序算法将数组 { 4,2,8,0,5,7,1,3,6,9 } 进行升序排序。


  实现代码如下所示。
#include <iostream>
using namespace std;
#include <algorithm>

// 最大堆调整
void MaxHeapify(int arr[], int start, int end) 
{
	// 建立父结点指标和子结点指标
	int Parent = start;
	int Child = Parent * 2 + 1;
	while (Child <= end)  // 若子结点指标在范围内才做比较
	{
		if (Child + 1 <= end && arr[Child] < arr[Child + 1]) // 先比较两个子结点指标大小，选择最大的
			Child++;
		if (arr[Parent] > arr[Child]) // 如果父结点大于子结点代表调整完毕，直接跳出函数
			return;
		else { // 否则交换父子内容再继续子结点和孙结点比较
			swap(arr[Parent], arr[Child]);
			Parent = Child;
			Child = Parent * 2 + 1;
		}
	}
}

void HeapSort(int arr[], int len) 
{
	// 初始化，i从最后一个父结点开始调整
	for (int i = len / 2 - 1; i >= 0; i--)
		MaxHeapify(arr, i, len - 1);
	// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
	for (int i = len - 1; i > 0; i--) 
	{
		swap(arr[0], arr[i]);
		MaxHeapify(arr, 0, i - 1);
	}
}

int main() 
{
	int arr[] = { 4,2,8,0,5,7,1,3,6,9 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	HeapSort(arr, len);
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
	system("pause");
	return 0;
}

排序前：

4 2 8 0 5 7 1 3 6 9

排序后：

0 1 2 3 4 5 6 7 8 9
  堆排序算法的详细过程如下图所示。


  时间复杂度： 堆排序的时间复杂度为$Ο(nlogn)$。
  空间复杂度： $O(1)$。
  稳定性： 由于在排序的过程中，用最大堆的结构排序，排序前后两个相同元素的位置会发生变化，所以堆排序是不稳定的排序，如下图所示。

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

/*
 * 堆排序是一种选择排序，时间复杂度为O(nlog<sub>2</sub>n)。
 * 
 * 堆排序的特点是：
 * 在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，
 * 利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。
 *
 * 基本思想
 * 1.将待排序数组调整为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
 * 2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置列入有序区，然后将新的无序区调整为大根堆。
 * 3.重复操作，直到无序区消失为止。
 * 初始时，整个数组为无序区。每一次交换，都是将大根堆的堆顶元素换入有序区，以保证有序区是有序的。
 */

namespace HeapSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// 程序入口点。
        /// </summary>
        public static void Main()
        {
            int[] a = {1, 14, 6, 2, 8, 66, 9, 3, 0, 10, 5, 34, 76, 809, 4, 7};

            Console.WriteLine("Before Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n");

            Console.WriteLine("In Heap Sort:");
            HeapSort(a);
            Console.WriteLine("");

            Console.WriteLine("After Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }
        }

        /// <summary>
        /// 堆排序方法。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void HeapSort(int[] a)
        {
            // 建立大根堆。
            BuildMaxHeap(a);
            Console.WriteLine("Build max heap:");
            foreach (int i in a)
            {
                // 打印大根堆。
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\nMax heap in each heap sort iteration:");
            for (int i = a.Length - 1; i > 0; i--)
            {
                // 将堆顶元素和无序区的最后一个元素交换。
                Swap(ref a[0], ref a[i]);

                // 将新的无序区调整为大根堆。
                MaxHeaping(a, 0, i);

                // 打印每一次堆排序迭代后的大根堆。
                for (int j = 0; j < i; j++)
                {
                    Console.Write(a[j] + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }

        /// <summary>
        /// 由底向上建堆。
        /// 由完全二叉树的性质可知，叶子结点是从index=a.Length/2开始，
        /// 所以从index=(a.Length/2)-1结点开始由底向上进行大根堆的调整。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void BuildMaxHeap(int[] a)
        {
            for (int i = (a.Length / 2) - 1; i >= 0; i--)
            {
                MaxHeaping(a, i, a.Length);
            }
        }

        /// <summary>
        /// 将指定的结点调整为堆。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        /// <param name="i">
        /// 需要调整的结点。
        /// </param>
        /// <param name="heapSize">
        /// 堆的大小，也指数组中无序区的长度。
        /// </param>
        private static void MaxHeaping(int[] a, int i, int heapSize)
        {
            // 左子结点。
            int left = (2 * i) + 1;

            // 右子结点。
            int right = 2 * (i + 1);

            // 临时变量，存放大的结点值。
            int large = i;

            // 比较左子结点。
            if (left < heapSize && a[left] > a[large])
            {
                large = left;
            }

            // 比较右子结点。
            if (right < heapSize && a[right] > a[large])
            {
                large = right;
            }

            // 如有子结点大于自身就交换，使大的元素上移；并且把该大的元素调整为堆以保证堆的性质。
            if (i != large)
            {
                Swap(ref a[i], ref a[large]);
                MaxHeaping(a, large, heapSize);
            }
        }

        /// <summary>
        /// 交换两个整数的值。
        /// </summary>
        /// <param name="a">整数a。</param>
        /// <param name="b">整数b。</param>
        private static void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
}

// Output:
/*
Before Heap Sort:
1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7

In Heap Sort:
Build max heap:
809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2
Max heap in each heap sort iteration:
76 14 66 7 10 34 9 3 0 8 5 2 1 6 4
66 14 34 7 10 4 9 3 0 8 5 2 1 6
34 14 9 7 10 4 6 3 0 8 5 2 1
14 10 9 7 8 4 6 3 0 1 5 2
10 8 9 7 5 4 6 3 0 1 2
9 8 6 7 5 4 2 3 0 1
8 7 6 3 5 4 2 1 0
7 5 6 3 0 4 2 1
6 5 4 3 0 1 2
5 3 4 2 0 1
4 3 1 2 0
3 2 1 0
2 0 1
1 0
0

After Heap Sort:
0 1 2 3 4 5 6 7 8 9 10 14 34 66 76 809
*/

 

十大经典排序算法

十大经典排序算法-冒泡排序算法详解
十大经典排序算法-选择排序算法详解
十大经典排序算法-插入排序算法详解
十大经典排序算法-希尔排序算法详解
十大经典排序算法-快速排序算法详解
十大经典排序算法-归并排序算法详解
十大经典排序算法-堆排序算法详解
十大经典排序算法-计数排序算法详解
十大经典排序算法-桶排序算法详解
十大经典排序算法-基数排序算法详解

一、什么是堆排序
1.概念
堆排序（Heapsort）是利用二叉堆的概念来排序的选择排序算法，分为两种：

升序排序：利用最大堆进行排序
降序排序：利用最小堆进行排序

2.算法原理
给定一个最大堆如下图所示，以该最大堆进行演示堆排序



首先，删除堆顶元素10（即最大的元素），并将最后的元素3补充到堆顶，删除的元素10，放置于原来最后的元素3的位置



根据二叉堆的自我调整，第二大的元素9会成为二叉堆新的堆顶



删除元素9，元素8成为最大堆堆顶



删除元素8，元素7成为最大堆堆顶



依次删除最大元素，直至所有元素全部删除



此时，被删除的元素组成了一个从小到大排序的序列


3.算法实现
// 下沉调整
// 最大堆
function downAdjust(arr, parentIndex, length) {
    // 缓存父节点的值，用于最后进行赋值，而不需要每一步进行交换
    let temp = arr[parentIndex];
    // 孩子节点下标，暂时定为左孩子节点下标
    let childIndex = 2 * parentIndex + 1;

    while (childIndex < length) {
        // 当存在右孩子节点，且右孩子节点的值小于左孩子节点的值，childIndex记录为右孩子节点的下标
        // childIndex实际记录的是最小的孩子节点的下标
        if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
            childIndex++;
        }

        // 如果父节点的值比孩子节点的值都小，则调整结束
        if (temp >= arr[childIndex]) {
            break;
        }

        // 将最小的孩子节点的值赋值给父节点
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
    }
    arr[parentIndex] = temp;
}

// 堆排序
function sort(arr) {
    // 把无序数组构建成二叉堆
    for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {
        downAdjust(arr, i, arr.length);
    }
    console.log(arr);

    // 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶
    for (let i = arr.length - 1; i > 0; i--) {
        // 最后一个元素与第一个元素交换
        [arr[0], arr[i]] = [arr[i], arr[0]];
        downAdjust(arr, 0, i);
    }
}

let arr = [10, 9, 8, 5, 6, 7, 1, 4, 2, 3];
sort(arr);
console.log(arr);

三、堆排序算法特点
1.时间复杂度
下沉调整的时间复杂度等同于堆的高度O(logn)，构建二叉堆执行下沉调整次数是n/2，循环删除进行下沉调整次数是n-1，时间复杂度约为O(nlogn)
2.空间复杂度
堆排序算法排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)
3.稳定性
堆排序算法在排序过程中，相同元素的前后顺序有可能发生改变，所以堆排序是一种不稳定排序算法

另外推荐一个开发者小工具网站，个人觉得里面的Json格式化功能很强大，报错很详细
https://tinyutil.com/
还可以输入表达式进行内容选取，对于复杂json非常多层级的内容展现非常用用处