資料結構：C語言實現希爾排序（縮小增量排序）

算法思想

將陣列按增量分組，對各組進行插入排序，逐步縮小增量至 1，最後一次為普通插入排序，因前序已近乎有序，效率極高。

完整程式碼

#include 
#include 

void ShellSort(int a[], int length) {
    for (int increment = length/2; increment > 0; increment /= 2) {
        for (int i = increment; i < length; i++) {
            int temp = a[i];
            int j;
            for (j = i - increment; j >= 0 && temp < a[j]; j -= increment)
                a[j + increment] = a[j];
            a[j + increment] = temp;
        }
    }
}

int main() {
    int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
    int n = sizeof(a)/sizeof(a[0]);
    printf("待排序：");
    for (int i=0;i

關鍵點

increment 遞減序列：n/2, n/4, …, 1（亦可用 Hibbard、Sedgewick 序列）。
內層插入排序以 increment 為步長。
不穩定排序，平均時間 O(n^1.3~1.5)，最壞 O(n²)。


執行結果
待排序：5 18 151 138 160 63 174 169 79 200
排序後：5 18 63 79 138 151 160 169 174 200