上面是一個完全二叉樹（一般的完全二叉樹有點不同），優先排滿左邊，用這個理解堆排序

堆排序(從小到大為例)

首先，這個用到了樹進行描述，但是這個只是為了減少復雜度，其實堆排序實際上沒有構建一個樹形結構，而是通過了運算模擬了樹，所以，只需要知道樹長什么樣的，就可以理解這篇文章了

---

如果是想直接看代碼，文末有代碼，可以看著代碼和算法分析，對比著看

概念：
最大堆：（一個完全樹），所有的根節點的數的都比子節點的數要大，那么就說這是一個最大堆
要知道，怎么通過數字的計算：（如下構建一個數組）
[0][1][2][3][4][5][6][7][8][9][10]
假設是上面這樣的的一個數組
(這個數組很特殊，下標恰好是數據內部內容)
[0] 的子節點是[1] [2]。[1] 的子節點是[3] [4]。[2]的子節點是[5] [6]….以此類推（如果你懂了廣度搜索，那么看這個會非常簡單；同樣，你要是理解了這個，看廣搜也會是非常簡單了）
我們這里構建一個二叉樹:
parent(i) = (i - 1)/2（向下取整，通過這樣的方式找到父節點）
left(i) = 2*i +1(這是二叉樹的左節點，i是一個父節點)
right(i) = 2*i + 2（這是二叉樹的右節點，i是一個父節點）
這樣的話，就算是這是一個數組，都可以構建一個二叉樹了。在邏輯上構建好了

---

和一般的講法不同，我先講算法思路，因為我覺得這樣更好理解
算法思路：找到最大那個數，將這個數放到數組的最后面。(其實跟很多其他的排序方式都是一樣的)

---

為什么要構建這個最大堆，其實理由很簡單
對于一個三個數構成樹，那么這樣的最大堆就實現了最大的那個數就會出現在這個只有三個數構建的數的最頂端(每一個根節點都比子節點大)
這樣，我們就更容易拿到那個最大數了。要知道，如果我們是從最深層開始遍歷的，那么先把最底層的那些數中的最大數都拿出來了，進入了倒數第二層。那么一直往回走，進入到了倒數第三之后，第二次的數已經是倒數一二層中最大的了，那么再把其中的最大放到了第三層….一直這樣，走到根節點，那么根節點中的數，就會是整個堆中最大的那個數了。
同時【關鍵！！】由于，我們之前的往回走，保證了每一層的父節點都是比子節點的要大的，那么就可以說是，左右兩邊的樹本身就是一個最大堆【這個性質非常重要，先記住這個，那么接下來的算法就是迎刃而解了】

---

要知道，之前那個部分很好，實現了所有的數中最大的那個到達了最頂端，但是實際上，其他部分，還是沒有排序好的。我們現在有的，只是一個最頂端(那個根)的左右樹都是最大堆(這個在之前的遍歷過程就已經實現了)。

---

下一步的操作就是將這個最大的點，和整個堆最后的那個數進行調換(記住，這個最后的位置是會變的，如果已經排好的位置，我們就不管了，這樣最后的那個數，其實就是在說“最后的那個還沒有排好的那個數”)。

【很重要的一點】，在調換之后，不是那個整個樹的最頂端就沒有不符合了最大堆的定義了么？那么我們就需要實現恢復。這個恢復的復雜度只有O(log n) （n是整個樹的規模，記住這個n會遞減的，上面一段講述了）
前提是 左右兩邊的樹都是最大堆
這恢復的代碼如下:

int *a, size; // a是一個數組，size是我們設置那個堆的大小，不是數組的大小 void max_Heapify(int i){ // 假設左右堆都是最大堆了 int l = 2*i + 1; // 得到左子樹 int r = 2*i + 2, largest = i; // 得到右子樹 if (l < size && a[l] > a[largest])largest = l;if (r < size && a[r] > a[largest]) largest = r;if (largest != i) {int temp = a[i];a[i] = a[largest];a[largest] = temp; // 交換父節點和兩個最大堆的根節點 max_Heapify(largest);} } // 用于維護最大堆

上面的代碼，其實建立在左右都是最大堆的前提下的。
當然如果左右只有一個數，那么左右本身就是一個最大堆，那么就這個回復過程，其實是實現了前文所述的三個數所構建的樹。

接下來就實現怎么建初始的最大堆呢？
還是利用前文的分析

void build_max_Heapify(){ // 相當于從最后一層開始建堆 for(int i = size / 2 - 1; i >= 0;--i){max_Heapify(i);} }

首先最后一層肯定是不用看的，因為他們沒有子節點，也就說他們本身就是最大的那個。
那么就直接從，最后那個數的父節點來看。
有人可能要問了，上面那個為什么是size/2-1呢？
要知道，計算機語言一般都是從0開始計數的。所以，size是整個堆的大小，那么堆的最后一個數的下標其實是size-1，那么根據最開始給出的算的公式parent(i) = (i - 1)/2 (向下取整)。
那么最后那個數其實的父節點其實是，(size - 2) / 2 (向下取整)。
那么就是size / 2(向下取整) - 1。
在C\C++中，也就是size/2 - 1

---

如果對于上面的沒有疑問了，那么就可以往下看了

---

上面實現了兩個操作，一個是建最大堆的過程，一個是回復最大堆的過程，其實，整個堆排序的大體就一個完成了。
剩下的就是，每一次將最大那個數放到堆的最后面之后，就再對前面沒有排序好（但是，任然是一個在根部的左右兩邊的都是最大堆的一個數，因為每次，只是改變最頂端的那個數）的部分再進行恢復
代碼如下：

void HeapSort(){build_max_Heapify(); // 構建最大堆 for (int i = size-1; i > 0; --i) { int temp = a[i];a[i] = a[0];a[0] = temp;size -= 1;max_Heapify(0); // 恢復頂端} }

整個代碼如下：(加上了main函數的)

#include <iostream> using namespace std;int *a, size; // a是一個數組，size是我們設置那個堆的大小，不是數組的大小 void max_Heapify(int i){ // 假設左右堆都是最大堆了 int l = 2*i + 1; // 得到左子樹 int r = 2*i + 2, largest = i; // 得到右子樹 if (l < size && a[l] > a[largest])largest = l;if (r < size && a[r] > a[largest]) largest = r;if (largest != i) {int temp = a[i];a[i] = a[largest];a[largest] = temp; // 交換父節點和兩個最大堆的根節點 max_Heapify(largest);} } // 用于維護最大堆 void build_max_Heapify(){ // 相當于從最后一層開始建堆 for(int i = size / 2 - 1; i >= 0;--i){max_Heapify(i);} } void HeapSort(){build_max_Heapify(); // 構建最大堆 for (int i = size-1; i > 0; --i) { int temp = a[i];a[i] = a[0];a[0] = temp;size -= 1;max_Heapify(0); } } int main(){int n;cin >> size;n = size;a = new int[n]; // 申請空間 for (int i = 0; i < size; ++i) {cin >> a[i]; // 數據讀入 }HeapSort(); // 排序 for (int i = 0; i < n; ++i) {cout << a[i]<< " "; // 排序后輸出 }cout << endl;delete[] a; // 釋放空間 }

歡迎關注我用于做筆記的公眾號：肥宅Sean筆記

總結

以上是生活随笔為你收集整理的堆排序（C\C++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。