【算法導論】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);
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. }