排序教材在最後說：只要第 (k) 小的元素時，不必把整個陣列排完。本篇把這件事做成演算法。平均線性時間的快速選擇足夠日常使用；最壞線性時間的中位數的中位數用來說明「最壞 (O(n)) 做得到」，實作較少逐行抄它。
相關教材：Sorting_Algorithms_Teaching_Materials.md（分割與快速排序）、Divide_And_Conquer_Teaching_Materials.md。
目錄
1. 問題
給 (n) 個可比較的元素，以及整數 (k)（(0 \le k < n)）。回傳第 (k) 小的元素。(k=0) 是最小，(k=n-1) 是最大，(k=\lfloor (n-1)/2 \rfloor) 是一種中位數定義。
不要求其他元素排好。只要這個元素的值，而且它在陣列裡的位置要滿足：左邊都不比它大，右邊都不比它小。
最小與最大可以一起在 (\lceil 3n/2\rceil - 2) 次比較內找完（兩兩配對，再在勝者裡找最大、敗者裡找最小）。這只對 (k=0) 和 (k=n-1) 有效，不能推廣到任意 (k)。
2. 先排序再取
(O(n\log n)) 一定對。資料要反覆查很多個不同的 (k) 時，排一次再查是划算的。只查一次，就多付了對其餘元素的排序。
堆積可以在 (O(n\log k)) 維持最小的 (k) 個（見堆積教材的 Top-K）。(k) 接近 (n/2) 時，這沒有比排序好。快速選擇針對「只查一個 (k)」。
3. 分割：和快速排序同一刀
選一個樞紐 pivot，重排區間，使樞紐落到索引 p：
- 索引
< p的元素都 (\le) 樞紐（或依實作都<） - 索引
> p的元素都 (\ge) 樞紐
這一步是線性的。快速排序接著兩邊都遞迴。快速選擇只遞迴含有 (k) 的那一邊。
4. 快速選擇
select(a, lo, hi, k): # 在 a[lo, hi) 找全域第 k 小，k 是全域索引
if hi - lo == 1: return a[lo]
p = partition(a, lo, hi) # 樞紐最後的索引
if p == k: return a[p]
if k < p: return select(a, lo, p, k)
else: return select(a, p+1, hi, k)(k) 用全域索引，遞迴時不要把它改成「子區間裡的第幾名」，除非分割的邊界也一起改。兩套寫法都可以，混用會找錯名次。
5. 手算
陣列 [7, 2, 9, 1, 5, 3]，找第 2 小（0-based 的 (k=2)）。排序後是 [1, 2, 3, 5, 7, 9]，答案應為 3。
用最後一個元素 3 當樞紐，Lomuto 分割（小於樞紐的換到左邊）：
| j | 看到 | 動作 | 陣列 |
|---|---|---|---|
| 0 | 7 | 不小於 3 | [7, 2, 9, 1, 5, 3] |
| 1 | 2 | 換到位置 0 | [2, 7, 9, 1, 5, 3] |
| 2 | 9 | 跳過 | 同上 |
| 3 | 1 | 換到位置 1 | [2, 1, 9, 7, 5, 3] |
| 4 | 5 | 跳過 | 同上 |
| 結束 | 樞紐換到位置 2 | [2, 1, 3, 7, 5, 9] |
樞紐索引是 2，等於 (k)。答案是 3。這一次沒有遞迴。
若改找 (k=0)，就只對左段 [2, 1] 繼續。左段樞紐 1 分割後落在全域索引 0，答案是 1。右段 [7, 5, 9] 完全沒被排序。
6. 期望線性、最壞二次
樞紐若每次都是當前區間的最小或最大，區間只縮短 1，成本是 (n+(n-1)+\cdots=\Theta(n^2))。和快速排序的最壞同一來源。
樞紐若隨機，或先隨機洗牌再固定取端點：期望下每次留下的區間比例是一個小於 1 的常數（精確計算是調和數，結論是期望 (\Theta(n))）。直覺是線性工作加「期望一半」的子問題：(T(n) \le O(n) + T(n/2)) 的期望版本仍是線性。這不是主定理能直接套的形狀，因為子問題大小是隨機變數。
實務上隨機樞紐的快速選擇就是答案。要避免最壞輸入，不要永遠用最後一個元素當樞紐，除非呼叫前已經洗牌。
7. 最壞線性：中位數的中位數
要一個最壞仍是 (O(n)) 的樞紐，做法是：
- 五個一組，每組用常數時間找中位數。約 (n/5) 個中位數。
- 遞迴找出這 (n/5) 個中位數的中位數，當作樞紐。
- 這個樞紐保證至少約 (3n/10) 個元素落在它的每一側（每組有一半的中位數不比它差，每組又有三個元素站在那一側）。
- 因此下一步最多遞迴 (7n/10) 的那一側。
遞迴式
[ T(n) \le T(n/5) + T(7n/10) + O(n) ]
(1/5+7/10 = 0.9 < 1)，幾何級數收斂，(T(n)=O(n))。常數比隨機版大很多，所以函式庫通常仍用隨機樞紐或 IntroSelect（類似 IntroSort：退化時改堆積），而不是默寫五個一組。
知道這件事的用途是：比較模型裡，「第 (k) 小」的最壞複雜度是線性，不是 (n\log n)。排序的 (\Omega(n\log n)) 下界沒有被打破，因為我們沒有產生全序。
8. 常見陷阱
- (k) 用 1-based 卻把 0 當最小。 先寫下來 (k) 的定義。
- 分割是嚴格
<還是<=。 相等元素很多時，嚴格小於會讓樞紐的一邊空掉，另一邊幾乎不縮。把等於樞紐的元素平均分到兩邊，或使用三向分割。 - 只遞迴一邊卻用錯邊界。
select(a, p+1, hi, k)裡的 (k) 仍是全域索引，不是k-p-1，除非函式定義的是「子陣列裡的名次」。 - 分割改壞了還需要的原順序。 快速選擇會重排陣列。呼叫端若還要原順序，先複製。
- 空區間。
hi==lo不該進來。(k) 超出 ([0,n)) 要在入口拒絕。
9. C++ 實作
#include <utility>
#include <vector>
int partition(std::vector<int>& a, int lo, int hi) {
int pivot = a[hi - 1];
int i = lo;
for (int j = lo; j < hi - 1; ++j) {
if (a[j] < pivot) std::swap(a[i++], a[j]);
}
std::swap(a[i], a[hi - 1]);
return i;
}
// k 是 0-based 全域名次。會重排 a。呼叫前應對 a 洗牌，以避免最壞輸入。
int quickselect(std::vector<int>& a, int lo, int hi, int k) {
while (hi - lo > 1) {
int p = partition(a, lo, hi);
if (p == k) return a[p];
if (k < p) hi = p;
else lo = p + 1;
}
return a[lo];
}這裡用迴圈取代遞迴，額外堆疊是 (O(1))。隨機化請在呼叫前對 a 做均勻洗牌，而不是在註解裡假裝已經隨機。
10. 練習題
[4, 1, 7, 3]，樞紐取最後一個3，分割後的陣列與樞紐索引是什麼？- 上一題若 (k=1)，答案是多少？還需要再遞迴嗎？
- 為什麼找中位數仍然可能是 (\Theta(n^2))，即使平均是線性？
- 中位數的中位數那個遞迴式，為什麼 (1/5+7/10<1) 就能得到線性？若是 (T(n)\le T(n/2)+T(n/2)+O(n)) 呢？
- 什麼時候該排序，什麼時候該快速選擇，什麼時候該用大小為 (k) 的堆積？
參考答案
- 小於 3 的只有 1。過程得到
[1, 3, 7, 4]，樞紐索引 1。 - 排序後
[1, 3, 4, 7]，第 1 小是 3。樞紐索引已經是 1，不必遞迴。 - 樞紐每次都極偏時區間只減 1。隨機化讓這個情況的機率指數下降，但某一次執行仍可能走到。最壞線性需要第 7 節那種保證，或退化時改用線性時間的選擇演算法。
- 子問題係數和小於 1，(T(n) \le cn + T(0.9n)) 展開是 (cn(1+0.9+0.9^2+\cdots)=O(n))。兩邊各一半再加 (O(n)) 是合併排序的形狀，答案是 (O(n\log n))，因為係數和等於 1，每一層都付 (O(n))，有 (\log n) 層。
- 很多個不同的 (k)：排序一次。單一個 (k) 且 (k) 接近 (n/2)：快速選擇。只保留最小的 (k) 個且 (k\ll n)、資料是串流：大小為 (k) 的堆積。
小結
快速選擇和快速排序共用分割，但只走進含第 (k) 小的那一側。隨機樞紐時期望時間線性，最壞仍是二次。五個一組取中位數的中位數把最壞也壓成線性，常數較大。它沒有違反排序下界，因為輸出不是全序。