堆排序

 1 /*堆排序*/
 2 //根节点元素自顶向下移动到合适的位置以构成最大堆
 3 void downToMaxHeap(vector<int> &arr, int bgn, int end)
 4 {
 5     int child;
 6     int parent = bgn;
 7 
 8     /*假根节点向下移动至合适的位置 --整个堆排序的核心代码块*/
 9     while ((child = parent * 2 + 1) < end)
10     {
11         if ((child < end - 1) && (arr[child] < arr[child + 1]))
12             ++child;    //右孩子节点
13         if (arr[child] > arr[parent])
14             mySwap(&arr[child], &arr[parent]);
15         else
16             break;
17         parent = child;
18     }
19 }
20 //将数组构造为最大堆
21 void buildMaxHeap(vector<int> &arr, int bgn, int end)
22 {
23     if (bgn >= end - 1)
24         return;
25 
26     int parent = end / 2 - 1;
27     while (parent >= 0)
28     {
29         downToMaxHeap(arr, parent, end);
30         --parent;
31     }
32 }
33 //堆排序
34 void heapSort(vector<int> &arr, int bgn, int end)
35 {
36     //构造最大堆
37     buildMaxHeap(arr, bgn, end);
38 
39     while (end > 1)
40     {
41         mySwap(&arr[0], &arr[--end]);
42         downToMaxHeap(arr, 0, end);
43     }
44 }

View Code

Code-堆排序

https://blog.csdn.net/u010452388/article/details/81283998

https://www.cnblogs.com/Glory-D/p/7884525.html

https://www.cnblogs.com/linjj/p/5260763.html

https://blog.csdn.net/li1914309758/article/details/81036854