相较于归并排序，堆排序的时间复杂度也为O(n*log n)，但空间复杂度远小于归并排序。堆排序用到了实用的数据结构——堆（heap），关于堆的详细介绍参看这里。堆排序基本思想：
/*adjust to keep the characters of the heap*/
void adjust(int a[],int root,int n)
{
int rootkey=a[root];
int child=2*root; //left child
while(child<=n)
{
if(child<n&&a[child]<a[child+1])
child++; //if right-child>left-child
if(rootkey>a[child])
break;
else
{
a[child/2]=a[child]; //move to parent
child*=2;
}
}
a[child/2]=rootkey;
}
void heap_sort(int a[],int n)
{
int i;
for(i=n/2;i>0;i--)
adjust(a,i,n); //establish the heap
for(i=n-1;i>0;i--)
{
swap(&a[1],&a[i+1]);
adjust(a,1,i);
}
}原文：http://blog.csdn.net/u013240812/article/details/23203537