希爾排序 (Shell Sort) Java 實現與增量序列深度解析

希爾排序核心原理

希爾排序是插入排序的改進版，又稱縮小增量排序。核心思想：先按增量 gap 將陣列分為若干子序列，對每個子序列進行直接插入排序；逐漸縮小增量至 1，最終進行一次完整插入排序。利用「近乎有序時插入排序極快」的特性，大幅減少移動次數。

時間/空間複雜度

Java 標準實現 (Shell 增量序列: n/2, n/4, ..., 1)

public class ShellSort {

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int n = arr.length;
        // 增量序列：n/2, n/4, ..., 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 對每個分組進行插入排序
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i - gap;

                // 組內插入排序：步長為 gap
                while (j >= 0 && arr[j] > key) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = key;
            }
        }
    }

    // 測試
    public static void main(String[] args) {
        int[] data = {9, 5, 1, 4, 3, 8, 2, 6, 7};
        shellSort(data);
        System.out.println(Arrays.toString(data)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

增量序列選擇對效能的關鍵影響

增量序列決定希爾排序實際效能，常見序列對比：

Sedgewick 序列 Java 實現

public static void shellSortSedgewick(int[] arr) {
    if (arr == null || arr.length <= 1) return;

    int n = arr.length;
    // 預計算 Sedgewick 增量 (小於 n)
    int[] gaps = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049, 1073643521};
    
    // 找到第一個小於 n 的增量起始索引
    int startIdx = 0;
    while (startIdx < gaps.length && gaps[startIdx] >= n) startIdx++;

    for (int k = startIdx; k >= 0; k--) {
        int gap = gaps[k];
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }
}

為什麼希爾排序不穩定？

// 例子：[5a, 3, 5b, 1] gap=2
// 分組0: [5a, 5b] → 排序後 [5a, 5b] (相對順序不變)
// 分組1: [3, 1]   → 排序後 [1, 3]
// 合併: [5a, 1, 5b, 3] → 5a 在 5b 前
// 但 gap=1 最後排序可能交換 5a 和 5b 相對位置

跨組交換導致相同元素相對順序可能改變。

實戰應用建議

1. 中等規模陣列 (1000-10000)：希爾排序比 O(n²) 排序快得多，實現簡單
2. 嵌入式/記憶體受限：O(1) 空間，無遞迴棧溢位風險
3. 不需穩定性：如整數、ID 排序
4. 替代方案：Java 內建 Arrays.sort() (雙軸快排/TimSort) 通常更快且穩定

常見錯誤避坑

• 增量序列包含 0：迴圈條件 gap > 0，確保最後執行 gap=1
• 內層索引越界：j >= 0 檢查在 arr[j] 之前
• 步長錯誤：移動時 j -= gap，賦值時 arr[j + gap]
• 增量計算溢位：大陣列用 n >>> 1 而非 n / 2 (無符號右移)