第k小元素这个问题，乍一看像是排序算法的附属品——排完序取下标不就完了。但真在项目里遇到"从上亿条日志中捞出响应时间中位数""海量订单里定位第99百分位金额"这类需求时，你会发现在内存和时间上都吃不消全套排序。分治法里的快速选择（QuickSelect）就是专门解决这个场景的：它不追求把序列整理成完全有序，只盯住第k个位置，期望时间复杂度能做到O(n)。这篇内容我打算把寻找一个序列中第k小元素的完整思路拆开讲透，从分治和减治的区别、基准值怎么选、划分函数怎么写、边界怎么防坑，一直到三路划分、BFPRT这些进阶变体。不管你是刚学数据结构与算法的学生，还是想在工程里做Top-K统计的开发者，都能直接拿去用。代码我以C++为主，最后也会给一份Python版本，方便不同技术栈的朋友抄作业。

1. 为什么第k小元素值得单独拿出来聊

1.1 从"排序后取下标"到"只做必要的工作"

最笨的办法大家都想得到：把整个序列排好序，然后取a[k-1]。用冒泡排序是O(n²)，用堆排序或者归并排序是O(n log n)。这个方法正确性没得说，问题在于它做了大量无用功。你要的只是第k小那一个元素，可排序却把每个元素的相对顺序都安排得明明白白，这些额外信息你根本用不上。

打个生活化的比方。图书馆要找出高度排在第k位的那本书，一种做法是把所有书按高度从头到尾重新排一遍，然后再去数第k本；另一种做法是先随便挑一本书当参照，把比它矮的放左边、比它高的放右边，看左边有多少本，再决定往哪边继续找。显然后一种做法省事得多，因为你不需要关心两堆书内部到底谁高谁矮，只需要知道左边那一堆的数量够不够k。快速选择走的就是第二条路，它的核心思想可以概括成一句话：每一轮只保证基准元素回到最终位置，其余的局部无序完全不影响判断。

这里要澄清一个特别容易被混淆的概念。很多教材把快速选择也归到"分治法"名下，严格来说它更像是分治法的一个变体——减治法（Decrease and Conquer）。标准分治像归并排序，是把问题拆成两个规模减半的子问题，两边都递归求解，最后再把结果合并；而快速选择每轮划分之后，第k小元素只可能落在其中一侧，另一侧整块丢弃，所以每次只递归一个子问题。分治是"分而治之、两边都要治"，减治是"分而治之、只治一边"。正是这个"只治一边"的特性，让快速选择从归并排序的O(n log n)降到了期望O(n)。

1.2 分治法在这类"选择问题"中的核心价值

分治法处理问题有一套固定的三步：分解、解决、合并。套到第k小元素上，分解就是选基准做划分，解决就是判断第k小落在左半区还是右半区，合并这一步几乎不存在——因为你不需要把两个子结果拼起来。这种"合并不费力"的问题，恰恰是分治思想最舒服的用武之地。

把视野放宽一点，你会发现二分查找算法也是同一个套路的亲戚：每轮砍掉一半搜索区间，只往一边走，所以能做到O(log n)。快速选择可以看成是二分查找在"无序数组"上的推广——二分查找要求序列有序才能判断往哪边砍，快速选择靠一次划分临时制造出"左小右大"的局部有序，从而同样能判断往哪边砍。理解了这层关系，你对分治的理解就不再是背模板，而是能看出哪些问题适合用这种"每轮淘汰一部分"的策略。

还有一个现实价值：第k小元素是很多统计指标的计算内核。中位数就是第n/2小元素，四分位数、百分位数、Top-K热门榜，本质都是选择问题。在监控系统里算P99延迟、在推荐系统里取分数第k高的候选，如果每次都全排序一遍，数据量一大就直接卡死。掌握快速选择，等于给这类统计需求装了一个省内存又省时间的引擎。我做过一个日志分析的小工具，最开始用全排序取中位数，一千万条数据要跑十几秒，换成快速选择之后稳定在两百毫秒上下，差距非常直观。

2. 快速选择算法的核心原理拆解

2.1 分治三步走：划分、判断、舍弃

快速选择的完整流程可以拆成三个动作，循环执行直到命中目标。

第一步是划分。从当前区间a[lo..hi]里挑一个元素当基准（pivot），然后重新排列区间内的元素，让所有小于基准的排到左边，所有大于基准的排到右边，基准自己则被放到它"应该待"的最终位置上。假设这个最终位置下标是p，那么可以确定：p左边有p-lo个元素，全都比基准小；p右边有hi-p个元素，全都比基准大。

第二步是判断。把p和k比较。如果p恰好等于k，恭喜，a[p]就是答案，直接返回。这里要注意下标对齐：如果题目说找"第k小"且k从1开始计数，那么目标下标是k-1；如果k从0开始计数，目标下标就是k。这个细节我在第4章会专门讲，它是新手最容易踩的坑。

第三步是舍弃。如果p大于k，说明第k小元素在左半区，那么右半区连同基准本身全部丢掉，把区间收缩到a[lo..p-1]继续找；如果p小于k，说明第k小在右半区，左半区连同基准也全丢掉，区间收缩到a[p+1..hi]。每执行一次这三步，问题规模就缩小一截，直到命中。

理解了这个流程，"只递归一边"的优势就一目了然了。归并排序每层要处理全部n个元素，一共log n层，所以是O(n log n)；快速选择每层只处理上一次留下的一半，总工作量是n + n/2 + n/4 + ...，收敛到2n左右。

2.2 基准值选得好不好，直接决定复杂度会不会跑偏

基准值的选择是快速选择的命门。不同的选法，复杂度能差出一个数量级。

最偷懒的做法是固定选第一个或者最后一个元素当基准。这在随机数据上问题不大，但一旦遇到已经有序或者接近有序的输入，就会退化成灾难——每次划分只能确定一个元素的位置，区间从n缩到n-1再缩到n-2，递归深度变成n层，复杂度直接掉到O(n²)。现实中"已排序"的数据非常常见，比如按时间追加的日志、按ID递增导出的表，所以固定基准这个坑一定要绕开。

随机选基准是工程上最常用的方案。每次划分前，在区间内随机挑一个下标，把它和区间末尾元素交换，再拿末尾元素做基准。因为基准是随机的，无论输入数据长什么样，每一轮划分的期望效果都接近把区间对半分，整体期望复杂度稳定在O(n)。这种方案代码改动极小，收益却很大，属于"性价比之王"。

三数取中是在随机基础上再稳一手。取区间首、中、尾三个元素，排一下序，用中间那个值当基准。它能有效对抗"部分有序"的输入，而且在实现上比纯随机更容易做出确定性的划分效果。很多标准库里的排序实现（如某些C++标准库的introsort）都会用类似策略。

如果要求最坏情况下也必须是O(n)，那就要请出中位数的中位数算法（BFPRT），它通过精心挑选基准，保证每次划分至少淘汰一定比例的元素。代价是常数因子比较大，实际跑起来往往不如随机版快。这部分我在第5章展开。

2.3 期望O(n)的数学推导，其实没那么玄乎

很多人看到"平均O(n)"就犯迷糊，觉得一层n、两层n，怎么会不是O(n log n)。其实关键就在这个等比数列上。

假设随机基准下，每轮划分期望能把基准放在靠近中间的位置，那么第1轮要扫描n个元素，第2轮扫描约n/2个，第3轮约n/4个，依此类推。总工作量是：

T(n) = n + n/2 + n/4 + n/8 + ... < 2n

这是个首项为n、公比为1/2的等比数列，求和结果趋于2n，所以期望复杂度是O(n)。

严格证明要复杂一些，因为随机基准并不总能精准落在中点，最坏情况可能落在边上。用指示随机变量（indicator variable）和期望线性性可以证明，在随机化划分下，任意两个元素被比较的期望次数是O(1)，总比较次数的期望是O(n)。这个证明在《算法导论》第九章有详细推导，篇幅不小，但结论很干净。你可以这样理解：虽然偶尔会出现"运气不好、只淘汰一个元素"的糟糕划分，但这种坏情况出现的概率随划分次数急剧衰减，平均下来影响被摊平了。这也解释了为什么随机化是快速选择的标配——它把"最坏情况"变成了"小概率事件"，而不是"想躲躲不掉的必然"。

3. 从零手写一份可复用的第k小元素代码

3.1 先定接口：k从0开始还是从1开始

动手写代码之前，接口约定必须先拍死，否则后面全是玄学bug。我习惯用0-based下标：数组a[0..n-1]，要找"第k小"就传k=0表示最小值，k=1表示第二小，依此类推，即"第k小"对应排序后的下标k。这种约定和C++、Python的数组下标天然一致，少一层加减法，出错的概率就低一层。

如果题目描述是"第k小且k从1开始"，那么进入算法前先做一次k减一，或者在比较时统一用k-1。我见过太多人因为这两种约定混用，导致结果总是差一位。建议在函数注释里明确写清楚语义，比如// 返回 nums 中第 k 小（k 从 0 开始）。

另一个接口细节是：算法会原地打乱数组顺序。如果你不希望调用方拿到一个被改乱的数组，就在入口处拷贝一份，或者提前说明"本函数会修改入参"。工程里更稳妥的做法是内部拷贝，用空间换正确性，除非你明确知道调用方不在乎原数组顺序。

3.2 划分函数的实现细节（Lomuto 与 Hoare 对比）

划分函数是整个算法的心脏，写法主要分两派：Lomuto 划分和 Hoare 划分。

Lomuto 划分的思路很直白：以末尾元素为基准，用指针i记录"小于区"的下一个空位，用j从左到右扫描，遇到比基准小的就把它换到i位置并让i前进。扫描完把基准换到i位置。代码短、好懂，缺点是相比Hoare版本多做了一些交换，而且在元素大量重复时表现不佳——因为它的条件是a[j] < pivot，等于基准的元素全被推到右边，遇到全是一个值的数组会退化成O(n²)。

Hoare 划分从两端向中间夹逼：左指针找到一个不小于基准的元素停下，右指针找到一个不大于基准的元素停下，交换两者，继续夹逼，直到两指针相遇。它的交换次数更少，对重复元素更友好，是很多标准库的实际选择。代价是边界处理更绕，尤其是"基准最终位置"不再是简单的返回值，需要小心设计。我下面的主实现用Lomuto加随机基准，因为对大多数读者来说它最好理解；重复元素的问题放到第4章用三路划分专门解决。

先看一份带随机基准的Lomuto实现：

#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // Lomuto 划分：随机选基准放到末尾，返回基准最终下标 int partitionLomuto(vector<int>& a, int lo, int hi) { uniform_int_distribution<int> dist(lo, hi); swap(a[dist(rng)], a[hi]); // 随机基准换到末尾 int pivot = a[hi]; int i = lo; // i 指向"小于区"的下一个空位 for (int j = lo; j < hi; ++j) { if (a[j] < pivot) { swap(a[i], a[j]); ++i; } } swap(a[i], a[hi]); // 基准归位到 i return i; }

这段代码里有几个点值得说道。随机数发生器我用了mt19937，它是C++11之后推荐的高质量随机数引擎，比古老的rand()分布均匀得多，做随机化算法时别再用rand()凑合。uniform_int_distribution保证区间内每个下标被选中的概率相等，不会因为取模运算引入偏斜。至于swap(a[dist(rng)], a[hi])这一步，是把随机基准"藏"到末尾，让后面的划分逻辑只认末尾元素，简化代码结构。

3.3 递归主体与边界处理

划分函数写好之后，主体逻辑就顺理成章了。因为每轮只往一边递归，我们可以直接把递归改成迭代，省掉函数调用栈的开销：

// 返回 a[lo..hi] 中第 k 小（k 为 0-based 全局下标） int quickSelect(vector<int>& a, int lo, int hi, int k) { while (lo <= hi) { if (lo == hi) return a[lo]; // 区间只剩一个元素 int p = partitionLomuto(a, lo, hi); if (p == k) { return a[p]; // 命中 } else if (p > k) { hi = p - 1; // 目标在左半区 } else { lo = p + 1; // 目标在右半区 } } return -1; // 正常情况下不会到达 }

调用方式很直接：quickSelect(a, 0, n-1, k)。这里有几个边界必须提。

第一个是lo == hi的特判。虽然理论上走到这一步时区间里只剩一个元素，那个元素必然就是答案，但加上这行能让逻辑更清晰，也避免划分函数在单元素区间上做一些无意义的随机和交换。第二个是循环条件lo <= hi，用等于号是允许"区间收缩到同一位置后立即返回"，用小于号则可能漏掉最后一个元素。第三个是返回值兜底，严格来说在合法输入下不会执行到return -1，但写上它能让编译器闭嘴，也能在调试时暴露异常输入。

递归版写法如下，逻辑一样，只是用函数调用代替循环：

int quickSelectRec(vector<int>& a, int lo, int hi, int k) { if (lo == hi) return a[lo]; int p = partitionLomuto(a, lo, hi); if (p == k) return a[p]; if (p > k) return quickSelectRec(a, lo, p - 1, k); return quickSelectRec(a, p + 1, hi, k); }

我一般推荐迭代版。随机化快速选择的期望递归深度是O(log n)，理论上不会爆栈，但如果基准选得不好（比如不小心关了随机或实现有bug），深度可能接近n，迭代版就不会有这个问题。用迭代版还有个附带好处：编译器更容易做优化，实测在大数组上迭代版往往还快一点点。

4. 踩过的坑与常见问题排查实录

4.1 k值越界与经典的"差一位"错误

新手在这个算法上翻车，十有八九是k的语义搞混。总结下来有三种常见的错误组合。

第一种是把"第k小（k从1开始）"直接当0-based下标用。比如数组[3,1,4,1,5]，题目问"第2小"，正确结果是1（排序后是[1,1,3,4,5]，下标1对应1）。如果你把k=2直接传进去当全局下标，会返回下标2处的元素即3，答案就错了。修正方法是在入口做k -= 1。

第二种是区间收缩时下标带了等号或漏了等号。hi = p - 1和lo = p + 1是必须的，因为p位置的元素已经确认过不是答案（前面已经判断过p != k），把p继续留在区间里会导致下一轮划分可能返回同一个p，形成死循环。这个死循环在数据恰好有序时特别容易出现，调试起来很折磨。

第三种是k本身越界。如果k小于0或者大于等于数组长度，算法行为未定义。生产代码里一定要在入口加校验：

if (k < 0 || k >= (int)a.size()) throw out_of_range("k out of range");

提示：调试这类问题时，最有效的办法是在每轮划分后打印区间[lo, hi]、基准位置p和目标k，连续打印几轮就能看出区间是不是往正确方向收缩。别嫌麻烦，这比盯着代码空想快得多。

4.2 大量重复元素时的性能塌方

这是Lomuto划分最隐蔽的坑。考虑一个极端输入：一百万个元素全都是同一个值，比如全为7。用Lomuto划分会发生什么？条件a[j] < pivot永远为假，所以i永远不动，划分结束返回i=lo，也就是说每次划分只能把区间的左端点确定下来，区间长度从n缩到n-1，复杂度直接退化成O(n²)。一百万个元素跑O(n²)，那就是实打实的灾难。

根治办法是改用三路划分（也叫荷兰国旗问题划分），把区间分成三块：小于基准、等于基准、大于基准。等于基准的那一整块可以一次性确定位置，彻底避免重复元素被反复划分。实现如下：

// 三路划分：返回 {等于区的左端, 等于区的右端} pair<int,int> partition3(vector<int>& a, int lo, int hi) { uniform_int_distribution<int> dist(lo, hi); swap(a[dist(rng)], a[lo]); int pivot = a[lo]; int lt = lo, gt = hi, i = lo + 1; while (i <= gt) { if (a[i] < pivot) { swap(a[lt++], a[i++]); } else if (a[i] > pivot) { swap(a[i], a[gt--]); // 注意这里不推进 i } else { ++i; } } return {lt, gt}; // a[lt..gt] 全部等于 pivot }

用三路划分改写主体，判断逻辑变成：

int quickSelect3(vector<int>& a, int k) { int lo = 0, hi = (int)a.size() - 1; while (lo <= hi) { auto [lt, gt] = partition3(a, lo, hi); if (k < lt) hi = lt - 1; else if (k > gt) lo = gt + 1; else return a[k]; // k 落在等于区 } return -1; }

注意swap(a[i], a[gt--])之后不能推进i，因为换过来的元素还没检查过。这是三路划分最容易写错的地方，漏掉这一点会得到错误结果。另外循环条件里k > gt用的是严格大于，k < lt用的是严格小于，因为等于区已经直接返回。

实测下来，在含大量重复值的数组上，三路划分版本比普通Lomuto版本快一个数量级不止，而且复杂度稳定在O(n)。如果你的数据里可能有大面积重复（比如状态码、评分、类别ID这类低基数数据），强烈建议直接用三路版本。

4.3 常见问题速查表

我把这些年调试快速选择时遇到的高频问题整理成一张表，方便你按症状对号入座。

注意：调试随机化算法时，一定要先固定随机种子，让每次运行走同一条路径，否则你会在"这次对那次错"的幻觉里耗掉一整天。等逻辑验证正确后，再换回真随机种子。

5. 进阶优化与不同场景的选型

5.1 BFPRT：用最坏O(n)换更大的常数

如果业务对最坏情况有硬性要求（比如实时系统里不允许偶发的卡顿），随机化快速选择的期望O(n)就不够看了，这时候可以考虑BFPRT算法（以五位提出者Blum、Floyd、Pratt、Rivest、Tarjan命名），也叫中位数的中位数算法。

它的核心改进在选基准这一步：把数组每5个元素分成一组，对每组求中位数（小组内直接排序，5个元素排序是常数开销），再对这些组中位数递归求中位数，把这个"中位数的中位数"当作基准。这样选出来的基准保证落在比较中间的位置，每轮划分至少能淘汰掉约30%的元素，递归式变成T(n) ≤ T(n/5) + T(7n/10) + O(n)，解出最坏复杂度是O(n)。

但天下没有免费的午餐。分组、求小组中位数、递归求中位数这些操作带来不小的常数因子。实测下来，在普通随机数据上，BFPRT往往比随机化快速选择慢好几倍。所以工程中的常规做法是：默认用随机化版本，只有在确实观测到性能抖动、且分析确认是划分退化导致时，才考虑BFPRT。别一上来就上最复杂的算法，那是舍近求远。

5.2 求一次第k小 vs 反复求Top-K：快速选择与堆的取舍

快速选择不是万能的，选不选它，取决于你的查询模式。我把典型场景和推荐方案列成表：

小顶堆求"第k大"是另一套经典思路：维护一个大小为k的小顶堆，遍历元素，堆没满就塞进去，满了就比较堆顶，比堆顶大就替换。遍历完堆顶就是第k大。它和快速选择的关键区别在于，快速选择要求数据一次性都在内存里并能随机访问，而堆方法可以流式处理，适合Kafka这种不断涌入的数据流场景。求一次用快速选择，求很多次或数据在流动就用堆，这是我自己总结的选型口诀。

5.3 一份可以直接跑的Python版本

考虑到不少朋友的主力语言是Python，我给一份等效实现。Python的随机化和切片语法让代码更短：

import random def quick_select(nums, k): """返回 nums 中第 k 小元素（k 从 0 开始）""" arr = nums[:] # 拷贝，不改动调用方数据 lo, hi = 0, len(arr) - 1 while lo <= hi: p = random.randint(lo, hi) arr[p], arr[hi] = arr[hi], arr[p] pivot = arr[hi] store = lo for i in range(lo, hi): if arr[i] < pivot: arr[i], arr[store] = arr[store], arr[i] store += 1 arr[store], arr[hi] = arr[hi], arr[store] if store == k: return arr[store] elif store > k: hi = store - 1 else: lo = store + 1 raise ValueError("k out of range") # 示例 data = [3, 1, 4, 1, 5, 9, 2, 6] print(quick_select(data, 0)) # 1（最小值） print(quick_select(data, 3)) # 3（第4小，0-based下标3）

这段Python代码和前面的C++版本结构完全对应，唯一区别是Python里切片和交换写起来更省事。有个小细节：arr = nums[:]做了一次浅拷贝，占O(n)额外空间。如果你确定调用方不关心原数组，把这一行去掉、直接用nums，能省一次拷贝，对超大数组来说这点空间也值得省。

关于Python还有一个实用建议。如果你的数据是数值型并且用了NumPy，遇到求中位数或分位数的场景，直接调numpy.median或numpy.percentile就行，它们底层用的就是类似快速选择的introselect算法，比你手写更稳更快。手写版本主要用在需要理解原理、或者要自定义划分规则的场合。

6. 我在实际项目里踩坑之后的几点体会

说点代码之外的东西。这个算法我最早是在准备信奥和数据结构与算法课程时学的，那时候只会背模板，觉得能写出来就万事大吉。真正到了工程里才发现，会写和写对之间隔着一条河。

第一点是随机化的重要性被大大低估了。我刚开始给日志系统写P99统计时，为了"简单"用了固定基准，结果上线后偶尔出现监控图表卡顿几十秒的情况，排查半天才定位到是某些时段的日志恰好按时间戳有序，touch了最坏情况。加上随机基准之后，抖动彻底消失。所以别嫌随机化多写两行，它买的是稳定性。

第二点是别迷信理论复杂度，要相信实测。BFPRT的最坏O(n)听起来很美，但在我那台机器上处理千万级随机数据时，它比随机快速选择慢了将近三倍。理论复杂度描述的是增长趋势，常数因子才是日常运行的体感。做选型时，拿真实数据跑基准测试，比对着大O符号拍脑袋靠谱得多。

第三点是把这类选择问题看成一个通用工具。学会找第k小之后，你会发现中位数、分位数、Top-K、甚至求第k大的问题（把比较符号反过来即可）都是它的变体。我在处理推荐系统候选打分、报表统计、异常值检测时反复用到它，一套思路打通好几类需求。与其死记硬背每个具体问题的解法，不如把快速选择这道题吃透，把分治和减治的思想刻进脑子里，以后遇到新的选择类问题，自然就知道该怎么往这个框架上套了。