經典排序算法系列（二）：插入排序、希爾排序與二分插入優化

前言：插入類排序的「構建有序區」思想

插入排序族核心：維護一個已有序的前綴區間，逐個將後續元素插入合適位置。本文涵蓋直接插入、二分插入（折半插入）、希爾排序（縮小增量排序），從原理、代碼、複雜度、適用場景全方位解析。

一、直接插入排序

1. 算法邏輯

外層遍歷 i = 1 ~ n-1，內層將 arr[i] 向左比較位移，直到找到 arr[j] <= key，插入 j+1。

2. 標準實現

void insertSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

3. 屬性分析

二、二分插入排序——優化查找位置

1. 改進點

內層線性查找插入位置 → 二分查找，比較次數從 O(n) 降為 O(log n)；但元素位移仍需 O(n)，總體時間複雜度仍為 O(n²)，僅減少比較操作。

2. 實現

void binaryInsertSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int lo = 0, hi = i - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] > key) hi = mid - 1;
            else lo = mid + 1;
        }
        // lo 為插入位置
        for (int j = i - 1; j >= lo; --j) arr[j + 1] = arr[j];
        arr[lo] = key;
    }
}

三、希爾排序——插入排序的「跨越式」升級

1. 核心思想：分組 + 插入 + 遞減增量

1. 選擇增量序列 gap = n/2, n/4, ..., 1（原文採用）。
2. 對每個 gap，將數組分為 gap 組（下標模 gap 相同），組內直接插入排序。
3. 最後 gap=1 即普通插入排序，但此時數組已基本有序，極快。

2. 增量序列選擇影響巨大

3. 實現（Shell 原版增量）

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

4. 屬性

四、三者對比與選型指南

五、工程建議

1. 小數組切換閾值：快排/歸併遞歸到底時（n < 16）改用直接插入。
2. 希爾增量用 Sedgewick：實測比 Shell 原版快 2-3 倍，代碼僅增量序列不同。
3. 二分插入適用於「比較成本高」：如字串、大結構體排序；整數排序現代 CPU 分支預測極強，線性查找未必慢。

總結

插入類排序以「構建有序區」為核心，直接插入簡洁穩定，二分插入優化比較，希爾排序通過分組跳躍打破 O(n²) 瓶頸。理解增量序列對希爾排序的決定性影響，是從「會用」到「精通」的分水嶺。