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

算法背景

希爾排序 (Shell Sort) 是插入排序的改進版，由 Donald Shell 於 1959 年提出。核心思想：**將陣列按增量分組，對各組進行插入排序，逐步縮小增量至 1**。此時陣列已近乎有序，最終插入排序極快。

核心原理

1. 選擇增量序列 d1 > d2 > ... > dt = 1
2. 對於每個增量 dk，將陣列分為 dk 組 (下標模 dk 相同者同組)
3. 對每組獨立執行插入排序
4. 增量遞減，重複上述過程，直到增量為 1 (即普通插入排序)

為何比直接插入快？

• 初期增量大，分組多，每組元素少 → 插入極快
• 後期增量小，元素已部分有序 → 插入移動次數大幅減少
• 避免了大量元素長距離移動

增量序列選擇 (關鍵影響效能)

原則： 最後必為 1；相鄰增量盡量不為倍數關係 (避免重複比較)。

Java 完整實現 (採用 Shell 原始序列，易理解)

public class ShellSort {
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 增量序列: n/2, n/4, ..., 1
        for (int gap = n >> 1; gap > 0; gap >>= 1) {
            // 對每組進行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                // 組內插入：與 gap 間隔的元素比較
                for (j = i; j >= gap && temp < arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - gap]; // 後移
                }
                arr[j] = temp; // 插入正確位置
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {44, 33, 99, 10, 30, 20, 59, 78, 23, 48};
        System.out.print("排序前: ");
        printArray(arr);
        shellSort(arr);
        System.out.print("排序後: ");
        printArray(arr);
    }
    static void printArray(int[] a) {
        for (int v : a) System.out.print(v + " ");
        System.out.println();
    }
}

關鍵細節解析

• j -= gap：跨組比較的步長
• temp 暫存待插入值，避免被覆蓋
• 內層循環條件 j >= gap && temp < arr[j-gap] 確保不越界且找到插入點即停止
• 最終賦值 arr[j] = temp 而非 arr[i]，因 j 是實際插入位置

複雜度與特性總結

實務建議

• 中小規模資料 (N < 5000) 表現優於 O(N log N) 算法 (因常數小、無遞歸開銷)
• 嵌入式系統、記憶體受限環境首選 (原地、代碼量小)
• 大規模或要求穩定排序時，優先考慮 Merge Sort / TimSort (Java Arrays.sort 即採用雙軸快排 + 歸併混合)
• 若追求極致效能，可硬編碼 Ciura 序列或 Sedgewick 序列

結語

希爾排序是「簡單算法中效能最強」的代表，理解其**分組插入**與**增量序列**兩大核心，不僅能應對面試，更能在資源受限場景下派上用場。