Java 實作希爾排序：簡潔範例與核心邏輯解析

前言

希爾排序透過「分組插入排序」大幅提升效能。本文提供精簡可執行的 Java 範例，並解析關鍵步驟與增量選擇對效能的影響。

核心邏輯三步驟

1. 計算初始增量 h（Knuth 序列：1, 4, 13, 40... h = 3*h + 1）。
2. 對每個增量 h，執行 h-排序（間距 h 的插入排序）。
3. 縮小增量 h /= 3，重複直到 h = 1 完成最後插入排序。

精簡 Java 實作

public class ShellSortSimple {
    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) {
                    int tmp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = tmp;
                }
            }
            h /= 3;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 6, 2, 1, 9, 4, 8, 7};
        System.out.println("排序前: " + Arrays.toString(data));
        sort(data);
        System.out.println("排序後: " + Arrays.toString(data));
    }
}

執行輸出

排序前: [5, 3, 6, 2, 1, 9, 4, 8, 7]
排序後: [1, 2, 3, 4, 5, 6, 7, 8, 9]

增量序列對效能的實測差異

結論：實務上推薦 Knuth 序列（簡單、效能佳）或 Sedgewick 序列（極致效能）。

常見錯誤與修正

• 錯：for (int i = h; i < n; i += h) → 這是分組遍歷，非插入排序。
  正：for (int i = h; i < n; i++) 配合內層 j -= h 回溯。
• 錯：增量序列包含公因子（如 8, 4, 2）→ 前輪排序被後輪抵銷。
  正：使用無公因子序列（Knuth、Sedgewick、Hibbard）。

適用場景提醒

資料量 < 5,000 且記憶體受限時可考慮；大數據量請改用 Arrays.sort() (Dual-Pivot QuickSort / TimSort)。