堆排序是什么？ 堆是一种特殊的完全二叉树。
二叉树中有两种特殊的二叉树，一种是满二叉树，另一种是完全二叉树。满二叉树的每个结点都有两个儿子，也是满二叉树的所有叶子结点都有同样的深度。
而一颗二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他是丰满的，那这样的二叉树就是完全二叉树。如果一个结点有右子结点，那它必定有左结点。
所有的父结点都比子结点都小，符合这样特点的完全二叉树称为最小堆。而所有的父结点都比子结点要大，这样的完全二叉树称为最大堆。 堆的操作有建堆、插入数，删除数等，但新增加数不符合最大最小堆的特性，就要将数调整到合适的位置。
堆调整的代码
向下调整的代码
void siftDown(int i)//传入一个向下调整的结点编号i从顶点开始向下调整 { int t,flag=0; while(i*2<=n && flag==0) { //判断结点和它的左右儿子用t记录值较小的结点编号 if(h[i]<h[i*2]) t=i*2; else t=i; if(i*2+1 <= n) { //如果右儿子的值更小，更新较小的结点编号 if(h[t] < h[i*2+1]) t=i*2+1; } if(t!=i) { Swap(t,i);//交换他们两个结点 i=t; } else flag=1; } return; }向上调整的代码
void siftup(int i) { int flag=0; if(i==1) return; while(i!=1 && flag==0) { //判断是否比父结点小 if(h[i]<h[i/2]) swap(i,i/2); else flag=1; i=i/2; } return; }完整堆排序代码： 以下为从小到大排序，利用最大堆做从小到大排序更好，最大堆建好之后，每次将顶部的最大值放在与末尾的数字交换位置，将第一个位置上的数字向下调整到符合最大堆，并且堆的长度在交换后就减一，则末尾的最大值不会再调整上来，循环到最后，就按照从小到大排列好了。同理，从大到小可以用最小堆来实现。
当然，也可以从小到大排列时用最小堆来实现，此时可以把堆顶元素拿出，也就是删除堆顶的操作，这时可以将末尾的元素拿上来，再调整使其符合堆的性质。
# include <stdio.h> int h[101]; int n; void Create(); void heapSorted(); void Swap(int x, int y) { int t; t=h[x]; h[x]=h[y]; h[y]=t; return; } void siftDown(int i)//传入一个向下调整的结点编号i从顶点开始向下调整 { int t,flag=0; while(i*2<=n && flag==0) { //判断结点和它的左右儿子用t记录值较小的结点编号 if(h[i]<h[i*2]) t=i*2; else t=i; if(i*2+1 <= n) { //如果右儿子的值更小，更新较小的结点编号 if(h[t] < h[i*2+1]) t=i*2+1; } if(t!=i) { Swap(t,i);//交换他们两个结点 i=t; } else flag=1; } return; } int main() { int i,num; printf("Please input the array's length.\n");//输入序列的长度 scanf("%d",&num); printf("Please input the numbers will be sorted.\n");//读入序列 for(i=1;i<=num;i++) scanf("%d",&h[i]); n=num; Create();//建堆 heapSorted();//堆排序 //输出排序好的序列 printf("The numbers have be sorted:\n"); for(i=1;i<=num;i++) printf("%d ",h[i]); return 0; } void Create() { int i; for(i=n/2;i>=1;i--) siftDown(i); return; } void heapSorted() { while(n>1) { Swap(1,n); n--; siftDown(1); } return; }结果：
