堆排序

View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define N 20001
 5 #define LEFT(x) ((x<<1)+1)
 6 #define RIGHT(x) ((x+1)<<1)
 7 #define PARENT(x) (((x+1)>>1)-1)
 8 int a[N];
 9 
10 void heapify(int s,int n){
11     int l,r,tmpmax,t;
12     l=LEFT(s);
13     r=RIGHT(s);
14     if(l<=n&&a[l]>a[s])
15         tmpmax=l;
16     else
17         tmpmax=s;
18     if(r<=n&&a[r]>a[tmpmax])
19         tmpmax=r;
20     if(tmpmax!=s){
21         t=a[s];a[s]=a[tmpmax];a[tmpmax]=t;
22         heapify(tmpmax,n);
23     };
24     return ;
25 }
26 
27 void build_maxheap(int n){
28     for(int i=PARENT(n);i>=0;i--){
29         heapify(i,n);
30     }
31     return ;
32 }//这一步只是把最大的放在了数组a[]的a[0]位置。并且使得每一个小的树都维持最大堆的性质。
33 
34 void heap_sort(int n){
35     int cnt,i,tmp;
36     cnt=n;
37     build_maxheap(cnt);
38     for(i=cnt;i>=1;i--){
39         tmp=a[0];a[0]=a[i];a[i]=tmp;//取出最大值
40         cnt--;
41         heapify(0,cnt);
42     }
43     return ;
44 }
45 
46 int main(){
47     int i,j,n;
48     scanf("%d",&n);
49     for(i=0;i<n;i++) scanf("%d",&a[i]);
50     heap_sort(n-1);//!!!!
51     for(i=0;i<n;i++){
52         if(i==0)printf("%d",a[i]);
53         else printf(" %d",a[i]);
54     }
55     printf("\n");
56     return 0;
57 }
保持每棵树的父节点的值比两个儿子大。详见代码。
keep moving...