通过将无序表转化为堆,可以直接找到表中最大值或者最小值,然后将其提取出来,令剩余的记录再重建一个堆,
取出次大值或者次小值,如此反复执行就可以得到一个有序序列,此过程为堆排序。
思路:
1.创建一个堆 H[0……n-1];
2.把堆首(最大值)和堆尾互换;
3.把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
4.重复步骤 2,直到堆的尺寸为 1。
代码实现:
#include <iostream> #include <random> using namespace std; template <typename T> //整數或浮點數皆可使用 void max_heapify(T* arr, int start, int end) { // 建立父節點指標和子節點指標 int dad = start; int son = dad * 2 + 1; while (son <= end) { // 若子節點指標在範圍內才做比較 if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的 son++; if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢,直接跳出函數 return; else { // 否則交換父子內容再繼續子節點和孫節點比較 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } } } template <typename T> //整數或浮點數皆可使用 void heap_sort(T* arr, int len) { // 初始化,i從最後一個父節點開始調整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); // 先將第一個元素和已经排好的元素前一位做交換,再從新調整(刚调整的元素之前的元素),直到排序完畢 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); } } int main() { int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr,len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; double arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; len = (int) sizeof(arrf) / sizeof(*arrf); heap_sort(arrf,len); for (int i = 0; i < len; i++) cout << arrf[i] << ' ' << endl; return 0; }