插入排序家族：直接插入、折半插入、希爾排序完整解析

插入排序家族：直接插入、折半插入、希爾排序完整解析

插入排序通過構建有序序列，對未排序數據在已排序部分從後向前掃描找到位置並插入。本文詳細對比三種變體。

1. 直接插入排序

時間：O(n²)，空間：O(1)，穩定。

void InsertSort(int a[], int len) {
    for (int i = 1; i < len; i++) {
        int key = a[i], j = i-1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

2. 折半插入排序

查找插入位置用二分，移動元素仍需 O(n)，總體 O(n²)，但比較次數減少。

void BinsertSort(int a[], int len) {
    for (int i = 1; i < len; i++) {
        int key = a[i], low = 0, high = i-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (key < a[mid]) high = mid-1;
            else low = mid+1;
        }
        for (int j = i-1; j >= high+1; j--) a[j+1] = a[j];
        a[high+1] = key;
    }
}

3. 希爾排序

分組插入排序，步長序列 n/2, n/4, ..., 1。時間 O(n^{1.5}) 左右，不穩定。

void ShellSort(int a[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2)
        for (int i = 0; i < gap; i++)
            for (int j = i+gap; j < n; j += gap)
                if (a[j] < a[j-gap]) {
                    int tmp = a[j], k = j-gap;
                    while (k >= 0 && a[k] > tmp) {
                        a[k+gap] = a[k];
                        k -= gap;
                    }
                    a[k+gap] = tmp;
                }
}

動態演示過程（希爾排序例）

數組 [80,93,60,12,42,30,68,85,10]：

1. gap=4 分 4 組，組內插入排序 → [10,30,60,12,42,85,68,93,80]
2. gap=2 分 2 組，組內插入排序 → [10,12,42,30,60,80,68,85,93]
3. gap=1 直接插入排序 → [10,12,30,42,60,68,80,85,93]

複雜度對比

適用場景

• 直接插入：小規模、近乎有序數據。
• 折半插入：比較操作昂貴（如複雜對象），移動廉價。
• 希爾排序：中等規模、要求原地、不需穩定性。

測試主函數

int main() {
    int a[] = {80,93,60,12,42,30,68,85,10};
    int n = sizeof(a)/sizeof(a[0]);
    InsertSort(a,n);  // 或 BinsertSort, ShellSort
    for (int x : a) printf("%d ", x);
    return 0;
}

掌握插入排序家族是理解「分治」、「增量」、「比較與移動權衡」等算法設計思想的基石。