分治算法-堆排序

 1 #include<iostream>
 2 using namespace std;
 3 
 4 
 5 void print(int a[],int n)
 6 {
 7     for(int i=0;i<n;i++)
 8         cout<<a[i]<<" ";
 9     cout<<endl;
10 }
11 void swap(int &a,int &b)
12 {
13     int temp=a;
14     a=b;
15     b=temp;
16 }
17 void AdjustDown(int a[],int i,int n)
18 {    
19     int l=2*i+1,r=2*i+2,max=i;
20     if(i<=(n-1)/2)
21     {
22         if(l<=n && a[l]>a[max])
23             max=l;
24         if(r<=n && a[r]>a[max])
25             max=r;
26         if(i!=max)
27         {
28             swap(a[i],a[max]);
29             AdjustDown(a,max,n);
30         }
31     }
32 }
33 void HeapSort(int a[],int n)
34 {
35     for(int i=(n-1)/2;i>=0;i--)
36         AdjustDown(a,i,n);
37     for(i=n;i>0;i--)
38     {
39         swap(a[i],a[0]);
40         AdjustDown(a,0,i-1);
41     }
42 }
43 int main()
44 {
45     int a[10]={5,3,7,2,6,4,13,1,9,8};
46     print(a,10);
47     HeapSort(a,9);
48     print(a,10);
49     return 0;
50 }