第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[p1..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小就传k0表示最小值k1表示第二小依此类推即第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(vectorint a, int lo, int hi) { uniform_int_distributionint 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它是C11之后推荐的高质量随机数引擎比古老的rand()分布均匀得多做随机化算法时别再用rand()凑合。uniform_int_distribution保证区间内每个下标被选中的概率相等不会因为取模运算引入偏斜。至于swap(a[dist(rng)], a[hi])这一步是把随机基准藏到末尾让后面的划分逻辑只认末尾元素简化代码结构。3.3 递归主体与边界处理划分函数写好之后主体逻辑就顺理成章了。因为每轮只往一边递归我们可以直接把递归改成迭代省掉函数调用栈的开销// 返回 a[lo..hi] 中第 k 小k 为 0-based 全局下标 int quickSelect(vectorint 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(vectorint 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。如果你把k2直接传进去当全局下标会返回下标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永远不动划分结束返回ilo也就是说每次划分只能把区间的左端点确定下来区间长度从n缩到n-1复杂度直接退化成O(n²)。一百万个元素跑O(n²)那就是实打实的灾难。根治办法是改用三路划分也叫荷兰国旗问题划分把区间分成三块小于基准、等于基准、大于基准。等于基准的那一整块可以一次性确定位置彻底避免重复元素被反复划分。实现如下// 三路划分返回 {等于区的左端, 等于区的右端} pairint,int partition3(vectorint a, int lo, int hi) { uniform_int_distributionint 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(vectorint 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 常见问题速查表我把这些年调试快速选择时遇到的高频问题整理成一张表方便你按症状对号入座。症状可能原因排查与修复结果总是差一位k的起始约定不一致入口统一k - 1或改用0-based程序死循环卡死区间收缩漏了p±1检查hi p-1和lo p1有序数据上极慢固定基准导致退化换成随机基准或三数取中全重复数据上极慢Lomuto划分退化换三路划分偶尔返回错误值划分函数基准归位有误打印每轮p和区间验证大数组程序崩溃递归版栈溢出改成迭代版结果不稳定多次运行不同随机化未固定种子或存在越界固定种子复现检查边界注意调试随机化算法时一定要先固定随机种子让每次运行走同一条路径否则你会在这次对那次错的幻觉里耗掉一整天。等逻辑验证正确后再换回真随机种子。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快速选择期望O(n)无额外空间反复求不同k、数据动态增长小顶堆维护Top-K增量O(log 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大的问题把比较符号反过来即可都是它的变体。我在处理推荐系统候选打分、报表统计、异常值检测时反复用到它一套思路打通好几类需求。与其死记硬背每个具体问题的解法不如把快速选择这道题吃透把分治和减治的思想刻进脑子里以后遇到新的选择类问题自然就知道该怎么往这个框架上套了。