堆排序算法

堆排序（Heap sort）算法，是將數據看成近似完全二叉樹結構，並根據完全二叉樹的特性來進行排序的一種算法。完全二叉樹要求每個結點的值都大於等於其左右子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。

堆排序就是把先將父節點的最大數取出，並構建最大堆，再將堆繼續調整為最大堆，再次將堆頂的最大數取出，這個過程持續到剩餘數只有一個時結束。堆排序的平均時間複雜度為 O(n log2 n)，空間複雜度：O(1)，穩定性：不穩定。

主要步驟是：

1. 首先數據按照二叉數來看待，將其下標與二叉樹節點對應起來；
2. 構建最大堆（Build-Max-Heap），將堆所有數據重新排序，使其成為最大堆，並且冒出最大數；
3. 堆排序(Heap-Sort)，從最後一個子節點開始遍歷，並將根節點與其交換，也就是移除第一個數據的根節點，並做最大堆調整的遞歸調用，直到排序完成。

堆排序算法執行過程分析：

待排序數組：[7, 11, 9, 10, 12, 13, 8]

下標對應: 0 1, 2, 3, 4, 5, 6

堆與數組關係

根據以上位置關係，我們可以傳入任意數組下標i，則可以得到父節點位置parent = (i-1) / 2取整，left = i * 2 + 1，right = i * 2 + 2。

構建大頂堆，取出最大數

• 從子節點開始排序，置換頂根節點與子節點，並繼續構建大頂堆：

將子節點與根節點交換且保持大頂堆

排序完成的大頂堆

堆排序算法代碼如下：

• JS代碼版本

堆排序JS版 1/2

堆排序JS版 2/2

堆排序構建大頂堆非遞歸寫法

非遞歸理解起來不如遞歸，但本質上是一模一樣的，性能沒有什麼差別。

堆排序Python版 1/2

堆排序Python版 2/2

堆排序Java版 1/2

堆排序Java版 2/2

堆排序C語言版 1/4

堆排序C語言版 2/4

堆排序C語言版 3/4

堆排序C語言版 4/4

堆排序TS版 1/3

堆排序TS版 2/3

堆排序TS版 3/3

總結

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

堆排序的基本過程是：將待排序序列看成是一個完全二叉樹，再去基於父節點構造成一個大頂堆，也就是將整個序列的最大值冒出到堆頂的根節點。然後將末尾節點與根節點進行交換，此時末尾就為最大值。然後將剩餘的n-1個元素按照大頂堆規則進行構建，這樣會將根節點不斷冒出並交換到末尾的位置。依此遍歷全部子節點，便把最大數逐個放在末尾，從而得到有序數列。

閱讀更多 刀法如飛 的文章

關鍵字: C語言 計算複雜性理論 Python