插入排序在做什麼
想像你在整理手上的撲克牌：每次從桌上拿一張新牌，往左邊已經排好的牌裡找位置，把比它大的牌往右挪一格，再把新牌放進空出來的位置。
演算法做的就是這件事：
- 把陣列的左邊一段視為「已排序」，一開始只有第一個數字。
- 取出下一個數字當作待插入值（key），原位置留下空位。
- 由右往左比較：比 key 大的數字就往右位移一格，空位跟著往左移。
- 遇到不比 key 大的數字（或到了最左邊），就把 key 放進空位。
- 重複直到全部數字都處理完。
為什麼最佳情況只要 O(n)
如果資料本來就排好了，每個 key 只會跟左邊那一個數字比一次就停下來，完全不用位移。試試上方的「最佳情況」，比較次數是 n − 1、位移次數是 0。
反過來，「最差情況」是完全反序：每個 key 都要一路位移到最左邊，比較與位移都是 n(n − 1) / 2 次。
複雜度
| 最佳 | O(n) |
|---|---|
| 平均 | O(n²) |
| 最差 | O(n²) |
| 額外空間 | O(1) |
| 穩定 | 是 |
常見問題
- 插入排序和氣泡排序哪個比較快？
- 兩者平均與最差都是 O(n²)，但插入排序通常比較快，因為它只做「位移」而不是反覆「交換」，而且在資料已大致排好時接近 O(n)。
- 插入排序什麼時候最適合用？
- 資料量小，或資料已經幾乎排好時。許多標準函式庫的排序在處理小區段時，會改用插入排序。
- 插入排序是穩定的嗎？
- 是。遇到相等的值時不會越過它，所以相等元素的相對順序不變。