二分搜尋的前提是「資料已排序」，所以排序與搜尋是一體兩面。這頁整理常見排序演算法的複雜度與特性，幫你在面試被問「你用的 sort 底層是什麼」「能不能比 O(n log n) 更快」時答得上來，也幫你判斷一題該不該先花 O(n log n) 排序。
排序演算法複雜度
| 演算法 | 平均 | 最壞 | 空間 | 穩定 | 比較式 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(1) | 是 | 是 |
| 選擇排序 | O(n^2) | O(n^2) | O(1) | 否 | 是 |
| 氣泡排序 | O(n^2) | O(n^2) | O(1) | 是 | 是 |
| 合併排序 | O(n log n) | O(n log n) | O(n) | 是 | 是 |
| 快速排序 | O(n log n) | O(n^2) | O(log n) | 否 | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 是 |
| 計數排序 | O(n + k) | O(n + k) | O(k) | 是 | 否 |
| 桶排序 | O(n + k) | O(n^2) | O(n + k) | 是 | 否 |
| 基數排序 | O(d(n + k)) | O(d(n + k)) | O(n + k) | 是 | 否 |
（k 為值域大小，d 為位數。）
三個關鍵屬性
- 穩定性 (stable)：相等的元素排序後是否保持原相對順序。需要「多關鍵字排序」（先按 A 再按 B，B 相同時維持 A 的序）時很重要。
- 原地 (in-place)：是否只用
O(1)／O(log n)額外空間。記憶體受限時優先。 - 比較式 (comparison-based)：是否只靠「兩兩比較」決定順序。
為什麼線性排序能突破下界
任何比較式排序最壞都不可能快於 O(n log n)（見 Problem Solving → 比較排序的下界）。計數／桶／基數排序之所以能做到 O(n)，是因為它們不靠比較，而是利用「值域有限」這個額外條件，用值本身當索引直接定位。代價是：值域 k 一旦遠大於 n，空間與時間就划不來。
TIP
面試實戰判斷：
- 值是小範圍整數（如分數 0–100、字母）→ 考慮計數排序。
- 只需要「部分有序」（第 k 大、前 k 個）→ 用堆或 Quickselect，不必整個排序。
- 一般情況 → 直接用語言內建排序（多為合併排序或 introsort 的混合），別重造輪子。
排序後能做什麼
排序常常不是答案，而是讓後續步驟變簡單的前處理：
- 排序後用二分搜尋
O(log n)查值或找邊界。 - 排序後相鄰元素才好比較 → 找重複、找最接近的配對。
- 排序後雙指針或貪心才成立（區間合併、三數之和）。