希爾排序演算法深度解析：從增量序列到 Java 高效實作

前言

希爾排序是插入排序的改進版，透過「分組插入排序」打破 O(n²) 魔咒，歷史地位極高。本文將深入剖析其核心思想、增量序列選擇對效能的劇烈影響、Java 實作細節、穩定性與適用場景。

核心思想：分組插入排序

1. 選擇增量 h（>1），按間距 h 將陣列分為 h 組。
2. 對每組獨立執行插入排序，使局部有序。
3. 縮小增量（如 h = h/2 或特定序列），重複上述步驟。
4. 最終增量為 1，執行標準插入排序完成排序。

關鍵洞見：大增量時元素長距離移動，快速接近最終位置；小增量時陣列近乎有序，插入排序極快。

增量序列決定生死

鐵律：相鄰增量不應有除 1 外的公因子，否則前輪排序成果被後輪抵銷。

Java 實作（Knuth 序列）

public class ShellSort {
    public static void sort(int[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;  // 最大增量 < N/3

        while (h >= 1) {
            // h-有序化
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    swap(a, j, j - h);
                }
            }
            h /= 3;  // 下一個增量
        }
    }

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

輸出範例（含中間過程）：

5 3 6 2 1 9 4 8 7
1 3 6 2 5 9 4 8 7
1 2 3 6 5 9 4 8 7
1 2 3 5 6 9 4 8 7
1 2 3 4 5 6 9 8 7
1 2 3 4 5 6 8 9 7
1 2 3 4 5 6 7 8 9

效能與特性總覽

• 時間複雜度：高度依賴增量序列，最佳 O(n⁴ᐟ³) ~ O(n¹·⁵)，最差 O(n²)。
• 空間複雜度：O(1) 原地排序。
• 穩定性：不穩定。同值元素可能在不同分組、不同輪次被交換順序。
• 適應性：對近乎有序資料表現優異。

適用場景與現代定位

• 中小型資料量（< 5000 元素），且記憶體受限、需原地排序。
• 嵌入式系統、即時系統（確定性優於快排最差 O(n²)）。
• 教學用途：理解「預排序」與增量設計思想。
• 不建議：大數據量、高效能要求場景 → 改用 QuickSort、MergeSort、TimSort (Java/JDK 內建)。

總結

希爾排序是演算法史上的里程碑，證明了 O(n²) 非極限。雖已非主流首選，但其「分組預排序」思想啟發了後世無數演算法。掌握增量序列選擇與實作細節，能深化對排序本質的理解。