赶紧让你的大脑来一套广播体操
前言
慢慢的，我们脱离了”小学生“算法，开始接触一些需要绕圈子的思路，赶紧沉浸入堆排序的头脑风暴当中吧。
简介
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
核心思想
- 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
- 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
- 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
- 直到无序区只有一个元素为止。
示例
建立最大堆
-
这里有一个数组
{100,5,3,11,33,6,8,7}，首先我们将数组我们将数组从上至下按顺序排列，转换成二叉树：一个无序堆。
堆排序-原始数组.png -
每一个三角关系都是一个堆，上面是父节点，下面两个分叉是子节点，两个子节点俗称左孩子、右孩子；如果一个孩子都没有的，不形成堆，只能做别人的孩子(啧啧啧)
堆排序-无序堆.png -
转换成无序对之后，我们要努力让这个无序堆变成最大堆或是最小堆，本文是建最大堆—即每个堆里，都实现父节点的值都大于任何一个子节点的值。要实现最大堆并不简单。
堆排序-4个堆.png 从最后一个堆开始，即左下角那个没有右孩子的那个堆开始；首先对比左右孩子，由于这货没有右孩子(真是惨)，所以只能用左孩子了，左孩子的值比父节点的值小所以不需要交换。如果发生交换，要检测子节点是否为其他堆的父节点，如果是，递归进行同样的操作。
-
第二次对比红色三角形内的堆，取较大的子节点，右孩子8胜出，和父节点比较，右孩子8大于父节点3，升级做爸爸，与3交换位置，3的位置没有子节点，这个堆建成最大堆。
堆排序-第二次排序.png -
对黄色三角形内堆进行排序，过程和上面一样，最终是右孩子33占领爸爸宝座，被交换的右孩子下面也没有子节点，所以直接结束对比。
堆排序-第三次排序.png 最顶部绿色的堆，堆顶100比左右孩子都大，所以不用交换，至此最大堆建成。
扩大有序区
-
下面进入第二阶段，扩大有序区，首先将堆顶100交换至最底部7的位置，7升至堆顶(终于做爸爸了)，100所在的底部位置即为有序区，有序区不参与之后的任何对比。
堆排序-有序区1.png -
在7升至顶部之后，对顶部重新做最大堆调整，左孩子33代替7的位置。
堆排序-第四次排序.png -
在7被交换下来后，下面还有子节点，所以需要继续与子节点对比，左孩子11比7大，所以11与7交换位置，交换位置后7下面为有序区，不参与对比，所以本轮结束，无序区再次形成一个最大堆。
堆排序-第五次排序.png -
将最大堆堆顶33交换至堆末尾，扩大有序区；
堆排序-第六次排序.png -
不断建立最大堆，并且扩大有序区，最终全部有序。
堆排序-全部有序.png
C语言代码
#pragma mark - 堆排序
void printfHeap (int arr[], int len) {
int line = 0;
for (int i = 0; i<len; i++) {
printf("%d\t",arr[i]);
if (i==line) {
printf("\n");
line = line==0?2:line+line*2;
}
}
printf("\n");
}
void adjustHeap (int arr[], int len, int parentIndex) {
int targetChildIndex = -1;
// 左右孩子的索引
int leftChildIndex = parentIndex*2+1;
int rightChildIndex = parentIndex*2+2;
// printf("未完成调整堆 %d\n",parentIndex);
// printfHeap(arr,len);
// 找出最大的孩子 先左后右
if (leftChildIndex > len-1) {
// 没有左右孩子 退出循环
return;
}else if (rightChildIndex > len-1) {
// 只有左孩子 直接用左孩子
targetChildIndex = leftChildIndex;
}else{
// 左右孩子都有 取出大的那个孩子
targetChildIndex = arr[leftChildIndex]>arr[rightChildIndex]?leftChildIndex:rightChildIndex;
}
// 如果孩子大于父节点 则互相交换
if (arr[targetChildIndex] > arr[parentIndex]) {
int temp = arr[targetChildIndex];
arr[targetChildIndex] = arr[parentIndex];
arr[parentIndex] = temp;
// printf("完成调整堆\n");
// printfHeap(arr,len);
adjustHeap(arr, len, targetChildIndex);
}
}
void heapSort (int arr[], int len) {
if (len < 2) {
return;
}
printf("原始数据\n");
printfArr(arr, len);
// 初始化最大堆
for (int i = (len-1)/2; i >= 0; i--) {
adjustHeap(arr, len, i);
}
printf("初始化完成\n");
printfHeap(arr,len);
for (int i = len - 1; i > 0; --i) {
if (arr[0] > arr[i]) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
}
printf("交换后\n");
printfHeap(arr, len);
adjustHeap(arr, i - 1, 0);
printf("调整后\n");
printfHeap(arr, len);
}
printf("最终堆\n");
printfHeap(arr,len);
printfArr(arr, len);
}
时间复杂度
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的，平均时间复杂度为：O(N*logN)。
总结
是不是看着就觉得复杂呢，个人觉得有时候直接看代码加画图能更快地了解算法的思路。
