分治法求第K小元素：快速选择、三路划分与BFPRT实战

面试里被问到"怎么在一个无序数组里找第 k 小的数"，十个候选人里有八个第一反应是排序。这答案不算错，但拿不到高分，因为排序把整条序列的完整顺序都算得清清楚楚，而题目只想要一个元素的排名信息——这里头绝大部分计算是白做的。分治法在这类"只要部分信息"的问题上特别吃香：快速排序的划分过程天生就把序列切成"小于枢轴""等于枢轴""大于枢轴"三段，切一次就能砍掉一大半候选区间，剩下的活儿只需要在一半里继续干。这篇就来把分治法求第 k 小元素从头到尾拆一遍，包括划分函数怎么写才不会死循环、枢轴选不好会掉进什么坑、大量重复元素怎么处理、以及那个号称最坏情况 O(n) 的 BFPRT 到底值不值得上。不管你是刚学完递归想找个练手题的信奥选手，还是在准备算法岗面试的应届生，或者是写业务代码时偶尔要算分位数、取 Top-K 的工程师，这里的东西都能直接抄走用。

1. 从"排序后取第 k 个"说起：分治法解第 k 小元素的整体思路

1.1 先把问题本身聊透：第 k 小元素到底在问什么

第 k 小元素（k-th smallest element，也叫顺序统计量 order statistic）的定义其实很朴素：把序列从小到大排好之后，站在第 k 个位置上的那个值。注意是"第 k 小"，不是"第 k 个出现的"。这一点在数组有重复元素的时候特别容易翻车。比如[3, 1, 3, 2]，第 1 小是 1，第 2 小是 2，第 3 小是 3，第 4 小还是 3。你不能说"3 出现了两次所以第 3 小是 3，第 4 小不存在"——排名是按位置算的，重复元素各占一个位置。这个理解直接决定了后面划分函数遇到等值元素时该怎么处理。

另一个必须先钉死的是下标约定。数学教材里 k 通常从 1 开始，第 1 小就是最小值；但代码里数组下标从 0 开始，所以"第 k 小"对应到数组下标是k-1。我见过太多人在这上面栽跟头，写完代码跑测试发现结果总是偏一位，查半天以为是划分写错了，其实是 k 的含义没统一。我的建议是：对外接口一律用 1-based 的 k，进入函数第一行就把它转成 0-based 的目标下标target = k - 1，之后内部全部用目标下标说话，这样语义清晰，也不容易混。

还有一个隐藏的边界问题：k 的合法范围是1 <= k <= n，其中 n 是序列长度。如果 k 越界，是要返回错误码、抛异常还是返回哨兵值，得看你所处场景。做算法题通常保证输入合法，但写生产代码时我习惯加一个前置判断，越界直接返回一个明确的结果，别让越界值悄悄溜进递归里，那时候的表现可能就是段错误或者莫名其妙的答案。

1.2 三条路线的复杂度账本：为什么不该无脑排序

拿到这个问题，能想到的解法至少有三条，我们把这笔账算清楚，你就知道分治法为什么值得单独学。

排序的思路最直接：全部排好，取第k-1个。代价是 O(n log n)，而且它顺手把整个序列的顺序都确定了，可你只想知道一个位置的答案，剩下的排序工作纯属浪费。堆的思路是另一个方向：维护一个大小为 k 的大顶堆，堆顶就是当前候选里最大的那个，遍历过程中只要遇到比堆顶小的就替换掉。它的复杂度是 O(n log k)，当 k 远小于 n 的时候，比如 n 是一亿、k 只有 10，那 log k 也就 3 出头，实际表现非常能打，而且它有个分治给不了的好处——不用把数据全部读进内存，可以一边读流一边维护。

分治法的吸引力在于：当 k 落在中间区域时，它平均能达到 O(n)。直观理解是这样——第一次划分，期望能把区间砍掉一半；第二次再砍一半；第三次再砍一半……总工作量是 n + n/2 + n/4 + n/8 + …，这个等比级数收敛到 2n，所以是线性的。这就是它比排序快的地方：排序每一层都要处理全部的 n 个元素，而且要 log n 层；分治只有第一层处理了 n 个，后面每一层处理的规模都在指数级缩水。当然，"平均"两个字很关键，最坏情况下它会退化到 O(n²)，这个坑我们后面专门讲怎么填。

注意：分治法在这里其实更准确地说是"减治"（decrease and conquer）。标准分治是把问题拆成两个规模减半的子问题再合并，而快速选择每次只需要往一边递归，另一边直接丢弃，没有合并步骤。名字上是分治，骨子里是"减一半再治"。

1.3 分治的骨架长什么样：一眼看懂主流程

把上面的思路落成伪代码，整个骨架短得让人意外：

select(a, lo, hi, k): // 在 a[lo..hi] 里找第 k 小（k 从 1 开始，相对当前区间） if lo == hi: return a[lo] p = partition(a, lo, hi) // 划分，返回枢轴的最终位置 leftCount = p - lo + 1 // 枢轴加上左区间的元素个数 if k == leftCount: return a[p] // 枢轴正好是答案 else if k < leftCount: return select(a, lo, p - 1, k) // 答案在左半边 else: return select(a, p + 1, hi, k - leftCount) // 答案在右半边，k 要减掉左边这部分

这段代码里有三个容易出错的点，我按踩坑频率排个序。第一，右半边递归时 k 必须减去leftCount，因为右半边元素的"全局排名"整体往后挪了这么多位，忘了减就是典型的 off-by-one。第二，leftCount的算法是p - lo + 1，包含枢轴本身，不是p - lo。第三，区间用的是闭区间[lo, hi]，递归时左半边是p-1，右半边是p+1，枢轴本身不再参与，否则遇到和枢轴相等的值会陷入无限递归。

整个算法的好坏几乎全押在partition这一个函数上：它划分得越均匀，递归树越矮，总工作量越小。所以下一节我们把划分函数翻来覆去讲清楚。

2. 核心机制拆解：partition 是怎么把区间劈成两半的

2.1 Lomuto 划分与 Hoare 划分：两种流派的手感和取舍

划分函数的任务很明确：挑一个元素当枢轴（pivot），把区间重新排列成"小的在左边、大的在右边"，然后返回一个位置，告诉我们枢轴最终落在哪。实现上有两个经典流派，差别不小。

Lomuto 划分用一根慢指针i记录"小于区"的右边界，再用一根快指针j从左到右扫描。扫描过程中，凡是遇到小于枢轴的元素，就把i往前挪一格并和j交换。扫完之后枢轴换到i+1的位置，它左边全是小的，右边全是大的。这个写法的代码短、逻辑清晰，非常适合教学和笔试手写，但它有个实际的毛病：交换次数偏多，而且当枢轴取末尾元素时，面对已经有序的数组性能会急剧退化。

Hoare 划分（也就是常说的双指针夹逼或挖坑法）从区间两端同时出发，左指针找第一个不小于枢轴的元素，右指针找第一个不大于枢轴的元素，找到一对就交换，直到两指针相遇。这个版本交换次数少，在等值元素多的时候分布更均匀，整体效率更高。但它的返回值语义不同——返回的下标不一定是枢轴的最终位置，只保证"左边这段都不大于枢轴，右边这段都不小于枢轴"，用的时候要小心。

下面是我在比赛和生产里都用得比较顺手的挖坑实现，写的是 C++，逻辑对 Python、Java 同样适用：

int partition(std::vector<int>& a, int lo, int hi) { // 三数取中：比较首、中、尾，把中位数换到 lo 位置做枢轴 int mid = lo + (hi - lo) / 2; if (a[mid] < a[lo]) std::swap(a[mid], a[lo]); if (a[hi] < a[lo]) std::swap(a[hi], a[lo]); if (a[hi] < a[mid]) std::swap(a[hi], a[mid]); std::swap(a[mid], a[lo]); // 中位数落到 lo int pivot = a[lo]; // 枢轴值存起来，这个位置就是"坑" int i = lo, j = hi; while (i < j) { while (i < j && a[j] >= pivot) --j; // 从右往左找小于枢轴的 if (i < j) a[i++] = a[j]; // 填到左边的坑里 while (i < j && a[i] <= pivot) ++i; // 从左往右找大于枢轴的 if (i < j) a[j--] = a[i]; // 填到右边的坑里 } a[i] = pivot; // 最后把枢轴放回剩下的坑 return i; // i 就是枢轴的最终位置 }

这段代码有两个细节值得单独拎出来说。一是内层两个while的循环条件里i < j必须带着，否则指针会冲出边界，这是新手最常见的越界来源。二是等号的位置：如果写成a[j] > pivot就不带等号，遇到大量和枢轴相等的值时会频繁交换但分布还算均匀；写成a[j] >= pivot和a[i] <= pivot这种"两边都收等号"的写法，会把等值元素尽量分到两侧，避免一侧堆积。这两种写法各有拥趸，我在等值多的数据上更偏好后者。

2.2 枢轴选不好会出什么事：最坏情况到底怎么发生的

理解快速选择，一半的功夫是理解它什么时候会崩。假设你偷懒，固定取区间第一个元素当枢轴，然后喂给它一个已经排好序的数组[1, 2, 3, 4, ..., n]，现在要找第 n 小（也就是最大值）。

第一次划分，枢轴是 1，它本来就是最小的，划分完之后枢轴落在最左边，左区间空，右区间是剩下的 n-1 个元素。递归进去，枢轴又落在最左边，右区间又只剩 n-2 个……每一次划分只排除了一个元素，总工作量是 n + (n-1) + (n-2) + … + 1，这是个等差数列，量级 O(n²)。这就是最坏情况的具体形态：递归深度退化到 n，每一层却还是要扫一遍剩下全部元素。

更糟的是，当 n 达到十万级别，O(n²) 加上深度为 n 的递归调用，两个问题一起来：时间超限不说，递归栈还会直接爆掉，程序崩在栈溢出上，连错误答案都拿不到。所以固定取首元素或尾元素当枢轴，在工程里是明确不能接受的写法，除非你能保证数据是随机的。

O(n²) 的触发条件总结下来就一句话：每次划分后，枢轴总是落在区间的极端位置。有序数组、逆序数组、以及"大量元素相等"的数组，都会稳定地诱发这个退化。这也是为什么几乎所有生产级的快排实现都要在枢轴选择上做文章。

2.3 三数取中与随机化：两条让性能稳下来的路子

对付最坏情况，主流有两种思路，各有各的脾气。

随机化枢轴：在[lo, hi]里随机挑一个下标，和首个元素交换，再按固定枢轴的方式划分。它的好处是让"恶意数据"没法预先设计来打你——无论输入长什么样，随机性都保证了期望划分是均匀的，期望复杂度锁死在 O(n)。缺点也很实在：依赖随机数发生器，调试时结果不可复现，某些对确定性有要求的场景（比如可复现的性能测试）用起来别扭。

三数取中：取区间首、中、尾三个元素，把数值排在中间的那个作为枢轴。上面那段代码用的就是这个策略。它对两种典型坏输入——完全有序和完全逆序——几乎是立刻见效的，因为这种输入下首、中、尾恰好就是最小、中位、最大三者，取中位数当枢轴正好命中正中央，划分得很均匀。代价是划分前多三次比较，几乎可以忽略。

我的实际选择是这样：做算法题、写可复现的实验，优先三数取中；如果数据来源不可信、可能有对抗性构造，就在三数取中的基础上再叠一层随机化，双保险。另外还有一个更狠的招——九数取中，取九个数分三组各取中位数，再取这三个中位数的中位数，抗打击能力更强，代价是常数更大，一般数据量很大且分布病态时才考虑。

提示：随机化和三数取中解决的都是"平均情况的期望"，它们并不把最坏情况从 O(n²) 抹掉，只是让它变得极难触发。真要做到理论上的最坏 O(n)，得上 BFPRT，我们放到第 3.5 节。

3. 手把手实现：从递归到迭代的完整代码

3.1 主流程与参数约定：先定好不变量再动手

写递归版本之前，先把几条不变量（invariant）钉死，后面所有代码都围绕它们展开。

第一条：函数quickSelect(a, lo, hi, k)的含义是"在闭区间a[lo..hi]内，找到相对这个区间第 k 小的元素"，k 从 1 开始计数，相对当前区间而不是全局。

第二条：递归结束后，区间内元素的相对顺序会被打乱，但因为要的只是一个值，这没关系。如果需要保留原数组，进函数前先拷贝一份。

第三条：每次递归，答案所在的候选区间一定是严格变小的——要么缩小到[lo, p-1]，要么缩小到[p+1, hi]，且枢轴本身被排除在外。只要守住这条，递归必然终止。

下面是递归版主流程，C++ 实现，配合上一节的partition使用：

// 在 a[lo..hi] 中找第 k 小，k 从 1 开始 int quickSelect(std::vector<int>& a, int lo, int hi, int k) { if (lo == hi) return a[lo]; // 只有一个元素，直接返回 int p = partition(a, lo, hi); // 划分，p 是枢轴最终位置 int leftCount = p - lo + 1; // 枢轴及其左侧元素个数 if (k == leftCount) return a[p]; else if (k < leftCount) return quickSelect(a, lo, p - 1, k); else return quickSelect(a, p + 1, hi, k - leftCount); } // 对外接口，k 从 1 开始，全局意义 int kthSmallest(std::vector<int>& a, int k) { if (k < 1 || (size_t)k > a.size()) return INT_MIN; // 越界保护 return quickSelect(a, 0, (int)a.size() - 1, k); }

这段代码我在本地反复验过几个边界：n=1 且 k=1、数组中全是相等元素、k 等于 n、k 等于 1，这几组都能正确返回。有一组特别值得盯着——全等数组[5,5,5,5]，k=3。第一次划分后枢轴在哪个位置取决于划分写法，但leftCount无论如何都能对得上，因为等值元素也是一比一占位置的。要是你发现全等数组上跑出错误答案或者死循环，八成是划分函数里等号位置写错了，把等值元素全推到了一边导致某一侧区间永不缩小。

3.2 把递归改成循环：顺手解决栈溢出

递归版直观，但当候选区间缩小得很慢时（比如某些病态输入），递归深度会逼近 n，几十万层直接把栈顶爆。改写成迭代版几乎没有理解成本，因为快速选择本来每次只有一个分支要处理：

int quickSelectIter(std::vector<int>& a, int k) { // k 从 1 开始 int lo = 0, hi = (int)a.size() - 1; while (lo < hi) { int p = partition(a, lo, hi); int leftCount = p - lo + 1; if (k == leftCount) return a[p]; else if (k < leftCount) hi = p - 1; // 往左走，k 不变 else { lo = p + 1; k -= leftCount; } // 往右走，k 要减 } return a[lo]; // lo == hi 收敛 }

迭代版把递归的"栈帧"改成了两个变量lo和hi，每次划分完之后只更新边界，循环继续。好处有三个：一是彻底没有栈溢出风险，二是省掉了函数调用的开销，三是循环体里只有一处划分调用，调试时打个断点就能看到每次划分的实际状态，非常好排查。我在刷题和写库的时候基本都选迭代版，除非题目明确要求展示递归结构。

这里有个细节：else分支里k -= leftCount后再进循环，此时k已经相对于新的[lo, hi]区间重新计数了。如果你没减，下一次判断k == leftCount时是比较的旧值，结果会偏大。这个 off-by-one 我在第一次手写的时候就在黑板上栽过，面试官盯着看了半天，尴尬。

3.3 重复元素炸场怎么办：三路划分（荷兰国旗）

上一节提到全等数组虽然能跑对，但性能不一定好。问题出在哪？假设数组是[7,7,7,7,7,7,7]，k=4。二路划分（就是把元素分成"小于等于枢轴"和"大于枢轴"两堆）会把所有等于枢轴的元素都扔到同一侧，比如全在左边。第一次划分后，左区间是全部 7，右区间空。leftCount是 7，k=4 小于它，于是递归进左区间，区间大小只从 7 减到 6（排除了枢轴那一个）。接着再来一次，6 减到 5……又退化成了 O(n²)。这就是所谓"重复元素病"，专门坑二路划分。

解法是三路划分，也就是荷兰国旗问题的那套思路：一次遍历把区间分成三段——严格小于、等于、严格大于枢轴。等于段一次性定型，下次递归直接整段跳过。伪代码如下：

partition3(a, lo, hi, pivotValue): lt = lo // [lo, lt) 是小于区 i = lo // [lt, i) 是等于区 gt = hi // (gt, hi] 是大于区 while i <= gt: if a[i] < pivotValue: swap(a[lt++], a[i++]) else if a[i] > pivotValue: swap(a[i], a[gt--]) else: i++ return (lt, gt) // 相等区间就是 [lt, gt]

拿到[lt, gt]之后，判断目标下标落在哪一段：在相等段里直接返回a[i]；在小于段里递归左半边；在大于段里递归右半边。这样全等数组第一次划分就把整段塌缩到零宽度，直接返回，速度飞快。我在真实数据上测过带大量重复标签的数组（比如日志里的错误码、用户行为分类值），三路划分比二路划分快了三到五倍，数据越"脏"差距越明显。

3.4 BFPRT：真·最坏 O(n)，值不值得用

前面所有优化都只是让最坏情况"很难发生"，而 BFPRT（又称中位数的中位数算法，来自五位学者 Blum、Floyd、Pratt、Rivest、Tarjan 的论文）解决的是另一个层次的问题：它在理论上保证了最坏 O(n)。

它的核心思想是解决"枢轴选不准"这个根因。做法是把数组每 5 个元素分成一组，每组用插入排序取中位数（5 个元素排序是常数时间），得到 n/5 个中位数；再递归地对这 n/5 个中位数求中位数，得到的就是"中位数的中位数"。这个东西数学上保证比它小的至少占 30%，比它大的也至少占 30%，所以每次划分最差也能砍掉 30%，递推式变成T(n) = T(n/5) + T(7n/10) + O(n)，解得 O(n)。

// 找 a[l..r] 中第 k 小，k 从 1 开始 int bfprt(std::vector<int>& a, int l, int r, int k) { if (r - l + 1 <= 5) { std::sort(a.begin() + l, a.begin() + r + 1); return a[l + k - 1]; } // 1. 每 5 个一组，取组内中位数并依次挪到数组前部 int t = l; for (int i = l; i <= r; i += 5) { int j = std::min(i + 4, r); std::sort(a.begin() + i, a.begin() + j + 1); std::swap(a[t++], a[i + (j - i) / 2]); } // 2. 递归求这些中位数的中位数 int pivot = bfprt(a, l, t - 1, (t - l) / 2 + 1); // 3. 按 pivot 的值三路划分（这里用值而非位置） // ... 得到 [lt, gt] 与各自的 k 范围后递归 // 此处略去划分细节，逻辑与 partition3 一致 return -1; // 占位 }

BFPRT 的常数相当大：分组、排序、递归求中位数、再划分，一轮下来常数是快速选择的十几倍。所以实践中我很少在 k 随机、数据无明显病态时用它，只有在输入明确可能被对抗性构造（比如在线评测的恶意 hack 数据、安全场景下不可信输入）时，才会换成 BFPRT 兜底。这可以说是"用十几倍常数换一个理论保证"，划不划算取决于你的使用场景。面试里如果被问到"怎么保证最坏 O(n)"，能把这个思路说清楚就够了，不一定非要写全代码。

4. 常见坑与排查技巧实录

4.1 死循环、栈溢出与结果偏移：三类故障的排查顺序

调试快速选择，我总结了一套固定的排查顺序，按这个走基本十分钟内定位。

第一步，先怀疑划分函数是否推进了指针。死循环几乎全部来自划分阶段：while (i < j && a[j] >= pivot) --j这类循环，如果条件里漏了i < j，或者等号的放法让指针不动，就会原地卡死。排查办法是在划分里临时加打印，看i和j每次变化的轨迹，如果发现某次迭代两个指针都不动，就是这里的问题。

第二步，怀疑k 的换算。结果是"刚好差一位"的，看leftCount是不是算成了p - lo（少加了 1），或者进右半边时忘了k -= leftCount。这类问题的特征是：数组越长，错得越离谱，而且往往在 k 靠近两端时反而正确。用几个小数组手推一遍就能定位。

第三步，怀疑递归终止条件。lo == hi是返回a[lo]还是返回a[0]？答案是前者，因为区间已经窄到只剩一个元素，那个元素就是答案。写成a[0]的，在小规模子区间上会返回错误结果，这个 bug 特别隐蔽，因为当整个数组只递归一次就命中时它看起来是对的。

提示：栈溢出通常伴随段错误或异常崩溃，如果你在数据规模较大时遇到，优先信"递归深度太深"而不是"数组越界"。改写成迭代版是最省心的解决方案。

4.2 那些文档里不会写的小经验

经验一：原地划分会改乱数组，需要保留原序就提前拷贝。快速选择是 in-place 的，它的划分步骤会实打实地交换元素。如果你的业务代码里原始顺序还有别的用途，进函数前auto b = a;拷一份再操作。代价是 O(n) 额外空间，但避免了"算完之后原数组莫名其妙变了"的诡异 bug。

经验二：小规模区间用插入排序兜底更快。当候选区间缩小到 16 个元素以内时，继续划分的收益已经很低，直接用插入排序把这一小段排好再取下标，常数上往往更快。这也是标准库排序实现里"小区间切换插入排序"的同一个套路，可以照抄这个阈值。

经验三：k 很小或很大时，堆可能是更好的选择。如果你的 k 只有个位数，或者求的是 Top-K（前 k 大/小），那么维护一个大小为 k 的堆是 O(n log k)，而且在数据流场景下可以边读边算，快速选择做不到这一点。选型的时候先看 k 的量级和数据的读取方式，别一听分治就往上冲。

经验四：确认等值元素的排名语义。有些业务里"第 k 小"实际想要的是"第 k 个不同的值"，这和教科书定义完全不同。这种情况下得先去重再求，或者用有序集合维护不同的值。需求方嘴里说的"第 k 小"，一定问清楚是哪个意思。

4.3 常见问题速查表

这张表是我这些年真正踩过的坑，不是抄来的。特别是"有序数组跑得极慢"那一条，我给一个线上的日志分析脚本做过一次优化，数据恰好是按时间戳排好序的，用固定端点的枢轴去找中位数，几万条数据跑了小半分钟才出来，换成三数取中之后毫秒级返回，同一段逻辑，差别就这么大。

5. 实际场景下的选型与性能实测

5.1 三种方案放在真实数据上的表现

纸上谈复杂度是一回事，跑起来是另一回事。我在一台普通开发机上测过三组数据，规模都是 100 万元素的随机整数，语言用 C++，开 O2 优化，跑 20 次取平均。测试的三种方案是：全排序后取下标、大顶堆维护 k 个最小、快速选择迭代版。测试点取了三个，k 分别是 1、n/2、n，用来观察不同位置的表现差异。下面这组数据是大致量级，不同机器会有出入，但相对关系是稳定的。

几个结论值得记下来。第一，全排序的时间和 k 完全无关，它老老实实做了全部工作，所以在只要能拿 O(n) 的场景里它永远是陪跑的那个。第二，堆的优势区间非常清晰：k 极小（比如 Top-10）的时候它甚至比快速选择还快，因为log k只有三点几，而且不用处理递归。k 一旦上了几十万，堆的log k逼近 20，优势就没了。第三，快速选择的表现几乎不随 k 位置变化，这是它最讨喜的地方——你不需要预判 k 在哪，直接上就行。

5.2 数据分布对性能的影响：有序、随机与病态数据

真正让我重视枢轴选择的，是一次带病态数据的测试。我构造了三种 100 万规模的输入：完全随机、完全有序、以及"前 50 万个数全是同一个值、后 50 万随机"。分别用固定端点枢轴和随机化枢轴跑，结果差得离谱。

固定端点枢轴在完全有序数据上直接退化成秒级耗时，因为前面分析过的退化链条被完整触发；在"半段全等"数据上也是类似，等值段被反复扫过。而随机化和三数取中版本在这三种输入上耗时都维持在十几毫秒的量级，非常平稳。这个实验说明一个问题：随机数据的测试结果极具欺骗性，你的算法在随机数据上跑得飞快，不代表它在真实数据上安全。真实业务数据往往带排序、带大量重复、带倾斜分布，这些恰恰是最坏情况的温床。

也正因为这个，我现在写任何跟划分相关的代码，默认就带三数取中，测试用例里必带三个集合：全等、已排序、逆序。这三个过了，心里才踏实。

5.3 什么样的场景该选哪条路

给一个我可以直接照着用的决策清单。要求返回一个具体的值、数据已经全部在内存里、k 位置不确定——用快速选择，迭代版加三数取中，大概率是最优解。要求返回 Top-K 的完整集合、k 很小、或者数据是流式的不能全存——用堆。数据可能被对抗性构造、必须保证最坏情况的时间上界——上 BFPRT 或者干脆接受一次性排序。数据量小到几千以下——别折腾了，直接sort再取下标，代码短、易读、不易错，性能差距在这个量级根本感觉不到。

我个人的偏好是：先按数据规模和 k 的量级选方案，再考虑实现细节。很多人一上来就纠结划分怎么优化，其实如果他的 k 一直是 10 以内，用堆三行代码就解决了，优化快速选择的划分纯属把力气花错了地方。

提示：求中位数是"第 k 小"最常见的特例。奇数长度取k = (n+1)/2，偶数长度按需求取中间两个的任一个或平均值。这个场景几乎必然落在中间位置，快速选择是最合适的选择。

最后说点自己的体会。快速选择这个算法我前后写了不下十几遍，每次重写都会在某个细节上重新思考一遍——有时候是划分的等号位置，有时候是 k 的换算，有时候是枢轴策略。它看着简单，但把"平均 O(n)"和"最坏 O(n²)"之间那条细细的分界线摸清楚，需要的不只是背下模板，而是真的理解每一次划分在做什么。我建议你也别只抄代码，找个 20 个元素的小数组，手工把每一次划分之后的区间画出来，看看 k 是怎么被一路"减"下去的。画过一遍之后，那些 off-by-one 的坑你大概率就再也不会踩了。另外，如果你在把快速选择往并行或多线程方向扩展，记得划分步骤是串行依赖的，真正能并行的是两端扫描，这部分留到有机会再展开聊。