1 排序思想：
将排序表的n个记录按照关键字建成堆，堆顶元素就是选择出的最大（或最小）记录，这样就得到排序的第一个记录。再将剩下的n-1个记录建成堆，得到次大（或者次小）的记录。如此反复，直到执行n-1次后，排序结束。
大顶堆的性质：R[i]>=R[2i]且R[i]>=R[2i+1]
2 算法实现：
// 堆排序
void heap_sort(int num[], int n){
int i;
// 将num[]调整成大顶堆
// 即num[i]>=num[2i]&&num[i]>=num[2i+1]
for(i=n/2;i>=0;i--){
heap_adjust(num,i,n);
}
for(i=n-1;i>0;i--){
// 将每一轮的堆顶放在i
SWAP(num[0],num[i]);
// 再将剩下的i个记录调整成大顶堆
heap_adjust(num,0,i);
}
}
// 将num[s,q)段调整成大顶堆
// num[s]>=num[2s]且num[s]>=num[2s+1]
void heap_adjust(int num[],int s,int q){
int rc=num[s];
int i;
for(i=2*s;i<q;i*=2){
if(i<q-1&&num[i]<num[i+1])
i++;
if(rc>=num[i])
break; // rc应当放在位置s
num[s]=num[i];
s=i;
}
num[s]=rc;
}
#define SWAP(x,y) {int t; t = x; x = y; y = t;}3 性能分析：
3.1 空间复杂度：O（1）
3.2 时间复杂度：平均和最坏时间复杂度是O（nlogn）
3.3 稳定性：不稳定
