第 04 章 入門 約 10 分鐘
插入排序：你打牌時做的事
拿一張新牌，往左邊已排好的牌堆裡塞——這就是插入排序。
建議先看過： 03-bubble-sort
你打牌時都這樣做
抽到一張新牌，從手牌右邊往左掃，看到比它大的就把它往右推一格，找到對的位置塞進去。
插入排序就是這個動作的演算法版。
動手看一遍
排 [5, 3, 8, 1, 4]：
| 步驟 | 已排序部分 (粗體) | 操作 |
|---|---|---|
| 初始 | [5, 3, 8, 1, 4] | 假設第 1 個自己排好了 |
| 拿 3 | [3, 5, 8, 1, 4] | 3 比 5 小，3 塞到 5 左邊 |
| 拿 8 | [3, 5, 8, 1, 4] | 8 比 5 大，不用動 |
| 拿 1 | [1, 3, 5, 8, 4] | 1 一路往左推到最前面 |
| 拿 4 | [1, 3, 4, 5, 8] | 4 插在 3 和 5 中間 |
💡關鍵直覺
左邊永遠是「已經排好」的，右邊是「還沒處理」的。 每次拿一張新牌，往左邊正確位置塞。
Pseudocode
Algorithm InsertionSort(A, n):
for i ← 1 to n-1:
key ← A[i] // 這次要插入的新牌
j ← i - 1
while j ≥ 0 and A[j] > key:
A[j+1] ← A[j] // 把大的往右推
j ← j - 1
A[j+1] ← key // 把 key 塞到正確位置
複雜度
| 情境 | Big-O | 為什麼 |
|---|---|---|
| 最壞（反向排序） | O(n²) | 每張牌都要推到最左邊 |
| 平均 | O(n²) | 平均推一半 |
| 最好（已排序） | O(n) | 每張牌一比就停 |
💡跟 Bubble Sort 比
Insertion Sort 在「幾乎已排序」時非常快——這是它比 Bubble Sort 強的地方。 所以實務上排「快接近排好」的資料，會選 Insertion Sort。
📝考試會這樣考
題型：給陣列，列出每一輪（每插入一張新牌後）的結果。
例：用 Insertion Sort 排 [6, 2, 5, 3, 9, 1]，列出每輪結束後的狀態。
| 輪 | 結束後 |
|---|---|
| 拿 2 | [2, 6, 5, 3, 9, 1] |
| 拿 5 | [2, 5, 6, 3, 9, 1] |
| 拿 3 | [2, 3, 5, 6, 9, 1] |
| 拿 9 | [2, 3, 5, 6, 9, 1] |
| 拿 1 | [1, 2, 3, 5, 6, 9] |
陷阱：插入排序的「每一輪」是「插入新一張牌」，跟 Bubble Sort 的「每一輪冒泡」不一樣。 看清楚題目要的是哪種紀錄方式。
這章記住
- 左邊永遠排好的，新牌往左塞。
- 最壞 O(n²)、最好 O(n)（這點比 Bubble Sort 強）。
- 適合幾乎排好的資料。
學習進度只存在你的瀏覽器，不會上傳。