堆排序是对简单选择排序的升级版，简单选择排序链接。堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
堆排序算法堆排序（Heap Sort）就是利用堆进行排序的方法 。基本思想：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，就能得到一个有序序列 。
堆排序用到的一个树的性质就是：
假设父节点下标为k(k>0)，那么其左孩子下标为2*k，右孩子下标为2*k+1。
实现堆排序需要解决2个问题：
如何由一个无序序列构建成一个堆？如何在输出堆顶元素后，调整剩余元素成一个新的堆？ /* 顺序表L堆排序 */void HeapSort(SqList *L){int i;for(i=L->length/2;i>0;i--)//把L中的r构建成一个大顶堆HeapAdjust(L, i, L->length);for(i=L->length;i>1;i--){swap(L, 1, i);//将堆顶记录和当前未经排序子序列的最后一个记录交换HeapAdjust(L, 1, i-1);//将L->r[1...i-1]重新调整为大顶堆}} /* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义*//* 本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆 */void HeapAdjust(SqList *L, int s, int m){int temp, j;temp = L->r[s];for(j=2*s;j<=m;j*=2){//沿关键字较大的孩子结点向下筛选if(j<m && L->r[j] < L->r[j+1])//左孩子比右孩子小++j;//j为关键字中较大的记录的下标if(temp >= L->r[j])break;//rc应插入在位置s上L->r[s] = L->r[j];s = j;}L->r[s] = temp;//插入}HeapSort函数的6－11行就是正式的排序过程，由于有了前面充分的准备，这个排序就很轻松了：
for(i=L->length;i>1;i+=){swap(L, 1, i);//将堆顶记录和当前未经排序子序列的最后一个记录交换HeapAdjust(L, 1, i-1);//将L->r[1..i-1]重新调整为大顶堆} 复杂度分析堆排序的运行时间主要在初始构建堆和重建堆时的反复筛选上，构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的交换，对于每个非终端结点来说，其实最多进行两次比较和交换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为log2(i)+1，并且需要取n-1次堆顶记录，所以，重建堆的时间复杂度为O(nlogn)。
总的来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态不敏感，所以无论是最好，最坏还是平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过冒泡、选择和插入的O(n^2)。
空间复杂度上，只有一个用来交换的暂存单元，不过由于记录的比较和交换是跳跃式的，所以堆排序不是一种稳定的排序方法。
另外，由于初始构建堆所需的比较次数较多，因此，它不适合待排序序列个数较少的情况。
例子下面的步骤图演示了最大元素如何被找到并排序，其他元素原理相同，不做演示。
这是最开始的序列形成的树形结构
从i = L->length/2开始，发现L->r[i]=7 < L->r[2*i]=9，将2*i处的值赋给i处，因为2*i处没有孩子，所以不用继续找
这里分了2步，9比8大，1比9小，所以9换到1的位置，然后继续找原来9的位置的孩子的最大值，如果比1大，那么继续交换，否则不交换。
到这里为止，最大元素已经找到，交换根元素和最后元素，然后继续重新构建堆。
#include <stdio.h>#include <stdlib.h>#define MAXNUM 10struct SqList{int r[MAXNUM+1];int length;};void HeapAdjust(SqList* L, int i, int j){int temp, k;temp = L->r[i];for(k=2*i;k<=j;k*=2){//沿关键字较大的孩子结点向下筛选，2i为左孩子，2i+1为右孩子 if(k<j && L->r[k] < L->r[k+1])//左孩子比右孩子小++k;//j为关键字中较大的记录的下标 if(temp >= L->r[k])//如果当前值比左右孩子中最大值还大，就跳出循环，将当前值存在当前左右孩子的父节点 break;//当前值应插入在位置i上，因为值比当前左右孩子还大 //如果当前值比左右孩子中最大的还小，那么把左右孩子中大的那个数存到当前结点 L->r[i] = L->r[k]; //然后将当前值索引指向了刚刚替换的位置，后面的k*=2拿到的是左孩子 i = k;}//这里插入的位置如果有孩子，值一定比孩子大，如果没有孩子，一定是叶子结点，也就是说小的数会被排到后面 L->r[i] = temp;//插入}void swap(SqList* L, int i, int j){int temp;temp = L->r[i];L->r[i] = L->r[j];L->r[j] = temp;}void HeapSort(SqList* L){int i;for(i=L->length/2;i>0;i--)//这里从1半开始调，最后得到的堆的根结点的值最大，最后结点的值最小 HeapAdjust(L, i, L->length);for(i=L->length;i>1;i--){//先进行一次交换，然后再调整大顶堆，使次大数放第二个位置...... swap(L, 1, i);//交换根位置最大值和末尾未交换过的位置 HeapAdjust(L, 1, i-1);//交换完之后重新找到最大值，此时最后面已经排好的值不要加进来 }} int main(){SqList* L = (SqList*)malloc(sizeof(SqList));L->length = MAXNUM;int a[11] = {12,6,1,3,0,7,4,5,2,8,9};//第一个为哨兵 int i;for(i=0;i<MAXNUM+1;i++)L->r[i] = a[i];//堆排序 HeapSort(L);//打印 for(i=0;i<MAXNUM+1;i++)printf("%d ", L->r[i]);printf("n");return 0;} 结果第一位为哨兵，不需要管。