堆排序詳解與 C++ 實現：從建堆到排序的完整指南

什麼是堆排序？

堆排序是一種基於二叉堆數據結構的比較排序算法。它利用堆這種近似完全二叉樹的特性，將數組元素視為堆中的節點，通過調整堆的結構實現排序。堆排序的時間複雜度在最好、最壞、平均情況下均為 O(n log n)，且空間複雜度僅為 O(1)，是一種不穩定的原地排序算法。

核心步驟

第一步：建堆

將無序數組構建為一個大頂堆（或小頂堆）。大頂堆要求每個父節點的值都大於等於其子節點的值。建堆過程從最後一個非葉子節點開始，自下而上、自右向左依次調用 HeapAdjust（下沉操作），確保以該節點為根的子樹滿足堆性質。

第二步：排序

1. 將堆頂元素（最大值）與堆尾元素交換，堆尾元素即為當前未排序部分的最大值，輸出到有序區。
2. 堆大小減一，忽略已排序的尾部元素。
3. 從新的堆頂開始，自上而下調用 HeapAdjust 恢復堆性質。
4. 重複上述過程直到堆大小為 1。

關鍵代碼解析

void HeapAdjust(vector<int>& L, int s, int num) {
    int temp = L[s-1];
    for (int j = 2*s; j <= num; j *= 2) {
        if (j < num && L[j-1] < L[j]) // 選取較大的子節點
            ++j;
        if (temp >= L[j-1]) // 無需交換
            break;
        L[s-1] = L[j-1]; // 將較大子節點上移
        s = j;           // 繼續向下篩選
    }
    L[s-1] = temp; // 插入臨時值
}

void HeapSort(vector<int>& L) {
    int num = L.size();
    // 建堆：從最後一個非葉子節點開始
    for (int i = num/2; i > 0; --i)
        HeapAdjust(L, i, num);
    // 排序：依次交換堆頂與堆尾
    for (int i = num; i > 1; --i) {
        swap(L[0], L[i-1]);
        HeapAdjust(L, 1, i-1); // 只調整剩餘未排序部分
    }
}

運行示例

輸入數組：{49, 38, 65, 97, 76, 13, 27, 49}

輸出結果：97 76 65 49 49 38 27 13（降序）

堆排序 vs 快速排序

堆排序最大的優勢在於最壞情況下仍能保證 O(n log n)，而快速排序在有序或近乎有序數據上會退化為 O(n²)。

圖示說明

總結

堆排序通過「建堆 + 交換頂尾 + 重建堆」三步走，實現了穩定的 O(n log n) 性能。雖然實際運行速度通常慢於優化良好的快速排序，但其最壞情況保證使其在實時系統、嵌入式開發等對性能波動敏感的場景中極具價值。掌握 HeapAdjust 的下沉邏輯是理解堆排序的關鍵。