🎯 什麼情境該想到我
當你「要排一堆資料，而且要快」的時候——這是絕大多數標準庫的預設選擇。
★ 但它有一個 的最差情況，而且那個最差情況在真實資料上並不罕見。這才是這一頁的重點。
⚙️ 怎麼用（機制與推導）
運作機制：先分割，再遞迴
和 合併排序 剛好相反：
| 難的部分在哪 | |
|---|---|
| 合併排序 | 切很簡單（取中點），合併很費工 |
| 快速排序 | 分割很費工，合併免費（分完就已經排好了） |
選一個 pivot（例如 4）
[5 2 4 6 1 3]
↓ partition
[2 1 3] 4 [5 6] ← 左邊全部 ≤ 4，右邊全部 > 4
↓遞迴 ↓遞迴
[1 2 3] 4 [5 6] ← 完成，不需要合併
兩種分割法（面試常要求寫）
Lomuto（好寫，但交換次數多）
func partitionLomuto[T cmp.Ordered](a []T) int {
pivot := a[len(a)-1] // 取最後一個當 pivot
i := 0 // a[:i] 全部 <= pivot
for j := 0; j < len(a)-1; j++ {
if a[j] <= pivot {
a[i], a[j] = a[j], a[i]
i++
}
}
a[i], a[len(a)-1] = a[len(a)-1], a[i]
return i // pivot 的最終位置
}Hoare（交換次數約為 Lomuto 的 1/3，標準庫用這類）
func partitionHoare[T cmp.Ordered](a []T) int {
pivot := a[len(a)/2]
i, j := -1, len(a)
for {
for { i++; if a[i] >= pivot { break } }
for { j--; if a[j] <= pivot { break } }
if i >= j { return j } // ★ 回傳 j，而且切成 a[:j+1] 與 a[j+1:]
a[i], a[j] = a[j], a[i]
}
}★ Hoare 版本的回傳值語義和 Lomuto 不同（它不保證
a[j]就是 pivot）。
混用兩者的切分方式是這題最常見的 bug。
★ 複雜度：為什麼平均很快、最差很慘
（ = 分割後左半的大小， 是分割成本）
| 情況 | 遞迴式 | 結果 | |
|---|---|---|---|
| 最佳（每次對半） | |||
| ★ 最差（每次切出 0 和 n-1） | |||
| 平均（隨機 pivot） | — | — |
★ 為什麼「平均」很穩健——一個值得記住的直覺：
就算每次都切成 9:1 這麼糟的比例，遞迴深度也只是 ——仍然是 。
要真的退化成 ，得幾乎每一次都切出極端不平衡的分割。
★ 但最差情況在真實資料上並不罕見：
- 取第一個或最後一個元素當 pivot，遇到已排序或逆序的輸入 → 每次都切出 0 和 n-1 →
- 而「已排序的輸入」在真實系統裡非常常見（資料庫剛排過、時間序列、ID 遞增）
四種防禦
| 手段 | 說明 |
|---|---|
| 隨機 pivot | 讓對手無法預測。期望 |
| 三數取中（median-of-three） | 取首、中、尾的中位數。便宜且能擋掉「已排序」這個最常見的壞情況 |
| ★ Introsort | 追蹤遞迴深度，超過 就切換成 堆積排序。 ★ 保證最差 ，同時保留快排的平均速度——C++ std::sort 的做法 |
| ★ 三路分割（Dutch national flag） | 分成 < pivot、== pivot、> pivot 三段。★ 大量重複元素時必備——兩路分割遇到「全部相同」會退化成 |
★ 「大量重複值」是第二個常被忽略的壞情況。排一個只有 10 種值的百萬筆陣列，沒有三路分割就會爆。
★ 為什麼實務上比合併排序快（同樣 ）
| 原因 | 說明 |
|---|---|
| 原地 | 只要 的遞迴堆疊，不需要 緩衝區 |
| ★ 快取友善 | 分割是兩根指標從兩端往中間掃——連續記憶體存取，快取命中率高 |
| 常數小 | 內層迴圈只有比較和交換 |
| 不用寫回 | 合併排序每層都要把緩衝區 copy 回原陣列 |
★ Go 與 JS 的實際情況（2026-09-20 查證）
| 用什麼 | 穩定？ | |
|---|---|---|
Go slices.Sort / sort.Sort | 快排家族（pdqsort） | ❌ 官方文件明寫 “The sort is not guaranteed to be stable” |
Go slices.SortStableFunc / sort.Stable | 穩定排序 | ✅ |
JS（V8）Array.prototype.sort | TimSort（合併排序家族） | ✅ |
★ Go 官方文件直接建議：
“Note: in many situations, the newerslices.SortFuncfunction is more ergonomic and runs faster.”
——sort.Slice是舊 API（用 reflect），slices.Sort是泛型版且更快。新程式碼直接用slices。⚠️ 不要依賴特定的內部演算法。Go 的排序實作會隨版本改變，文件只承諾複雜度與是否穩定。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ 不穩定。要保留相等元素的原始順序（例如先按時間排、再按類別排）一定要用穩定排序——Go 是
slices.SortStableFunc。 - ★ 最差 是可被攻擊的。對外開放的服務若用固定 pivot 策略，攻擊者可以構造出讓你 CPU 爆滿的輸入（演算法複雜度攻擊）。標準庫都有隨機化防禦，自己寫的話一定要加。
- 大量重複值必須用三路分割。
- 遞迴深度：要對較小的那一半遞迴、較大的那半用迴圈（尾遞迴消除），否則最差情況下堆疊會爆。
- 鏈結串列上不適用（需要隨機存取）——用 合併排序。
- 外部排序不適用（需要隨機存取）——用 合併排序。
- 小陣列切換插入排序（見 插入排序）。
- 不要自己寫。除非在實作排序庫或面試。