C 語言插入排序演算法詳解與實作

演算法核心思想

插入排序的工作原理類似整理撲克牌：將陣列分為「已排序區」與「未排序區」，初始時已排序區僅含第一個元素。每次從未排序區取出一個元素，在已排序區中由後向前掃描，找到合適位置插入，並將後續元素依序後移。過程重複直到未排序區為空。

程式碼實作

#include 
#include 

#define N 10

int main() {
    int a[N] = {-1, 3, 6, 9, 13, 22, 27, 32, 49};  /* 預留一個空位給待插元素 */
    int x, j, k;

    x = rand() % 100;
    printf("隨機產生 x 的值為: %d\n", x);

    if (x > a[N-2]) {
        a[N-1] = x;                    /* 比最大元素還大，直接放入尾部 */
    } else {
        j = 0;
        while (j <= N-2 && x > a[j])   /* 尋找插入位置 */
            j++;
        for (k = N-2; k >= j; k--)     /* 元素後移騰出空位 */
            a[k+1] = a[k];
        a[j] = x;                      /* 插入新元素 */
    }

    printf("輸出:\n");
    for (j = 0; j <= N-1; j++)
        printf("%d ", a[j]);
    return 0;
}

關鍵步驟圖解

執行結果範例

複雜度與特性分析

優化方向

• 二分查找插入位置：將查找從 O(n) 降為 O(log n)，但元素移動仍為 O(n²)。
• 哨兵節點：在陣列頭部設置哨兵，省去邊界檢查。
• 希爾排序：對插入排序進行分組跳躍，大幅提升大規模資料效能。

插入排序雖非大規模排序首選，但其簡潔、穩定、適應性強的特點，使其在工程實踐中（如 `std::sort` 小區間切換、TimSort 的基礎組件）依然佔有一席之地。