堆排序

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 
 6 void print(int a[], int n){  
 7     for(int j= 0; j<n; j++){  
 8         cout<<a[j] <<"  ";  
 9     }  
10     cout<<endl;  
11 }  
12   
13   
14   
15 /** 
16  * 已知H[s…m]除了H[s] 外均满足堆的定义 
17  * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
18  * 
19  * @param H是待调整的堆数组 
20  * @param s是待调整的数组元素的位置 
21  * @param length是数组的长度 
22  * 
23  */  
24 void HeapAdjust(int H[],int s, int length)  
25 {  
26     int tmp  = H[s];  
27     int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
28     while (child < length) {  
29         if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
30             ++child ;  
31         }  
32         if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
33             H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
34             s = child;       // 重新设置s ,即待调整的下一个结点的位置  
35             child = 2*s+1;  
36         }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
37              break;  
38         }  
39         H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
40     }  
41     print(H,length);  
42 }  
43   
44   
45 /** 
46  * 初始堆进行调整 
47  * 将H[0..length-1]建成堆 
48  * 调整完之后第一个元素是序列的最小的元素 
49  */  
50 void BuildingHeap(int H[], int length)  
51 {   
52     //最后一个有孩子的节点的位置 i=  (length -1) / 2  
53     for (int i = length/2 -1 ; i >= 0; --i)  
54         HeapAdjust(H,i,length);  
55 }  
56 /** 
57  * 堆排序算法 
58  */  
59 void HeapSort(int H[],int length)  
60 {  
61     //初始堆  
62     BuildingHeap(H, length);  
63     //从最后一个元素开始对序列进行调整  
64     for (int i = length - 1; i > 0; --i)  
65     {  
66         //交换堆顶元素H[0]和堆中最后一个元素  
67         int temp = H[i]; H[i] = H[0]; H[0] = temp;  
68         //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
69         HeapAdjust(H,0,i);  
70   }  
71 }   
72   
73 int main(){  
74     int H[10] = {3,1,5,7,2,4,9,6,10,8};  
75     cout<<"初始值：";  
76     print(H,10);  
77     HeapSort(H,10);  
78     //selectSort(a, 8);  
79     cout<<"结果：";  
80     print(H,10);  
81   
82 }