这是一个最初级的树，堆排序，时间复杂度低； 样例输入
14 99 5 36 7 22 17 46 12 2 19 25 28 1 92样例输出
1 2 5 7 12 17 19 22 25 28 36 46 92 99代码
#include<iostream> #include<cstdio> using namespace std; int h[101]; ///用来储存堆的数组； int n; ///用来储存堆中元素的个数，也就是堆的大小； void swap(int x,int y) ///交换函数，用来交换堆中的两个元素的值； { int t; t=h[x]; h[x]=h[y]; h[y]=t; } void siftdown(int i) ///向下调整； { int t,flag=0; ///用来标记是否需要继续向下调整； ///当i节点有儿子（其实至少有左儿子）并且又需要继续调整的时候循环就执行； while(i*2<=n&&flag==0) { if(h[i]>h[i*2]) ///首先判断他和左儿子的关系，并用t记录值较小的节点编号； 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; ///更新i为刚才与它交换的儿子节点的编号，便于接下来继续向下调整； } else flag=1;///否则说明当前的的父亲节点已经比两个子结点都要小了， ////不需要继续调整了； } } void creat() ///建立堆的函数 { int i; for(i=n/2;i>=1;i--) { siftdown(i); ///从最后一个非叶节点到第一个节点依次进行调整； } } int deletemax() ///删除最大元素； { int t; t=h[1]; ///用一个临时变量记录堆顶点的值； h[1]=h[n]; ///将堆的最后一个点赋值到堆顶； n--; ///堆的元素减少一； siftdown(1); ///向下调整； return t; ///返回之前记录的堆的顶点的最大值； } int main() { int i,num; scanf("%d",&num); ///读入要排序的数字个数； n=num; creat(); ///建堆； for(i=1;i<=num;i++) scanf("%d",&h[i]); n=num; creat(); ///建堆； for(i=1;i<=num;i++) printf("%d ",deletemax()); getchar(); getchar(); return 0; }