五分鐘看懂一個高難度的排序：堆排序

摘要： 堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。 大頂堆 小頂堆 堆排序 堆排序（Heapsort）是指利用堆這種資料結構（後面的【圖解資料...

堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。

大頂堆

小頂堆

堆排序

堆排序（Heapsort）是指利用堆這種資料結構（後面的【圖解資料結構】內容會講解分析）所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

• 大頂堆：每個節點的值都大於或等於其子節點的值，在堆排序演算法中用於升序排列；

• 小頂堆：每個節點的值都小於或等於其子節點的值，在堆排序演算法中用於降序排列；

堆排序的平均時間複雜度為 Ο(nlogn)。

演算法步驟

1. 建立一個堆 H[0……n-1]；

2. 把堆首（最大值）和堆尾互換；

3. 把堆的尺寸縮小 1，並呼叫 shift_down(0)，目的是把新的陣列頂端資料調整到相應位置；

4. 重複步驟 2，直到堆的尺寸為 1。

來源： ofollow,noindex">github.com/hustcc/JS-S…

演算法演示

排序動畫過程解釋

1. 首先，將所有的數字儲存在堆中

2. 按大頂堆構建堆，其中大頂堆的一個特性是資料將被從大到小取出，將取出的數字按照相反的順序進行排列，數字就完成了排序

3. 在這裡數字 5 先入堆

4. 數字 2 入堆

5. 數字 7 入堆， 7 此時是最後一個節點，與最後一個非葉子節點（也就是數字 5 ）進行比較，由於 7 大於 5 ，所以 7 和 5 互動

6. 按照上述的操作將所有數字入堆，然後從左到右，從上到下進行調整，構造出大頂堆

7. 入堆完成之後，將堆頂元素取出，將末尾元素置於堆頂，重新調整結構，使其滿足堆定義

8. 堆頂元素數字 7 取出，末尾元素數字 4 置於堆頂，為了維護好大頂堆的定義，最後一個非葉子節點數字 5 與 4 比較，而後交換兩個數字的位置

9. 反覆執行調整+交換步驟，直到整個序列有序

程式碼實現

為了更好的讓讀者用自己熟悉的程式語言來理解動畫，筆者將貼出多種程式語言的參考程式碼，程式碼全部來源於網上。