堆排序算法深度解析：原理、過程演示與 Java 高效實現

堆排序是利用二叉堆這一數據結構實現的選擇排序，時間複雜度穩定在 O(n log n)，空間複雜度 O(1)，是不穩定排序中效能最可靠的算法之一。本文從堆的性質、建堆與調整邏輯、排序流程圖解、複雜度分析到 Java 完整實現，全方位剖析堆排序。

一、二叉堆基礎

1. 定義與性質

• 完全二叉樹：除最後一層外每層節點滿，最後一層節點靠左排列
• 數組存儲：索引 0 為根，任意節點 i 的左子節點 2i+1、右子節點 2i+2、父節點 (i-1)/2
• 大頂堆：每個節點 ≥ 其子節點，根節點為最大值
• 小頂堆：每個節點 ≤ 其子節點，根節點為最小值

2. 核心操作

• 上浮：新增元素放在末尾，與父節點比較交換，直到滿足堆性質
• 下沉：根節點被替換後，與較大（小）的子節點交換，遞歸向下調整

二、堆排序算法思想

1. 建堆：將無序數組調整為大頂堆（從最後一個非葉子節點倒序下沉）
2. 排序：重複「交換堆頂與堆尾元素 → 堆大小 -1 → 下沉新堆頂」直到堆大小為 1
3. 最終數組升序排列（大頂堆）或降序（小頂堆）

三、流程圖解：以 [89, -7, 999, -89, 7, 0, -888, 7, -7] 為例

步驟 1：建立大頂堆

初始:          89
            /    \
          -7     999
         / \    /  \
      -89  7   0  -888
      / \
     7  -7

調整後大頂堆:       999
                 /      \
               89       7
              /  \     /  \
             7   -7   0  -888
            / \
          -89  7

步驟 2：首次交換與調整

• 交換 999 ↔ -7（堆尾），有序區 [999]
• 新堆頂 -7 下沉：與 89 交換 → 與 7 交換 → 完成

步驟 3：重複直到有序

每輪將當前最大值移至有序區末尾，無序區縮小，最終得到升序數組：[-888, -89, -7, -7, 0, 7, 7, 89, 999]

四、時間複雜度分析

• 建堆：O(n) —— 非直觀但經證明，非葉子節點總下沉距離之和為線性
• n-1 次調整：每次 O(log n)，總計 O(n log n)
• 總體：O(n log n)（最好/最壞/平均一致）
• 空間：O(1) 原地排序
• 穩定性：不穩定（長距離交換可能改變相等元素相對順序）

適用場景：數據量極大（百萬級+），避免快速排序遞歸導致棧溢出；嵌入式系統記憶體受限環境。

五、Java 完整實現

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // 1. 建立大頂堆：從最後一個非葉子節點開始下沉
        for (int i = (n - 2) / 2; i >= 0; i--) {
            sink(arr, i, n);
        }
        
        // 2. 逐輪提取最大值
        while (n > 1) {
            swap(arr, 0, --n);   // 堆頂與當前堆尾交換
            sink(arr, 0, n);     // 新堆頂下沉
        }
    }
    
    /** 下沉調整：將 idx 位置元素在 size 範圍內下沉到合適位置 */
    private static void sink(int[] arr, int idx, int size) {
        while (true) {
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;
            int largest = idx;
            
            if (left < size && arr[left] > arr[largest]) largest = left;
            if (right < size && arr[right] > arr[largest]) largest = right;
            if (largest == idx) break;  // 已滿足堆性質
            
            swap(arr, idx, largest);
            idx = largest;  // 繼續向下調整
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    // 測試
    public static void main(String[] args) {
        int[] data = {89, -7, 999, -89, 7, 0, -888, 7, -7};
        sort(data);
        System.out.println(Arrays.toString(data));
        // [-888, -89, -7, -7, 0, 7, 7, 89, 999]
    }
}

六、優化與變體

• 三路划分：處理大量重複鍵值時結合荷蘭國旗問題優化
• 平滑排序：利用已有序區間特性，接近 O(n) 最好情況
• 外部堆排序：超大文件分塊建堆、歸併

七、總結

堆排序以「完全二叉樹隱式存儲 + 下沉調整」實現原地 O(n log n) 排序。掌握 sink 核心邏輯與建堆的線性時間證明，是演算法面試與高效工程實踐的必修課。實際項目中，優先考慮 JDK Arrays.sort()（雙軸快排+TimSort），但在特定約束下（嵌入式、實時系統、超大數據流），手寫堆排序不可替代。