(Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录Data[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩 子结点之间的内在关系，在当前无序的序列中选择关键字最大(或最小)的记录。
时间复杂度
O(n l o g 2 log_2 log2n)
空间复杂度
O(1)
算法特点：
1 ) 是不稳定排序。
2 ) 只能用于顺序结构，不能用于链式结构。
3 ) 初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2n)，相对于快速排序最坏情况下的O(n2)而言是一个优点， 当记录较多时较为高效。
完整代码：
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXSIZE 100 //顺序表最大容量，可以自行加大 typedef struct {int key;//关键字项 char *otherinfo;//其他数据项 }ElemType;//记录类型 typedef struct{ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 int length;//顺序表的长度 }SqList;//顺序表 void InitList(SqList &L)//顺序表的初始化 {L.length = 0;//使顺序表长度归0，便是顺序表的初始化 }void CreateList(SqList &L)//顺序表的创建 {printf("请输入："); while(1)//建立一个死循环，循环终止条件是按了enter键 {L.length++;//顺序表长度加一 if(L.length>MAXSIZE)//判断是否超出最大容纳量 {printf("顺序表已满！n");return ;}scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 if(getchar() == 'n')//循环终止条件 break;}}void InputList(SqList L)//顺序表的输出 {int i;//记录次数 if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 {printf("顺序表是空的！n");return ;}printf("打印为：");for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 printf("%d ",L.Data[i].key);}void HeapAdjust(SqList &L,int s,int m)//假设Data[s+1…m]已是堆，将Data[s…m]调整为以Data[s]为根的大根堆 {//筛选法调整堆 int j;L.Data[0] = L.Data[s];for(j=2*s;j<=m;j*=2)//沿key较大的孩子结点向下筛选 {if(j<m&&L.Data[j+1].key > L.Data[j].key)//j为key较大的记录的下标 j++;if(L.Data[0].key >= L.Data[j].key)//Data[0]应插入在位置s上 break;L.Data[s] = L.Data[j];s = j;}L.Data[s] = L.Data[0];//插入 }void CreatHeap(SqList &L)//建初堆，把无序序列L.Data[1…n]建成大根堆 {int i;for(i=L.length/2;i>0;i--)//反复调用HeapAdjust HeapAdjust(L,i,L.length);}void HeapSort(SqList &L)//对顺序表L进行堆排序 {int i;CreatHeap(L);//把无序序列L.Data[1…L.length]建成大根堆 for(i=L.length;i>1;i--){L.Data[0] = L.Data[1];//将堆顶记录和当前未经排序子序列L.Data[1…i]中最后一个记录互换 L.Data[1] = L.Data[i];L.Data[i] = L.Data[0];HeapAdjust(L,1,i-1);//将L.Data[1…i-1]重新调整为大根堆 }}int main(){SqList L;InitList(L);//初始化顺序表 CreateList(L);//创建顺序表 HeapSort(L);//堆排序 InputList(L);//打印排序后结果 return 0;}
（完）