堆排序

 1 void heapify(int arr[], int n, int i)
 2 {
 3     int largest = i; // 将最大元素设置为堆顶元素
 4     int l = 2 * i + 1; // left = 2*i + 1 
 5     int r = 2 * i + 2; // right = 2*i + 2 
 6 
 7                        // 如果 left 比 root 大的话
 8     if (l < n && arr[l] > arr[largest])
 9         largest = l;
10 
11     // I如果 right 比 root 大的话
12     if (r < n && arr[r] > arr[largest])
13         largest = r;
14 
15     if (largest != i)
16     {
17         swap(arr[i], arr[largest]);
18 
19         // 递归地定义子堆，只用定义被破坏的子堆即可
20         heapify(arr, n, largest);
21     }
22 }
23 
24 void heapSort(int arr[], int n)
25 {
26     // 建立堆，从第一个非叶子节点开始
27     for (int i = n / 2 - 1; i >= 0; i--)
　　　　　　//n是最大元素下标，i是要调整树的根
28         heapify(arr, n, i);
29 
30     // 一个个从堆顶取出元素,因为只有堆顶是最大，其他地方还无序，所以每取出一个最大的放到最后，就要调整一次堆
31     for (int i = n - 1; i >= 0; i--)
32     {
33         swap(arr[0], arr[i]);
34         heapify(arr, i, 0);
35     }
36 }