堆排序

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 void max_heapify(int arr[], int start, int end) {
 6     // 建立父節點指標和子節點指標
 7     int dad = start;
 8     int son = dad * 2 + 1;
 9     while (son <= end) { // 若子節點指標在範圍內才做比較
10         if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
11             son++;
12         if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
13             return;
14         else { // 否則交換父子內容再繼續子節點和孫節點比較
15             swap(arr[dad], arr[son]);
16             dad = son;
17             son = dad * 2 + 1;
18         }
19     }
20 }
21 
22 void heap_sort(int arr[], int len) {
23     // 初始化，i從最後一個父節點開始調整
24     for (int i = len / 2 - 1; i >= 0; i--)
25         max_heapify(arr, i, len - 1);
26     // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
27     for (int i = len - 1; i > 0; i--) {
28         swap(arr[0], arr[i]);
29         max_heapify(arr, 0, i - 1);
30     }
31 }
32 
33 int main() {
34     int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
35     int len = (int) sizeof(arr) / sizeof(*arr);
36     heap_sort(arr, len);
37     for (int i = 0; i < len; i++)
38         cout << arr[i] << ' ';
39     cout << endl;
40     return 0;
41 }