内部排序之堆排序的实现详解

堆排序（Heap Sort）只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
（1）基本概念
a）堆：设有n个元素的序列：
{k1, k2, ..., kn}
对所有的i=1,2,...,(int)(n/2)，当满足下面关系：
                                                                  ki≤k2i，ki≤k2i+1
                                                  或            ki≥k2i，ki≥k2i+1
这样的序列称为堆。
堆的两种类型：
   根结点最小的堆----小根堆。
   根结点最大的堆----大根堆。
根结点称为堆顶，即：在一棵完全二叉树中，所有非叶结点的值均小于（或均大于）左、右孩子的值。
b）堆排序：是一种树型选择排序，特点是，在排序过程中，把R[1..n]看成是一个完全二叉树的存储结构，利用完全二叉树双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（最小）的记录。
2）堆排序步骤：
1、从k-1层的最右非叶结点开始，使关键字值大（或小）的记录逐步向二叉树的上层移动，最大（或小）关键字记录成为树的根结点，使其成为堆。
2、逐步输出根结点，令r[1]=r[i](i=n,,n-1,...,2)，在将剩余结点调整成堆。直到输出所有结点。我们称这个自堆顶到叶子的调整过程为“筛选”。
（3）要解决的两个问题：
１、如何由一个无序序列建成一个堆；
２、输出一个根结点后，如何将剩余元素调整成一个堆。
将一个无序序列建成一个堆是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第floor(n/2)个元素，由此“筛选”只需从第floor(n/2)个元素开始。
堆排序中需一个记录大小的辅助空间，每个待排的记录仅占有一个存储空间。堆排序方法当记录较少时，不值得提倡。当n很大时，效率很高。堆排序是不稳定的。
堆排序的算法和筛选的算法如第二节所示。为使排序结果是非递减有序排列，我们在排序算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1个记录进行筛选，重新将它调整为一个“大顶堆”，然后将选得的一个关键字为最大的记录（也就是第一个元素）与当前最后一个记录交换（全局看是第n-1个），如此往复，直到排序结束。由到，筛选应按关键字较大的孩子结点向下进行。
堆排序的算法描述如下： 

 

用C语言代码实现如下：
</div> </div>