排序演算法那麼多，你真正需要搞懂的只有三個半：Quick Sort、Merge Sort、Insertion Sort，還有半個 Bubble Sort（用來面試解釋「什麼是穩定排序」）。
排序沒有銀彈
一般情況用 Quick Sort，需要穩定排序用 Merge Sort，資料量小或幾乎排好了用 Insertion Sort。Bubble Sort 和 Selection Sort 基本上只存在於教科書裡。
| 演算法 | 時間(平均) | 時間(最差) | 空間 | 穩定 |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | 是 |
| Selection Sort | O(n²) | O(n²) | O(1) | 否 |
| Insertion Sort | O(n²) | O(n²) | O(1) | 是 |
| Merge Sort | O(n log n) | O(n log n) | O(n) | 是 |
| Quick Sort | O(n log n) | O(n²) | O(log n) | 否 |
穩定性是什麼？兩個值相同的元素，排序後相對位置不變。聽起來無關緊要？等你需要「先按價格排，同價格按上架時間排」的時候就知道了。
O(n²) 三兄弟：能跑，但跑不遠
Bubble Sort 像泡泡一樣，大的往上浮。每一輪把相鄰的比一比、該交換就交換。
[64, 34, 25, 12]
第一輪：64>34 換 → 64>25 換 → 64>12 換 → [34, 25, 12, 64]
第二輪：34>25 換 → 34>12 換 → [25, 12, 34, 64]
第三輪：25>12 換 → [12, 25, 34, 64]Selection Sort 每次找最小的放前面。直覺好懂，但不穩定（交換會打亂相同元素的順序）。
Insertion Sort 像整理撲克牌，一張一張插到對的位置。它有個被低估的超能力：資料近乎有序時是 O(n)。所以 Tim Sort（Python/Java 內建排序）在小區段就是用 Insertion Sort。
[64] | 34, 25, 12 → 插入 34 → [34, 64]
[34, 64] | 25, 12 → 插入 25 → [25, 34, 64]
[25, 34, 64] | 12 → 插入 12 → [12, 25, 34, 64]程式碼比想像中短，就是「把比 key 大的往後推，空出位子塞進去」：
void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) { // 比 key 大的往後移
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 空出來的位子塞 key
}
}近乎有序時那個 while 幾乎不進去，所以退化成 O(n)——這就是它在 Tim Sort 裡當小兵的原因。
Merge Sort：穩定的好學生
分而治之：拆到只剩一個元素，再兩兩合併。
[64, 34, 25, 12]
↓ 分割
[64, 34] [25, 12]
↓ ↓
[64] [34] [25] [12]
↓ ↓ 合併
[34, 64] [12, 25]
↓ 合併
[12, 25, 34, 64]合併過程是整個演算法的精髓——兩個已排序的陣列，用兩根指標從頭比，小的先放，O(n) 搞定。
void merge(int[] arr, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(arr, left, mid + 1);
int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0, k = left;
while (i < L.length && j < R.length) {
// 用 <= 而不是 <，相等時先拿左邊——這一個字元決定了穩定性
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < L.length) arr[k++] = L[i++];
while (j < R.length) arr[k++] = R[j++];
}那個 <= 不是隨手寫的：相等時堅持先拿左邊，才保得住穩定性。改成 < 排出來一樣有序，但同值元素的相對順序就悄悄亂了——這種 bug 最難抓。
代價是什麼？需要 O(n) 額外空間。在記憶體很貴的場景（嵌入式系統之類），這可能是個 deal breaker。
Quick Sort：實務之王
選一個 pivot，小的放左邊，大的放右邊，遞迴處理。
[64, 34, 25, 12, 22, 90] pivot = 22
小於 22：[12]
大於 22：[64, 34, 25, 90]
結果：[12, 22, ...] 繼續遞迴真正的機關在 partition。經典的 Lomuto 版用一根 i 指標守住「小於 pivot」的邊界，j 一路掃，遇到小的就換到邊界內：
int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 拿最後一個當 pivot
int i = low - 1; // i 之前都是 < pivot 的
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // pivot 歸位，左小右大
return i + 1; // 回傳 pivot 最終落點
}partition 跑完，pivot 就待在它排序後的最終位置了——這一格永遠不用再動，左右兩邊各自遞迴。
為什麼最差 O(n²) 卻還是「實務上最快」？三個原因：
- 原地排序，cache 友好（Merge Sort 需要來回複製）
- 常數因子小（每步操作簡單）
- 平均 O(n log n)，最差情況可以用隨機 pivot 或三數取中避免
所以面試官問你「為什麼不直接用 Merge Sort」的時候，你可以回答：「因為 cache locality。」然後看他露出滿意的微笑。
🎬 互動視覺化：五種排序並排跑同一組資料 — 同一批亂序數字，即時看 Bubble / Selection / Insertion / Merge / Quick 各自怎麼移動、誰先排完、比較與交換次數差多少。
怎麼選？
小資料（< 50）或近乎有序 → Insertion Sort 需要穩定排序 → Merge Sort 一般情況 → Quick Sort 記憶體受限 → Quick Sort（原地排序）
其他更特殊的排序（Heap Sort、Radix Sort、Counting Sort）請看 更多排序演算法。
Bubble Sort 唯一的用途是讓你在面試時說：「我知道它很慢，但它是穩定的。」然後優雅地轉向 Quick Sort。
接下來往哪走
- 更多排序演算法 — Heap / Radix / Counting Sort，這篇「三個半」之外的專用武器
- Divide and Conquer 分治法 — Merge Sort 和 Quick Sort 都是分治，把抽象骨架看清楚
- Searching 搜尋演算法 — 資料排好序之後，下一步就是二分搜尋