如果只允许用一个词概括我在算法这条路上最晚才真正想明白的道理我会选次序。分而治之这四个字谁都会解释——拆成子问题、递归解决、合并结果。可同一个问题先处理哪个子问题、决定往哪一侧继续深入这些次序上的差别能把复杂度差出一个数量级。这篇次序选择要聊的正是分治思想里一个非常经典的问题在一个无序数组里找出第 K 小的元素也就是按数值次序排在第 K 位的那个数。这个问题乍看简单排序后按下标取就行。但多问一句就很有意思我们真的有必要把十万个元素全部排好序才能知道第 500 个最小的是谁吗这个问题能把人从全排序的惯性思维里拽出来也正好引出分而治之的一个特殊形态——只分一支、只治一半的减治思想。不管你是刚开始刷算法题的初学者还是已经在写生产代码的工程师这篇文章都值得花几分钟读一遍它讲的不是某个偏门技巧而是一条贯穿二分查找、快速选择、TopK 问题的通用主线。1. 选择问题一个排序都能解但值得较真的题目先给出形式化描述给定长度为 n 的数组 A 和一个下标 k0 ≤ k n要求在无序数组中找出按从小到大次序排在第 k1 位的元素。这个排在第几位就是次序的含义——我们不关心元素的具体值分布只关心它在全局顺序中的名次。典型场景遍地都是统计一批请求延迟的中位数k n/2、从十万条搜索词里挑出热度第 300 名、计算成绩分布的 30 百分位线。这些问题的本质都是同一个给定一个次序位置找出对应的元素。最朴素的做法是排序。C 里 sort 一下取 A[k]Python 里sorted(A)[k]一行代码就结束了。排序本身当然没有错但这里藏着一个容易被忽略的浪费排序会把所有元素的位置关系全部理顺而我们只想要其中一个位置。打个比方这就好比你只是想从一堆人里找出个子第二高的那位却让整个队伍按身高从头到尾排了一遍。排序在这个问题上的代价是 O(n log n) 次比较但其中绝大多数比较结果和最终答案没有任何关系。那为什么 O(n log n) 不够好当数据量只有几百几千时差别确实无所谓可数据量一旦上到几百万、几千万log n 这个因子就变成了实打实的成本。一千万个元素排序大约需要两亿多次比较而线性算法只需要约一千万次。在实时推荐、广告排序、中间件监控这类对延迟敏感的场景里这个差距足够让一个接口从勉强可用变成需要扩容。所以线性时间的次序选择不是炫技而是硬需求。顺着这个诉求再回头看分而治之会发现一个关键点分治的治阶段未必一定要把拆出来的子问题全部解决。如果我们能通过一次划分搞清楚答案落在哪一侧那么另一侧就完全可以丢弃。这是一种偏科的分治——只选需要的那条分支继续深入。二分查找是这么干的接下来要讲的 QuickSelect 也是这么干的。这里次序的第二层含义就出来了不仅元素有次序我们对子问题的处理也有次序先确定哪一侧有答案再决定往哪边走。这也是面试官们喜欢考这个题的原因。它不是考你会不会背快排而是考你对分治本质的理解什么时候必须两边递归什么时候剪掉一侧还保证正确。很多人能把快排默写下来却说不清快排和快速选择的复杂度为什么会差一个 log n。搞明白这个差别比记住十个模板题都有价值。2. 核心算法 QuickSelect划分一次只深入一侧2.1 一次划分到底做了什么QuickSelect 的地基是划分partition。划分操作选一个基准值 pivot把数组原地重排成三段小于等于 pivot 的靠左pivot 挪到中间某个位置大于 pivot 的靠右。划分完成后最关键的性质是pivot 最终停留的下标就是它在这个数组全部排好序时应该待的位置。这个性质看起来平平无奇却是整个算法的定海神针——只要 pivot 落定的下标恰好等于 k那这个值就是第 k1 小的元素直接返回即可。实现划分的方式有很多我最常用的是单游标法基准取区间最右元素从左往右扫一遍凡是遇到小于等于 pivot 的元素就把它换到左区边界处最后再把 pivot 换到左区边界。整个过程中左半区始终维护着已经确认不大于 pivot的元素集合右半区则是尚未检查的元素。代码如下def partition(arr, left, right): pivot arr[right] i left for j in range(left, right): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] return i这段单游标划分的时间复杂度是 O(n)额外空间是 O(1)因为它只用了一个额外的交换动作没有申请任何辅助数组。这里有一个细节值得注意比较用的是 而不是 。这个选择在普通快速排序里影响不大但在 QuickSelect 里会直接影响递归方向的正确性尤其是在重复元素很多的数组上如果改成 小于等于区的边界会变得难以界定pivot 的落点位置也可能出现歧义最终导致返回的元素不是真正排在第 k 位的值。具体原因我留到第 5 节专门展开。2.2 递归只追一个方向有了划分函数QuickSelect 的主流程就很简单划分一次比较 k 和 pivot 落点的关系决定递归哪一侧。import random def quickselect(arr, k): if not arr or k 0 or k len(arr): raise ValueError(invalid k) return _quickselect(arr, 0, len(arr) - 1, k) def _quickselect(arr, left, right, k): if left right: return arr[left] # 随机化把随机选中的元素换到最右侧再划分 rand_idx random.randint(left, right) arr[rand_idx], arr[right] arr[right], arr[rand_idx] pivot_idx partition(arr, left, right) if k pivot_idx: return arr[k] elif k pivot_idx: return _quickselect(arr, left, pivot_idx - 1, k) else: return _quickselect(arr, pivot_idx 1, right, k)整个算法的灵魂在最后三行判断上。如果 k 小于 pivot 落点下标说明答案在左区右区整块丢弃如果 k 大于 pivot 落点下标说明答案在右区左区整块丢弃如果相等直接返回。每次递归都会丢掉一大块确定无用的区间规模缩减非常激进。用一个简单例子走一遍arr [7, 3, 9, 2, 8, 1, 5]找第 3 小的元素即 k 2。第一轮划分选择 5 作为基准划分后数组变成[3, 2, 1, 5, 8, 9, 7]5 落在下标 3。k 2 小于 3所以答案一定在左半部分[3, 2, 1]里。第二轮划分选 1 作基准划分后得到[1, 2, 3]1 落在下标 0。k 2 大于 0于是把 k 更新为2 - 0 - 1 1去右半部分[2, 3]里找。第三轮选 3 作基准落点下标恰好等于更新后的 k 1返回 3。整个数组排序后的第 3 小元素确实是 3。这种只追一侧的分治在算法理论里有个专门的名字叫减治decrease and conquer也叫剪枝式分治。它和传统分治的区别在于普通分治要把每个子问题的解都凑齐才能合并出原问题的答案而减治只需沿着一条路径往下走其他分支全部剪掉。二分查找是最古老的减治例子QuickSelect 是它在无序数组场景下的推广。2.3 和快速排序的分道扬镳快排和快速选择经常被放在一起比因为它们都用划分函数代码前半段几乎一模一样。区别在于递归之后快排对划分出来的左右两个区间都要递归因为它的目标是让所有元素各归其位快速选择只递归包含答案的那一侧因为它的目标仅仅是确定一个位置的值。这个差异直接反映在复杂度上。快排平均情况递推 T(n) 2T(n/2) O(n)解出 O(n log n)快速选择平均情况递推 T(n) T(n/2) O(n)解出 O(n)。一个 log n 的差距根源在于快排买的是全序快速选择只买单点信息。工程上的启发也很直白先想清楚你到底需要多少信息再决定投入多少计算。这是比任何代码都重要的方法论。3. 期望 O(n) 是怎么来的以及最坏情况为什么很糟3.1 平均情况下的递推假设基准选得不错划分后 pivot 大致落在区间中点附近。那么快速选择第一次划分花 O(n)第二次处理规模约 n/2第三次约 n/4以此类推。总时间就是等比级数 n n/2 n/4 ...收敛到 2n也就是 O(n)。很多人第一次看到这个推导会觉得太巧了每次只剩下一半但另一半不是凭空消失而是被证明不可能包含答案后合法地丢弃了所以每一层的开销都在按比例收缩。更严谨的写法是设 T(n) 表示期望时间递推式写作 T(n) T(n/2) O(n)。这里的 T(n/2) 是平均意义下的子问题规模严格的概率推导需要把基准落在每个位置的可能性都考虑进去结论不变。这是整个算法最漂亮的数学点看似每次只消掉一半但这一半是确定含答案的一半所以另一半根本不需要再花钱。3.2 最坏情况有序数组的陷阱如果基准固定选最右元素而数组恰好已经有序会发生什么划分后 pivot 落在最右端左边是 n - 1 个元素右边是 0 个元素。递归规模从 n 变成 n - 1于是递推式变成 T(n) T(n - 1) O(n)解出 O(n²)。一个为了高效选第 K 小元素而生的算法在数据恰好有序时反而退化到冒泡水平这个讽刺是很多人的第一堂复杂度实践课。注意固定取最右元素作为基准的 QuickSelect绝不能在有序或近似有序的数据上直接使用。真实工程里这种看起来随机、其实有序的数据比比皆是日志时间戳天然递增、数据库按主键返回的记录有序、监控数据按时间序列排列。如果你写成固定取最右基准又碰巧把这种数据喂进去线上性能会瞬间垮掉。所以固定基准的 QuickSelect 只能用于教学不能直接上线。3.3 随机化让坏情况几乎不发生解决方案是随机选择基准。代码里的做法是先从当前区间随机挑一个下标把该位置的元素和最右元素交换再走标准的单游标划分。这样一来最坏情况的输入依然存在——每次随机都命中当前区间的最值——但它与数据的初始形态彻底解绑变成了独立的小概率事件。连续若干次都抽到最值的概率按指数级衰减实际运行中可以认为不会发生。如果你对随机源有顾虑或者不想依赖语言自带的随机数也可以用三数取中取区间首、中、尾三个元素的中位数作为基准。它在快排里非常流行在快速选择里效果同样不错能平滑大部分退化场景。不过要说彻底的随机性还是直接随机选下标更省事。这一点完全取决于你对概率保证的接受程度。4. BFPRT 算法让最坏情况也稳定在 O(n)4.1 为什么是五元素一组随机化再好也只是把最坏情况变成小概率事件。某些场景不允许存在几乎比如实时竞价、风控拦截、在线计费延迟超出预算就是事故你不能跟老板解释这次是随机数运气不好。这时候就需要一个确定性算法让最坏情况也严格是 O(n)。这就是 BFPRT通常称为中位数的中位数Median of Medians算法。BFPRT 的核心思路是给快速选择换一个质量极高的基准不再依赖随机而是靠计算得到。步骤分三步第一把数组每 5 个元素分成一组最后不足 5 个的单独成组第二每组内部排序取每组的中位数第三递归地对这些组中位数求中位数用这个结果作为全局 pivot。为什么是 5 而不是 3 或 73 个一组能得到类似的复杂度结论但常数和递归深度不划算7 个一组会减少递归层数却让每组排序的开销变大。5 正好站在一个平衡点上每组排序成本很低5 个元素排序最多十几次比较又能保证后续的规模收缩率达到理论需要的水平。工程界最终普遍采用 5是一个在数学和实现之间反复权衡后沉淀下来的经验选择。4.2 复杂度证明的直觉假设数组有 n 个元素分成约 n/5 组每组取中位数再对这些中位数递归取中位数作为 pivot。关键性质是至少有一半的组它们的组中位数小于等于全局 pivot。每个这样的组有 5 个元素组内排序后至少前 3 个都不大于组中位数也就都不大于全局 pivot。因此至少有约 3 × (n/5) / 2 3n/10 个元素小于等于 pivot。同理至少有 3n/10 个元素大于等于 pivot。这意味着无论 pivot 最后落在哪左右两侧都至少排除了 30% 的元素。于是递推式变为 T(n) ≤ T(n/5) T(7n/10) O(n)第一项是递归求中位数的中位数第二项是最坏情况下依旧要处理的剩余区间第三项是分组排序和划分的开销。解这个递推式两种子问题的规模加起来是 n/5 7n/10 9n/10小于 n所以最终复杂度被压回 O(n)。这个证明的直觉就是找基准这件事本身就带来了 10% 的规模收缩。4.3 代码与使用建议实现上BFPRT 常见的写法是利用三块划分严格小于 pivot、等于 pivot、严格大于 pivot。def bfprt(arr, k): if len(arr) 5: return sorted(arr)[k] medians [] for i in range(0, len(arr), 5): group arr[i:i5] group.sort() medians.append(group[len(group) // 2]) pivot bfprt(medians, len(medians) // 2) left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] if k len(left): return bfprt(left, k) elif k len(left) len(mid): return pivot else: return bfprt(right, k - len(left) - len(mid))三块划分对重复元素处理非常友好等于区直接命中返回不用纠结小于等于边界。代价是每次递归需要复制子数组空间 O(n)。如果你想省内存可以改成原地版本但代码可读性会差很多。我个人的习惯是讲原理和面试时用原地版思路工程落地优先可读性这种非原地版完全够用。实际使用时还得泼一盆冷水BFPRT 的常数很大几十万以内的小数据上通常跑不过随机化 QuickSelect。分组排序、递归取中位数、三块筛选每一步都有开销。它真正的用武之地是数据量巨大、又有硬性的最坏情况保证需求。普通业务里随机化配合合理的工程防护性价比高得多。5. 实战中的边界情况与翻车现场5.1 K 的下标语义是第一大坑选第 K 小K 到底是 0 起始还是 1 起始这个看起来无关紧要的约定是实际开发里最常踩的坑。我见过不止一次事故外层函数用第 i 小1 起始对外暴露内部递归按 0 起始下标实现两边没做转换结果线上数据每个月都整体偏移一位。这类 bug 隐蔽在正确和错误之间单看边界用例很难发现。提示把第几小1 起始和数组下标0 起始在入口处显式转换能避免一整类隐蔽 bug。我的建议是对外接口统一使用 1 起始的第几小语义方便调用方理解内部递归统一使用 0 起始数组下标方便和 partition 落点对齐。两层之间在入口处做一次显式转换并在文档里写明传入 k1 表示最小值klen(arr) 表示最大值。宁可多写一行转换也不要在模糊约定上赌运气。5.2 重复元素与全相等数组重复元素是划分实现的照妖镜。如果你在划分时使用 而不是 小于等于区的边界会变得不可控pivot 落点和递归方向都可能出错。使用 时重复元素会被分到左区pivot 的落点依然是一个有意义的边界快速选择的正确性可以保持。比重复元素更极端的是全相等数组。这种情况下小于区为空、等于区占满。非原地版 BFPRT 的三块划分对这种场景非常友好等于区直接一击命中原地版 QuickSelect 也能正确返回因为每次划分后 pivot 的位置始终有效。如果你发现写出来的算法在全相等数组上行为异常优先检查划分函数里的比较符号。5.3 递归深度、空数组与迭代改写快速选择最坏情况递归深度是 O(n)随机化虽然让这个概率极低但 Python 默认递归深度限制通常 1000还是可能在某些极端随机种子下被碰到。真要彻底放心可以改成迭代版本用 while 循环模拟递归每次确定 pivot 落点后把 left 或 right 边界收缩到一侧不产生新的函数调用。这样既不担心递归深度也让代码更贴近 C/C 里常见的手写版本。def quickselect_iterative(arr, k): left, right 0, len(arr) - 1 while left right: if left right: return arr[left] rand_idx random.randint(left, right) arr[rand_idx], arr[right] arr[right], arr[rand_idx] pivot_idx partition(arr, left, right) if k pivot_idx: return arr[k] elif k pivot_idx: right pivot_idx - 1 else: left pivot_idx 1空数组和越界 K 属于必须提前防御的输入。我在公共入口里加了一个校验K 不在 [0, n) 范围内直接抛异常。别觉得这是小题大做——在数据管道里跑上一个月什么脏数据都可能出现算法入口的防御就是第一道护城河。5.4 一段顺手可用的验证脚本写完快速选择先别急着计入线上用暴力对拍脚本跑一遍随机生成数组、随机生成长度、随机生成 K把快速选择的结果和排序取下标的结果逐一比对。几千轮下来负数、正数、重复值、全相等、单元素数组这些角落基本都能覆盖到。对拍通过后再谈优化和上线这一步成本极低却能省掉未来无数个排查 bug 的深夜。def brute(arr, k): return sorted(arr)[k] for _ in range(2000): arr [random.randint(-100, 100) for _ in range(random.randint(1, 100))] k random.randint(0, len(arr) - 1) assert quickselect(arr[:], k) brute(arr, k)我习惯把这段对拍脚本保留在项目的测试目录里以后改任何排序相关代码都会顺手跑一遍。算法题可以靠脑内验证工程代码必须靠测试说话。两者之间隔着一条明确的分界线。6. 次序选择之外的延伸思考6.1 由第K小到中位数、TopK第 K 小变中位数只需要令 k (n - 1) // 2变 TopK则找第 n - k 1 小把 TopK 的边界值切出来剩下的自然就是最大的 K 个。排行榜、异常检测、p99 延迟监控本质上都是选择问题。这些场景的共性在于你关心的不是全体元素的完整顺序而只是某个或某几个次序位置上的值。抓住这一点就能用同一个线性算法覆盖一大批应用。6.2 二分查找是同一招吗二分查找其实也是次序选择的一种特殊形式它在一个已经有序的数组上通过折半不断缩小候选区间最终定位到目标值所在的次序位置。区别只在于有序数组天生知道中点的意义而无序数组必须先花 O(n) 用划分来购买中点两侧的次序信息。这么一看二分查找、快速选择都是同一种思想的实例每次迭代都做一次划分然后只保留包含答案的那一侧。这个统一视角非常值得带进脑海。以后再遇到在 XX 里找第 Y 个 XX的问题第一反应不应该是套模板而是先问候选区间是什么划分代价是什么丢弃哪一侧是安全的三个问题想清楚算法自然就出来了。6.3 分治中先处理哪一侧的决策价值回到题目本身。次序选择这四个字表面上是说选择问题深层其实是分治里的次序决策先递归哪一侧、哪一侧可以安全丢弃、什么条件下可以提前终止。现实工程里很多分治算法就是因为没有正视这个次序习惯性地两个分支都递归复杂度凭空多出一个 log n分支更多的场景更是直接膨胀成指数级。我自己的习惯是拿到一个分治问题先画递归树标出每个节点的规模再逐个检查哪些子树可以剪枝。对选择类问题答案通常非常漂亮——永远存在一条只走一侧的路径把复杂度压下一个量级。这是我在分而治之这个系列里最想传达的一课分治的价值不只是拆分更在于拆分之后对方向的选择。最后分享一个小技巧实现快速选择时把划分函数单独抽出来并在注释里写明返回 pivot 的最终下标。这个约定让我后来接 BFPRT、改迭代版本、移植到其他语言时都省了大量脑力。边界和语义这类约定越早固化越好未来的你会感谢现在的自己。
限制的工程实践指南)
