前言
在数据结构中我们学了堆的性质及其实现，而这里我们将讲解用堆来实现排序
背景
对给定数组进行堆排序，排成降序
排序策略
排序原则
如果是排升序那么则先将给定数组建立大堆
如果是排降序那么则先将给定数组建立小堆
注：这里排成降序，我们数组建立成一个数组小堆，对于大堆稍作修改就行了
如何建小堆数组
- 根位置和左右子位置下标关系：
leftchild=root*2+1;
rightchild=root*2+2;
(leftchild(rightchild)-1)/2=root;
我们依据下标关系，可以找到对应的根位置或者子位置并操作数据建立成堆
建堆策略1：向上调整
- 对每个数据进行向上调整直到符合小堆
- 当前位置数据和根位置数据比较，如果不符合小堆则交换，直到向上调整到符合小堆
- 这里我们可以从第二个数据开始调整，也可以从最后一个数据开始调整
图示过程：从尾部数据往前开始向上调整
建堆策略2：向下调整
- 对每个位置数据的根位置数据进行向下调整
- 根位置和数据较小的子位置比较，不符合大堆则交换，直到符合
- 然而对数据使用向下调整的前提是，根的左右子堆都符合大堆
- 所以我们从最后一个数据的根位置开始进行调整，直到堆顶数据调整完毕
图示过程：
建成小堆之后
我们都知道小堆堆顶的数据永远是当前堆中数据最小的
我们让堆顶的数据与堆尾数据进行交换（最小的数就排到了最后）
交换后将除现堆尾的数据看成一个堆
对交换后的堆顶数据进行向下调整（调整后又成小堆）
调整后的堆顶数据是当前堆中（包括排除在外的堆尾的最小数）次小的数
让该堆顶数据与堆倒数第二个数据交换
以此循环直到交换到堆的正数第二个数据，这个数组降序也就排序好了
过程示图：
参考代码：
//数据调整 void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child<size) { //找到数据小的儿子 if (child + 1 < size && a[child + 1] < a[child]) { child++; } //将父节点与小子节点交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]);//交换数据 parent = child;//调整下标位置 child = parent * 2 + 1; } else { break;//结束调整 } } } // 对数组进行堆排序 void HeapSort(int* a, int n) { //排降序，建立小堆（小堆堆顶数据一定是最小的） for (int i = (n - 1 - 1) / 2; i >= 0; i--)//建堆：从最后一个数据的父节点进行向下调整一直到最开始数据 { AdjustDown(a, n,i); } //将堆顶数据放与末尾数据交换，再将除最小数据外的数组看成堆 //对当前顶数据调整，调整后当前堆的最小数据处在堆顶位置 //以此循环，每次最小的数据都放在当前堆的最后面，最终也就成了降序 for (int end = n - 1; end >= 0; end--) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); } }
测试
- 测试代码：
int main() { int a[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); HeapSort(a, sizeof(a) / sizeof(a[0])); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }
测试结果：
