演算法圖解：插入排序法原理、C 語言實作與《演算法導論》經典圖示

生活中的插入排序：整理麻將/撲克牌

抓一把亂序的牌，從第二張開始，每拿一張就插入已整理好的手牌中適當位置——這就是插入排序的直覺邏輯。電腦雖需逐一比較移動，但極高速度讓過程瞬間完成。

核心演算法邏輯

• 外層迴圈：i = 1 ~ n-1，array[i] 為待插入元素。
• 內層迴圈：j = i-1 向前掃描，將大於 temp 的元素右移。
• 插入：找到 array[j] <= temp 位置，將 temp 放入 array[j+1]。
• 不變量：array[0..i] 永遠保持有序（已排序子陣列）。

C 語言標準實作

#include <stdio.h>
#define SIZE 10

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];  // 右移
            j--;
        }
        arr[j + 1] = temp;        // 插入
    }
}

int main() {
    int a[SIZE] = {5,1,8,9,4,6,3,2,7,0};
    insertion_sort(a, SIZE);
    for (int i = 0; i < SIZE; i++) printf("%-5d", a[i]);
    return 0;
}

for 迴圈版內層（等價寫法）

for (int j = i - 1; j >= 0 && arr[j] > temp; j--) {
    arr[j + 1] = arr[j];
}
arr[j + 1] = temp;

複雜度分析

• 空間複雜度：O(1) 原地排序
• 穩定性：穩定（相等元素不交換順序）
• 適應性：對近乎有序資料極快

《演算法導論》經典圖示流程

教科書以陣列 {5, 2, 4, 6, 1, 3} 為例，逐輪展示 i、j、key 變化與元素右移過程，強調「已排序子陣列」不變量的維持。

實戰優化提示

1. 二分搜尋插入點：將內層線性掃描改為 O(log i)，比較次數降為 O(n log n)，但移動次數仍 O(n²)，適合比較昂貴（如字串）場景。
2. 哨兵優化：arr[0] 設為最小值，省去 j >= 0 邊界檢查。
3. 小規模資料首選：n < 50 時常快於快速排序、合併排序（常數因子小、快取友好）。

總結

插入排序以「人類直覺整理牌」為藍本，代碼簡潔、穩定、適應性強，是小規模或近乎有序資料的最佳選擇。掌握其不變量邏輯與邊界處理，是演算法入門的關鍵一課。