插入排序演算法 C++ 實作與近乎有序資料優勢分析

插入排序模擬整理撲克牌：將未排序元素插入已排序區間適當位置。對近乎有序資料極其高效，是混合排序（如 Timsort、Introsort）的核心組件。本文提供過程圖解、標準實作與複雜度分析。

插入過程圖解（升序）

初始: 10 3 8 0 6 9 2
取 3:  3 10 | 8 0 6 9 2
取 8:  3 8 10 | 0 6 9 2
取 0:  0 3 8 10 | 6 9 2
取 6:  0 3 6 8 10 | 9 2
取 9:  0 3 6 8 9 10 | 2
取 2:  0 2 3 6 8 9 10

標準 C++ 實作

#include <iostream>
using namespace std;

void InsertSort(int arr[], int len) {
    for (int i = 1; i < len; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];  // 向右平移
            --j;
        }
        arr[j + 1] = key;  // 插入空位
    }
}

int main() {
    int arr[] = {9, 2, 8, 2, 3, 2, 4, 10, 34, 5};
    InsertSort(arr, 10);
    for (int v : arr) cout << v << ' ';  // 2 2 2 3 4 5 8 9 10 34
}

複雜度與特性

核心優勢場景

1. 近乎有序資料：比較/移動次數極少，逼近 O(N)。
2. 小規模資料：N < 50 時常快於快速排序/歸併（無遞迴開銷、緩存友善）。
3. 混合排序基石：Timsort（Python/Java）、Introsort（C++ STL）小區間皆用插入排序。
4. 線上/串流排序：資料逐筆到達即可維持有序。

二分搜尋優化（二分插入排序）

• 用 binary_search 找插入位置 O(log N)，但移動元素仍需 O(N)，總體仍 O(N²)，僅減少比較次數。
• 適用於比較極其昂貴（如長字串、複雜物件）的場景。