您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

堆積排序演算法詳解與 Java 高效實作：從堆建構到原地排序

編輯：Java 相關知識

前言

堆積排序結合了完全二叉樹結構與選擇排序思想，保證 O(n log n) 最差時間複雜度且僅需 O(1) 額外空間。本文將從堆定義、建堆策略、排序流程、Java 實作細節到效能特性完整剖析。

堆的定義與陣列映射

大根堆：每個節點值 ≥ 子節點值，根節點為最大值。
小根堆：每個節點值 ≤ 子節點值，根節點為最小值。
完全二叉樹陣列索引公式（0-based）：
父節點：(i-1)/2 | 左子節點：2*i+1 | 右子節點：2*i+2

核心操作：下沉與上浮

下沉 - 用於建堆、刪除堆頂後調整

private void sink(int[] a, int k, int N) {
    while (2*k + 1 < N) {
        int j = 2*k + 1;              // 左子節點
        if (j+1 < N && a[j] < a[j+1]) j++;  // 取較大子節點
        if (a[k] >= a[j]) break;      // 已符合堆序
        swap(a, k, j);
        k = j;
    }
}

上浮 - 用於插入新元素

private void swim(int[] a, int k) {
    while (k > 0 && a[(k-1)/2] < a[k]) {
        swap(a, (k-1)/2, k);
        k = (k-1)/2;
    }
}

建堆兩大策略

策略	方法	時間複雜度	特點
下沉法	從最後一個非葉節點 (N/2-1) 反向下沉至根	O(n)	標準教科書做法，產生的堆結構確定
上浮法	視首元素為堆，依序插入其餘元素並上浮	O(n log n)	較直觀，但較慢；產生的堆結構可能不同

工程上一律採用下沉法建堆。

堆積排序完整流程

建大根堆：for (int i = N/2-1; i >= 0; i--) sink(a, i, N);
重複 N-1 次：
a. 交換堆頂 a[0] 與堆尾 a[i]（最大值歸位）
b. 堆大小 -1，對新堆頂 sink(a, 0, i) 下沉調整

Java 完整實作

public class HeapSort {
    public static void sort(int[] a) {
        int N = a.length;
        // 1. 建大根堆
        for (int i = N/2 - 1; i >= 0; i--) sink(a, i, N);
        // 2. 排序
        while (N > 1) {
            swap(a, 0, --N);
            sink(a, 0, N);
        }
    }

    private static void sink(int[] a, int k, int N) {
        while (2*k + 1 < N) {
            int j = 2*k + 1;
            if (j+1 < N && a[j] < a[j+1]) j++;
            if (a[k] >= a[j]) break;
            swap(a, k, j);
            k = j;
        }
    }

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

複雜度與特性

指標	數值	備註
最佳/平均/最差時間	O(n log n)	與輸入分佈無關
空間複雜度	O(1)	原地排序
穩定性	不穩定	交換操作可能改變相等元素順序
適應性	無	近乎有序仍需完整流程

工程優化要點

遞歸改迭代：sink 用 while 避免呼叫棧開銷。
減少比較：子節點比較合併邏輯，如上方程式碼。
哨兵優化：在陣列末尾放入極大值可省去邊界檢查（需額外空間）。
底層優化：JDK Arrays.sort 對基本型別用 Dual-Pivot QuickSort，對物件用 TimSort（合併+插入混合），堆排序多用於優先佇列實作。