排序算法之堆排序

 1 //堆排序，伪代码
 2 // HEAPSORT(A)
 3 // BUILD-MAX-HEAP(A)
 4 // for i=A.length downto 2
 5 //       exchange A[1] with A[i]    //将第一个元素和第i个元素交换
 6 // A.heap-size = A.heap-size - 1;
 7 // MAX-HEP-APIFY(A,1);
 8 
 9 void heapAdjust(int iarr[],int start,int len)
10 {
11     int i = start,temp = 0,maxChildIndex = 0;
12     for(;i < len / 2; ++i)
13     {
14         maxChildIndex = 2*i+1;
15         if(maxChildIndex + 1 < len)    //如果右节点存在
16         {
17             maxChildIndex = iarr[maxChildIndex] > iarr[maxChildIndex + 1] ? maxChildIndex: maxChildIndex + 1;
18         }
19         if(iarr[i] < iarr[maxChildIndex])
20         {
21             temp = iarr[maxChildIndex];
22             iarr[maxChildIndex] = iarr[i];
23             iarr[i] = temp;
24         }
25     }
26 }
27 void heapSort(int iarr[],int len)
28 {
29     int i,temp;
30     //开始的时候建堆，根据堆的性质，从原始数组的最后一个元素的父节点开始调整即可
31     for(i = len / 2; i > 0; --i)
32     {
33         heapAdjust(iarr,i - 1,len);
34     }
35     for(i = 0;i < len; ++i)
36     {
37         cout << iarr[i] << " ";
38     }
39     cout << endl;
40     for(i = len - 1; i > 0; --i)
41     {
42         //堆的最后一个元素与第一个元素交换
43         temp    = iarr[i];
44         iarr[i] = iarr[0];    
45         iarr[0] = temp;
46         heapAdjust(iarr,0,i);
47     }
48 }
49 int main()
50 {
51     int a[10]={4,1,3,2,16,9,10,14,8,7};
52     heapSort(a,10);
53     for(int i=0;i < 10; ++i)
54         cout << a[i] << " ";
55     return 0;
56 }