Java 進階排序算法：希爾排序原理與完整實現

算法簡介

希爾排序（Shell Sort）是插入排序的改進版，又稱「縮小增量排序」。它通過將數組按一定增量分組，對每組進行插入排序，逐步減小增量至 1，最終完成整體排序。對於中等規模數據（數千項），效能優於 O(n²) 的簡單排序，且實現簡單，代碼量小。

核心思想

1. 增量序列選擇：初始增量 h 取較大值（通常 h < n/3），常用 Knuth 序列：h = 3*h + 1（1, 4, 13, 40, 121...）。
2. 分組插入排序：對相距 h 的元素進行插入排序，使數組局部有序。
3. 遞減增量：h = (h - 1) / 3，重複上述過程直到 h = 1（即普通插入排序），此時數組基本有序，插入排序效率極高。

增量序列的影響

增量序列對性能影響巨大。理想序列應互質（除 1 外無公因數），且最後必須為 1。常見序列：

• Shell 原始：n/2, n/4, ..., 1（性能較差）
• Hibbard：2^k - 1（1, 3, 7, 15...）
• Knuth：(3^k - 1)/2（1, 4, 13, 40...）⭐ 推薦
• Sedgewick：1, 5, 19, 41, 109...（性能最優但複雜）

Java 完整實現

package com.jll.sort;

public class ShellSort {
    int[] arr;
    int size;

    public ShellSort() {
        super();
    }

    public ShellSort(int size) {
        this.size = size;
        arr = new int[size];
    }

    public static void main(String[] args) {
        ShellSort ss = new ShellSort(10);
        for (int i = 0; i < 10; i++) {
            ss.arr[i] = (int) ((Math.random() * 100) + 1);
            System.out.print(ss.arr[i] + " ");
        }
        ss.shellSort();
        System.out.println();
        System.out.println("after sort:");
        for (int i = 0; i < 10; i++) {
            System.out.print(ss.arr[i] + " ");
        }
    }

    public void shellSort() {
        int h = 1;
        // 計算初始增量：最大小於 size/3 的 Knuth 序列值
        while (h <= size / 3) {
            h = h * 3 + 1;
        }
        // 逐步減小增量
        for (; h > 0; h = (h - 1) / 3) {
            // 對每個分組進行插入排序
            for (int i = h; i < size; i++) {
                int temp = arr[i];
                int j = i;
                // 向前查找插入位置
                while (j > h - 1 && arr[j - h] > temp) {
                    arr[j] = arr[j - h];
                    j -= h;
                }
                arr[j] = temp;
            }
        }
    }
}

代碼解析

• 初始增量計算：while (h <= size/3) h = 3*h+1 確保 h 為最大不超過 n/3 的 Knuth 數。
• 外層循環：for (; h > 0; h = (h-1)/3) 按序列遞減增量。
• 內層插入排序：i 從 h 開始，步長為 1，實際上是對 h 個子序列並行插入排序。
• 移位而非交換：使用 temp 暫存，向後移動元素，最後插入，減少賦值次數。

複雜度分析

希爾排序不適用於極大數據集（百萬級以上），此時優先考慮快速排序、歸併排序或堆排序（O(n log n) 保證）。但對於中小型數據、嵌入式環境或教學演示，是極佳選擇。

擴展練習

• 嘗試不同增量序列（Hibbard, Sedgewick）並測試性能差異。
• 實現泛型版本 shellSort(T[] arr, Comparator<T> cmp)。
• 結合插入排序優化：當子數組長度較小時直接切換至插入排序。