Java 排序算法總結：堆排序原理、實現與性能分析

堆排序核心思想

堆排序利用二叉堆（完全二叉樹）特性：大根堆中父節點 ≥ 子節點，堆頂為最大元素。算法分兩階段：

1. 建堆：將無序數組調整為大根堆（自底向上 heapify）。
2. 排序：反覆交換堆頂（最大值）與堆尾元素，縮小堆範圍，並對新堆頂執行 heapify（下沉調整），直到堆大小為 1。

算法特性

• 時間複雜度：建堆 O(n)，n-1 次下沉調整各 O(log n)，總體 O(n log n)，且最好/最壞/平均一致。
• 空間複雜度：O(1)，原地排序。
• 穩定性：不穩定，元素長距離交換破壞相對順序。
• 適應性：非自適應，數據分佈不影響性能。

Java 完整實現（0-based 索引優化）

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;

        // 1. 建堆：從最後一個非葉子節點開始下沉
        for (int i = (n >>> 1) - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 排序：逐個提取堆頂
        for (int end = n - 1; end > 0; end--) {
            swap(arr, 0, end);        // 最大值移至末尾
            heapify(arr, end, 0);     // 對剩餘堆下沉調整
        }
    }

    // 下沉調整：將索引 i 節點下沉到合適位置，堆大小為 size
    private static void heapify(int[] arr, int size, int i) {
        int largest = i;
        int left = (i << 1) + 1;
        int right = (i << 1) + 2;

        if (left < size && arr[left] > arr[largest]) largest = left;
        if (right < size && arr[right] > arr[largest]) largest = right;

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, size, largest); // 遞歸下沉
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

關鍵優化點

• 0-based 索引：左子節點 2*i+1，右 2*i+2，父 (i-1)>>>1，無需哨兵位，緩存友好。
• 建堆 O(n) 證明：高度 h 的節點最多下沉 h 步，節點數 ≤ n/2^{h+1}，總操作 Σ h·n/2^{h+1} = O(n)。
• 迭代版 heapify：避免遞歸棧開銷，生產環境建議改為循環。

與快速排序、歸併排序對比

實際應用建議

Java Arrays.sort() 基本類型用雙軸快速排序，對象用 TimSort。堆排序常用於：

• 嵌入式/實時系統（最壞時間確定）。
• Top-K 問題（維護大小 K 的小根堆，O(n log k)）。
• 優先隊列底層實現（JDK PriorityQueue 即基於堆）。