十大經(jīng)典排序算法系列博客——>傳送門

---

堆排序Heapsort是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

算法步驟：

• 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；

• 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn)，且滿足R[1,2…n-1]<=R[n]；

• 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。
  

---

代碼展示

#include<iostream> #include<vector> using namespace std;// 遞歸方式構(gòu)建大根堆(len是arr的長(zhǎng)度，index是第一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)) void adjust(vector<int> &arr, int len, int index) {int left = 2*index + 1; // index的左子節(jié)點(diǎn)int right = 2*index + 2;// index的右子節(jié)點(diǎn)int maxIdx = index;if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;if(maxIdx != index){swap(arr[maxIdx], arr[index]);adjust(arr, len, maxIdx);}}// 堆排序 void heapSort(vector<int> &arr, int size) {// 構(gòu)建大根堆（從最后一個(gè)非葉子節(jié)點(diǎn)向上）for(int i=size/2 - 1; i >= 0; i--){adjust(arr, size, i);}// 調(diào)整大根堆for(int i = size - 1; i >= 1; i--){swap(arr[0], arr[i]); // 將當(dāng)前最大的放置到數(shù)組末尾adjust(arr, i, 0); // 將未完成排序的部分繼續(xù)進(jìn)行堆排序} }int main() {vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};heapSort(arr, arr.size());for(int i=0;i<arr.size();i++){cout<<arr[i]<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【GIF动画+完整可运行源代码】C++实现 堆排序——十大经典排序算法之七的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。