#include<stdio.h>//交换函数void swap(int k[], int i, int j){int temp;temp = k[i];k[i] = k[j];k[j] = temp;}//对顺序表k进行堆排序void HeapAdjust(int k[],int s,int n){int i,temp;temp = k[s];//之所以从2s开始是因为根据二叉树的性质知2s就是它的左子结点，for(i=2*s;i<=n;i*=2){//如果右子结点比左的大，那么i+1,目的就是把最大的交给他们的父结点if(i<n&&k[i]<k[i+1]){i++;}//如果父结点最大，那么直接跳出循环，不用再继续if(temp>=k[i]){break;}//把比较大的记录赋值给k[s],即父结点k[s] = k[i];s = i;//将i的值赋给s,在循环过后可以把刚才父结点的值赋给相应的结点}k[s] = temp;}void HeapSort(int k[], int n){int i;//这个循环是将k中的数据构成一个大顶堆for(i=n/2; i>0; i–){HeapAdjust(k,i,n);}//这个循环的作用是将堆顶记录和数组的最后一个记录交换，//然后再减去1(即最后一个已经是最大的，不用参与)后再重新调整为大顶堆for(i=n; i>1; i–){swap(k,1,i);//交换第一个和最后一个记录HeapAdjust(k,1,i-1);//在没有最后一个记录的情况下重新构造大顶堆}}int main(){int i,a[10] = {-1,5,2,6,0,3,9,1,7,4};HeapSort(a,9);printf("排序后的结果是:");for(i=1; i<10; i++){printf("%d",a[i]);}printf("\n\n");return 0;}
堆排序复杂度分析：
他的运行时间主要是消耗在初始构建堆和重构建堆时的反复筛选上，在堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其他孩子进行比较和若有必要的交换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，，因此整个构建堆的时间复杂度为O(n),在正式排序的时候，第i次取堆顶记录重建堆需要用O（logi）的时间，并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以，总体来讲，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此，他无论最好最坏和平均时间复杂度都是O（nlogn）.
因为他的记录交换和比较是跳跃式进行的，因此堆排序也是一种不稳定的排序方法。
有勇气并不表示恐惧不存在，而是敢面对恐惧克服恐惧
