C++ 二路插入排序：環形與非環形數組對比分析

算法背景

二路插入排序是對直接插入排序的改進，利用一個輔助數組 `b`，從中間向兩側擴展，減少元素移動次數。本文對比兩種實現：環形數組（循環利用空間）與非環形雙端擴展（雙指針向兩端擴展）。

環形數組版本

void Grial_circular(int a[], int n) {
    int b[n];
    int i = 0, j = 0; // i: 右邊界, j: 左邊界(模n)
    b[0] = a[0];
    for (int k = 1; k < n; ++k) {
        if (a[k] >= b[i]) { // 插入右端
            b[(i + 1) % n] = a[k];
            i = (i + 1) % n;
        } else if (a[k] <= b[j]) { // 插入左端
            j = (j - 1 + n) % n;
            b[j] = a[k];
        } else { // 插入中間，需移動元素
            if (i - j + 1 <= n - (i - j + 1)) { // 移動較短的一側
                // 向右移動...
            } else {
                // 向左移動...
            }
        }
    }
    // 輸出：從 j 開始遍歷到 i
}

非環形雙端擴展版本

void Grial_linear(int a[], int n) {
    int b[n];
    int i = 0, j = n - 1; // i: 左端已用, j: 右端已用
    b[0] = a[0];
    for (int k = 1; k < n; ++k) {
        int lenL = i + 1, lenR = n - j;
        if (a[k] >= b[i]) { b[++i] = a[k]; }
        else if (a[k] <= b[j]) { b[--j] = a[k]; }
        else if (lenL <= lenR) { // 移動左側
            for (int m = i; b[m] > a[k]; --m) b[m+1] = b[m];
            b[m+1] = a[k]; ++i;
        } else { // 移動右側
            for (int m = j; b[m] < a[k]; ++m) b[m-1] = b[m];
            b[m-1] = a[k]; --j;
        }
    }
    // 結果在 b[j..i]
    for (int k = 0; k < n; ++k) a[k] = b[j + k];
}

核心差異對比

複雜度分析

• 時間：O(n²) 最壞情況（逆序輸入），平均 O(n²)，但移動次數約為直接插入排序的一半
• 空間：O(n) 輔助數組
• 穩定性：穩定（相等元素不交換相對順序）

實戰建議

• 教學/面試：非環形版本邏輯更清晰，易於現場編寫
• 嵌入式/內存受限：環形版本空間利用率極致，但需仔細處理邊界
• 實際工程：優先使用 `std::sort` (IntroSort, O(n log n)) 或 `std::stable_sort`

測試用例驗證

// 測試數據
int a1[] = {10,4,2,5,88,1,23}; // 7個元素
int a2[] = {2,4,77,3,1,6,3,10,8,-1}; // 10個元素
// 兩版本輸出均為升序序列