一、堆排序的思想
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆（若不清楚什么是堆，可以看我前面的文章，有详细阐述）来进行选择数据，通过向下调整算法，从第一个非叶子结点开始在局部先创建出大堆（或小堆），然后父亲结点不断往上走，直到整棵树都建成一个堆。 需要注意的是排升序要建大堆，排降序建小堆。（ 然后不断交换根节点和最后一个节点的值，交换完后节点的数目减1（因为最后一个节点已经是它应该在的位置了，不用再参与建堆），再从根节点向下建堆（除最后一个节点其它节点又会建成一个堆） ） 。 然后重复红色括号中的过程，堆排序就完成了。
二、堆排序的图解
下图以建大堆为例排一个升序序列
三、堆排序的实现
3.1向下调整算法的实现
实现堆排序最重要的就是实现向下调整算法。以下是向下调整算法的代码以及解释
//这里以建大堆为例 void AdjustDown(int* a, int n, int root) { int child = root * 2 + 1;//找到根节点的左孩子 while (child < n)//判断左孩子是否出界 { if (child + 1 < n && a[child + 1] > a[child]) //child + 1 < n判断右孩子是否出界， //a[child + 1] > a[child]判断左右孩子的大小，取左右孩子中大的那一个 child++; if (a[child] > a[root])//入过孩子的值比父亲的值大，就交换孩子和父亲的位置 Swap(&a[child], &a[root]); else//如果孩子的值不比父亲的值大，就证明大堆已经建好了（因为此时父亲的左右子树都是大堆）， //直接break跳出循环。 break; //没有break来到这里就顺着子树继续往下走 root = child; child = root * 2 + 1; } }
3.2堆排序的实现
以下是堆排序的代码实现以及解释
void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { //(n - 1 - 1) / 2找到第一个非叶子节点，从第一个非叶子结点开始向下建堆 AdjustDown(a, n, i); } //堆建好了 int end = n - 1; while (end > 0) { //假设是建大堆，将下标为0的元素和下标为end的元素交换， //最大的数就排到最后了，也就相当于最后的那个数已经排好了，不用再参与下面的向下建堆 Swap(&a[0], &a[end]); AdjustDown(a, end, 0);//还没有排好的数向下建堆从0位置开始向下建堆 end--; } }
四、总结
堆排序的时间复杂度为 O(N*logN) （向下建堆时间复杂度为O(N)，排序时间复杂度为O(N*logN)）， 空间复杂度：O(1) ，稳定性：不稳定。
