希爾排序：從插入排序到子序列分組的間距序列藝術

核心思想

希爾排序是插入排序的改進版：

• 插入排序對基本有序數組極快（接近 O(n)），但對逆序數組為 O(n²)。
• 希爾排序先按間距 (gap) 將數組分為若干子序列，對每個子序列進行插入排序，使數組「大致有序」。
• 逐步縮小間距，最終 gap=1 時為標準插入排序，此時數組已近乎有序，極快完成。

間距序列選擇：決定性能的關鍵

標準實現（Knuth 序列：h = 3h + 1）

void shell_sort(int a[], int n) {
    // 生成最大間距 < n
    int h = 1;
    while (h < n / 3) h = 3 * h + 1;  // 1, 4, 13, 40, 121...

    for (; h >= 1; h /= 3) {
        // 對每個間距為 h 的子序列插入排序
        for (int i = h; i < n; ++i) {
            int tmp = a[i];
            int j = i;
            while (j >= h && a[j - h] > tmp) {
                a[j] = a[j - h];
                j -= h;
            }
            a[j] = tmp;
        }
    }
}

複雜度分析

• 時間：取決於間距序列。最壞 O(n²)（Shell 原版），最佳已知 O(n log² n)（Pratt），實踐中 Sedgewick/Ciura 接近 O(n^{1.2~1.5})。
• 空間：O(1) 原地排序。
• 穩定性：不穩定（長距離交換可能改變相等元素相對順序）。

為什麼間距為 1 時必須是最後一輪？

若 gap=1 不在最後，後續更大間距會打亂已排序的局部順序。gap=1 保證最終全局有序。

工程優化技巧

1. 預計算間距表：避免運行時計算，直接用 Ciura 序列靜態數組。
2. 二分插入：子序列較長時，用二分查找插入位置，減少比較次數（但移動次數不變）。
3. 混合排序：小數組（< 50）直接用插入排序，大數組用希爾排序。

對比：希爾排序 vs 快排 vs 歸併

總結

希爾排序是「最簡單的非 O(n²) 排序」，通過預排序思想大幅提升插入排序效能。選擇優秀間距序列（Ciura/Sedgewick）可使其在中小規模數據（< 10⁵）上媲美快排，且代碼極短、無遞歸、原地排序，極適合嵌入式與系統級開發。