演算法圖解：直接插入排序法原理、過程演示與 Java 實作代碼

直接插入排序核心邏輯

將待排序記錄逐一插入已排序有序序列適當位置，直到全部插入完畢。

過程演示：陣列 {60, 71, 49, 11, 24, 3, 66}

1. 前 3 個已排序：{49, 60, 71}
2. 插入 11：哨兵 r[0]=11，從 71 向左比較右移，插入位置 r[1] → {11, 49, 60, 71}
3. 後續 24、3、66 同理插入，最終得 {3, 11, 24, 49, 60, 66, 71}

演算法步驟

1. 設哨兵 r[0] 存待插入值。
2. 從有序區末尾向前掃描 j。
3. 大於哨兵者右移 r[j+1] = r[j]。
4. 遇到 ≤ 哨兵停止，哨兵存入 r[j+1]。

Java 實作

public void zjinsert(Record r[], int n) {
    for (int i = 1; i < n; i++) {
        Record temp = r[i];
        int j = i - 1;
        while (j >= 0 && temp.key < r[j].key) {
            r[j + 1] = r[j];
            j--;
        }
        r[j + 1] = temp;
    }
}

複雜度與特性

總結

直接插入排序以「人工整理牌」直覺為藍本，代碼簡潔、穩定、適應性強，適合小規模或近乎有序資料。哨兵技巧簡化邊界判斷，是教學與工程雙適用的經典排序演算法。