排序算法詳解：希爾排序

基本思想

希爾排序是插入排序的改進版。先取增量 d1 < n，將數組分為 d1 組（下標間距為 d1 的元素歸為一組），各組內進行直接插入排序。然後縮小增量 d2 < d1 重複，直到增量為 1（即普通插入排序）。由於前輪排序使數組趨近有序，最後一輪插入排序極快。

增量序列選擇

性能高度依賴增量序列。好序列特徵：最後必為 1；避免相鄰增量互為倍數。常用序列：n/2, n/4, ..., 1（Shell 原版）、2^k - 1 (Hibbard)、1, 4, 13, 40, ... (Sedgewick)。實驗表明比較/移動次數約 n^1.25 ~ 1.6 n^1.25。

C++ 實現（含過程打印）

#include <iostream>
#include <iomanip>
using namespace std;

void printArr(int a[], int n, int step) {
    for (int i = 0; i < n; ++i) {
        cout << setw(3) << a[i];
        if ((i+1) % step == 0) cout << endl;
    }
    cout << endl;
}

void shellSort(int a[], int n) {
    for (int step = n/2; step > 0; step /= 2) { // 增量序列
        cout << "增量 " << step << " 分組排序前：" << endl;
        printArr(a, n, step);
        // 各組內直接插入排序
        for (int i = step; i < n; ++i) {
            int tmp = a[i], j = i;
            while (j >= step && a[j-step] > tmp) {
                a[j] = a[j-step];
                j -= step;
            }
            a[j] = tmp;
        }
        cout << "排序後：" << endl;
        printArr(a, n, step);
        cout << "整體數組：" << endl;
        printArr(a, n, n);
        cout << "----------------" << endl;
    }
}

int main() {
    int a[] = {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};
    int n = sizeof(a)/sizeof(a[0]);
    shellSort(a, n);
    return 0;
}

算法分析

• 時間複雜度：依賴增量序列，最好 O(n log n)，最壞 O(n²)，平均約 O(n^1.3)。
• 空間複雜度：O(1) 原地排序。
• 穩定性：不穩定（同值元素可能跨組移動改變相對序）。

適用場景

中小規模數據（<10000）且內存受限時優於 O(n log n) 算法（無遞歸棧、無臨時數組）。大規模數據建議用快排/歸併/堆排。