【算法导论】C++实现堆排序

【算法导论】C++实现堆排序

堆排序的过程就不说明了，代码如下：

1. void Build_Max_Heap(int array_list[] ,const int array_size,const int index); 
2. bool HeapSort(int array_list[],const int array_size); 
3. int main() 
4. { 
5.     const int size = 10; 
6.     int array_list [] ={16,14,10,8,7,9,3,2,4,1}; 
7.     HeapSort(array_list,size); 
8.      
9.     return 0; 
10. } 
11. bool HeapSort(int array_list[],const int array_size) 
12. { 
13.     if(array_size < 0) 
14.     { 
15.         return false; 
16.     } 
17.     for(int i=0;i<array_size;i++) 
18.     { 
19.         for(int j = ((array_size - i)/2-1);j>=0;j--) 
20.         { 
21.             Build_Max_Heap(array_list,array_size - i,j); 
22.         } 
23.         int tmp = array_list[0]; 
24.         array_list[0] = array_list[array_size -1 - i]; 
25.         array_list[array_size -1 - i] = tmp; 
26.         std::cout<<"Sorted:"<<i+1<<"\t"; 
27.         for(int i=0;i<array_size;i++) 
28.         { 
29.             std::cout<<array_list[i]<<"\t"; 
30.         } 
31.         std::cout<<std::endl; 
32.     } 
33.     return true; 
34. } 
35. /*构建大根堆*/ 
36. void Build_Max_Heap(int array_list[] ,const int array_size,const int index) 
37. { 
38.     int left_index = 2*index + 1; 
39.     int right_index = 2*index + 2; 
40.     int largest = index; 
41.     if((right_index < array_size) ) 
42.     {/*在建立大根堆时，如果父节点比两个子节点都小，则交换最大的一个子节点*/ 
43.         if((array_list[left_index] < array_list[right_index])) 
44.         { 
45.             largest = right_index; 
46.         } 
47.         else 
48.         { 
49.             largest = left_index; 
50.         } 
51.     } 
52.     else 
53.     { 
54.         if(left_index < array_size) 
55.         { 
56.             largest = left_index; 
57.         } 
58.     } 
59.     if((array_list[index] < array_list[largest]) && (largest != index)) 
60.     { 
61.         int tmp = array_list[index]; 
62.         array_list[index] = array_list[largest]; 
63.         array_list[largest] = tmp; 
64.         /*如果交换了某个节点的值，则需要递归交换其子树的节点*/ 
65.         Build_Max_Heap(array_list,array_size,largest); 
66.     } 
67. }