希爾排序：插入排序的間距優化實戰

編輯：關於C語言

希爾排序核心思想

希爾排序是直接插入排序的重大改進版本。直接插入排序每次只能將元素移動一位，當小數值位於陣列末尾時需大量移動操作。希爾排序引入增量序列概念，先按固定間距分組進行插入排序，使元素能「大步跨越」快速接近最終位置，隨著增量逐漸縮小至 1，最終退化為標準插入排序完成精細調整。

演算法流程

選取初始增量 increment = n / 2（n 為陣列長度）。
將陣列按增量分為 increment 個子序列，各子序列內部進行直接插入排序。
增量縮半 increment /= 2，重複步驟 2。
當增量為 1 時執行最後一次插入排序，排序完成。

常見增量序列：Shell 原始序列 (n/2, n/4, ..., 1)、Hibbard 序列 (2^k-1)、Sedgewick 序列等，不同序列影響效能上限。

C 語言完整實現代碼

#include <stdio.h>
#include <stdlib.h>

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

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：\n"); print(arr, n);
    ShellSort(arr, n);
    printf("排序後：\n"); print(arr, n);
    return 0;
}

效能特性分析

指標	數值/特性
時間複雜度	依增量序列而異：O(n²) ~ O(n^1.3) ~ O(n log²n)
空間複雜度	O(1)
穩定性	不穩定（相同元素可能因跨組移動改變相對順序）
適用場景	中等規模資料（n < 5000），嵌入式系統、系統級排序庫備選