🎯 什麼情境該想到我
當你「資料量小、或資料本來就幾乎排好了」的時候。
★ 它看起來是個教學用的玩具，但每一個工業級排序實作的最底層都有它——這才是該記住它的理由。
⚙️ 怎麼用（機制與推導）
運作機制
把陣列分成「已排序的前綴」與「未處理的後綴」，每次從後綴取一個元素，往前找到它該待的位置插進去。
[5] 2 4 6 1 3 已排序前綴 = [5]
[2 5] 4 6 1 3 2 往前擠過 5
[2 4 5] 6 1 3 4 往前擠過 5
[2 4 5 6] 1 3 6 不用動
[1 2 4 5 6] 3 1 一路擠到最前面 ← 這一步搬了 4 次
[1 2 3 4 5 6]
就是摸撲克牌的排法：手上的牌永遠是排好的，抽到新牌就插進去。
func InsertionSort[T cmp.Ordered](a []T) {
for i := 1; i < len(a); i++ {
key := a[i]
j := i - 1
// ★ 用「搬移」而不是「交換」：交換要寫 3 次記憶體，搬移只要 1 次
for j >= 0 && a[j] > key {
a[j+1] = a[j]
j--
}
a[j+1] = key
}
}
a[j] > key不能寫成>=—— 寫成>=會讓相等的元素互相跨越，穩定性就沒了。
★ 複雜度：它的執行時間正比於「逆序對」數量
| 情況 | 比較/搬移次數 | 複雜度 |
|---|---|---|
| 已排序 | 每個元素比 1 次就停 | Θ(n) |
| 逆序 | 第 個要往前走 步 → | Θ(n²) |
| 平均 | 平均往前走 步 | Θ(n²) |
更精確的說法（這是插入排序真正的特徵）：
逆序對 = 滿足 且 的配對數。
★ 所以「近乎排好的資料」上它是線性的。
一個只有 個逆序對的陣列，插入排序只花 。
這個性質是快速排序、TimSort 都比不上的——它們無法利用既有的有序性做到這麼徹底。
四個性質
| 性質 | 說明 |
|---|---|
| 穩定 | 相等元素的相對順序不變（見上面那個 > vs >=） |
| 原地 | 額外空間 |
| 自適應 | 越接近有序越快 |
| ★ 線上（online） | 可以邊接收資料邊排序——不需要事先知道全部資料。合併排序與快速排序都做不到 |
★ 為什麼工業級排序裡都有它
所有主流排序在「分段夠小」時都切換成插入排序：
| 實作 | 做法 |
|---|---|
Go slices.Sort | pdqsort，小分段切插入排序 |
JS（V8）Array.sort | TimSort，短的 run 用二分插入排序建立 |
C++ std::sort | introsort，末段用插入排序 |
為什麼： 的演算法有較大的常數（遞迴呼叫、pivot 選擇、額外記憶體）。
在 左右時，插入排序的低常數 + 快取友善（純順序存取）會贏過漸進上更好的演算法。
★ 這是「漸進複雜度不是全部」最經典的例子，面試很值得講。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- 資料量一大就不能用。 的隨機資料， 約 次操作——會跑到天荒地老。
- 實務上不要自己寫排序。Go 用
slices.Sort/slices.SortFunc，JS 用Array.prototype.sort。手寫插入排序只在「你正在實作排序庫」或「面試」時有意義。 - 二分插入排序只省比較不省搬移。用二分搜尋找插入位置能把比較次數降到 ，但搬移仍然是 ——資料搬移才是瓶頸，所以幾乎沒有幫助。
- 選擇排序不是它的替代品。選擇排序在任何情況下都是 ，不具備自適應性，而且不穩定。插入排序嚴格優於它。
- 鏈結串列上可以做到 插入，但找位置仍要 走訪，總複雜度不變（見 鏈結串列）。