直接插入排序算法詳解：原理、優化、哨兵機制與性能分析

基本思想

假設數組 R[1..n]，初始 R[1] 自成有序區，無序區為 R[2..n]。第 i-1 趟（i=2..n）將 R[i] 插入有序區 R[1..i-1] 適當位置，使其保持有序。類似整理撲克牌：左手有序，右手摸牌插入。

兩種插入實現方式

簡單法：先查位置，再移動

1. 在有序區 R[1..i-1] 中查找插入位置 k
2. 將 R[k..i-1] 整體後移一位
3. 將 R[i] 放入 R[k]

注意：若 R[i] 關鍵字 ≥ 有序區所有關鍵字，則原位不動。

改進法：邊查邊移（單向掃描）

將待插入記錄暫存，從右向左比較：

tmp = R[i];
for (j = i-1; j >= 1 && R[j] > tmp; j--)
    R[j+1] = R[j];  // 後移
R[j+1] = tmp;       // 插入

優勢：只需一次掃描，無需額外查找循環。

哨兵優化

利用 R[0] 作為哨兵，雙重作用：

1. 暫存待插入記錄 R[i]
2. 監視下標越界：循環條件 R[j] > tmp 中，若 j=0 時 R[0] 為最小值，自動終止

void InsertSort(int R[], int n) {
    for (int i = 2; i <= n; i++) {
        R[0] = R[i];           // 哨兵暫存
        int j = i - 1;
        while (R[j] > R[0]) {  // 自動包含 j>=1 檢查
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = R[0];
    }
}

性能特徵

算法特點總結

• 穩定排序：相等元素相對順序不變
• 適應性強：對近乎有序數據極其高效（接近 O(n)）
• 小規模優勢：n 較小時（通常 < 50），常數因子小，比快排/堆排更快
• 在線算法：可邊讀入邊排序
• 就地排序：只需 O(1) 輔助空間

工程應用場景

1. 小數組排序（如 STL std::sort 閾值以下改用插入排序）
2. 近乎有序數據維護
3. 數據流實時排序
4. 教學演示排序基本原理

直接插入排序雖非大數據首選，但其簡潔、穩定、適應性強的特性，使其在特定場景和混合排序算法中不可或缺。