經典排序算法系列一：插入排序原理、實作與效能分析

前言：四大基礎排序族群與統一測試框架

基礎排序四大家族：**插入排序、希爾排序、交換排序、選擇排序**。為公平比較，本系列採用統一測試框架：

• 資料類型：int 陣列，單一關鍵碼
• 規模：N=10,000（避免最壞情況執行過久、計數器溢位、遞迴堆疊溢位）
• 三種輸入分佈：升序（最佳）、隨機（平均）、降序（最壞）
• 指標：KCN（關鍵碼比較次數）、RMN（記錄移動次數）、執行時間
• 複雜度歸一化：KCN/N、KCN/N²、KCN/(N log N)

一、插入排序核心思想

模擬整理撲克牌過程：將陣列分為「已排序區間」與「未排序區間」，每次從未排區間取一元素，在已排區間中尋找插入位置並平移元素騰出空間。

1. 直接插入排序

template <class T>
void InsertSort(T a[], int N, int& KCN, int& RMN) {
    KCN = RMN = 0;
    for (int i = 1; i < N; ++i) {
        T temp = a[i]; RMN++;  // 待插元素暫存
        int j = i;
        // 從右向左掃描已排區間，邊比較邊後移
        for (; j >= 1 && ++KCN && temp < a[j-1]; --j) {
            a[j] = a[j-1]; RMN++;
        }
        a[j] = temp; RMN++;  // 插入空位
    }
}

2. 折半插入排序（優化比較次數）

template <class T>
void BinaryInsertSort(T a[], int N, int& KCN, int& RMN) {
    KCN = RMN = 0;
    for (int i = 1; i < N; ++i) {
        T temp = a[i]; RMN++;
        int low = 0, high = i - 1, mid;
        // 折半查找插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (++KCN && temp < a[mid]) high = mid - 1;
            else low = mid + 1;
        }
        // 統一後移
        for (int j = i; j > low; --j) { a[j] = a[j-1]; RMN++; }
        a[low] = temp; RMN++;
    }
}

3. 希爾排序（插入排序的間隔推廣，下篇詳解）

二、效能測試結果分析

關鍵觀察

1. 最佳 O(N)：已排序輸入僅比較不移動，極適合「近乎有序」資料
2. 平均/最壞 O(N²)：雙重迴圈特性，N=10,000 仍可接受，N=100,000 明顯吃力
3. 穩定排序：相等元素不交換順序，滿足穩定性需求
4. 原地排序：O(1) 額外空間
5. 線上演算法：可邊讀取資料邊排序，適合串流處理

三、實務應用場景

• 小規模資料（N < 50）：標準庫 std::sort 內部常切換至插入排序
• 近乎有序資料：日誌追加、時間序列資料流
• 教學與嵌入式：程式碼簡潔、無遞迴、堆疊消耗極小
• 混合排序基石：TimSort（Python/Java/Android）、Introsort 皆以插入排序處理小區間

四、優化變體速覽

總結

插入排序雖非大規模首選，但其簡潔、穩定、適應性強、小規模極快的特性，使其成為工業級排序引擎不可或缺的微觀基石。下一篇將揭示希爾排序如何以「間隔插入」突破 O(N²) 瓶頸。