C 語言直接插入排序：原理圖解、代碼實現與穩定性分析

算法思想

將無序數組分為「已排序區」與「待插入區」。初始已排序區含首元素。每輪從待插入區取首元素，在已排序區中從右向左比較，找到插入位置，後移元素騰出空位，完成插入。重複直到待插入區為空。

過程圖解（以 3 2 4 1 為例）

初始: [3] | [2 4 1]
第1輪: 2<3 → 插入前 → [2 3] | [4 1]
第2輪: 4>3 → 插入後 → [2 3 4] | [1]
第3輪: 1<2 → 插入最前 → [1 2 3 4] | []

代碼實現 (C++ 引用語法)

void insert_sort(int a[], int &n) { // n 為元素個數
    for (int i = 1; i < n; i++) {
        int t = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > t) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = t;
    }
}

關鍵特性

• 穩定排序：相等元素相對順序不變（插入時遇等值停在右側）。
• 原地排序：空間複雜度 O(1)。
• 時間複雜度：最好 O(n)（有序）、最壞 O(n²)（逆序）、平均 O(n²)。
• 適應性強：對近乎有序數組極快。

適用場景

小規模數據、近乎有序數組、需穩定排序場合。大規模數據優選快排/歸併/堆排。