C语言对堆排序一个算法思路和实现代码
算法思想简单描述：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
堆排序是不稳定的。算法时间复杂度O(nlog2n)。
voidsift(int*x,intn,ints){
intt,k,j;
t=*(x+s);
k=s;
j=2*k+1;
while(j{
if(j<*(x+j+1))&&*(x+j)/>{//判断是否满足堆的条件：满足就继续下一轮比较，否则调整。
j++;
}
if(t<*(x+j)){
*(x+k)=*(x+j);
k=j;
j=2*k+1;
}else{
break;
}
}
*(x+k)=t;
}
voidheap_sort(int*x,intn){
inti,k,t;
int*p;
for(i=n/2-1;i>=0;i--){
sift(x,n,i);
}
for(k=n-1;k>=1;k--){
t=*(x+0);
*(x+0)=*(x+k);
*(x+k)=t;
sift(x,k,0);
}
}
voidmain(){
#defineMAX4
int*p,i,a[MAX];
p=a;
printf("Input%dnumberforsorting:\n",MAX);
for(i=0;i<MAX;i++){
scanf("%d",p++);
}
printf("\n");
p=a;
select_sort(p,MAX);
for(p=a,i=0;i++){
printf("%d",*p++);
}
printf("\n");
system("pause");
}