1. 为什么第215题是“背了又忘”的高频题如果你刷过一段时间的算法题大概率对这道题有印象给定一个整数数组nums和一个整数k要求返回数组中第 k 个最大的元素。乍一看这就是“排序然后取下标”的事但 Leetcode 215 之所以被反复拿出来讲恰恰是因为它考察的不是你会不会调排序接口而是你有没有理解快速排序内部的分治本质。我第一次做这道题时也走了弯路直接sort(nums.begin(), nums.end())然后返回nums[nums.size() - k]。提交能过但总觉得这事没完。因为面试官大概率会追问一句如果数组特别大内存放不下全量排序或者数据是流式的只允许遍历一次你还能怎么做这道题的真正价值在于引出两个经典思路——堆优先队列和快速选择Quick Select其中快速选择就是“单边分治版的快速排序”理解了它你对快速排序的理解才算真正上了一个台阶。这篇文章我准备从零开始拆解先讲清楚第 215 题的目标与边界然后进入快速排序的分治模型说明快速选择为什么能平均 O(n) 完成查找再给出完整可运行的 C 实现最后专门聊一聊那些坑——尤其是基准值选择和退化问题。全程用 C 代码说话尽量还原我在实际做题和模拟面试时的思考过程。2. 先厘清题目目标第 k 大到底对应哪个位置2.1 从“排序后取下标”的直觉说起题目给的是“第 k 个最大的元素”。注意这个表述和“第 k 个最小”容易混淆。一个简单的换算关系是如果要找第 k 大其实就是升序排序后从右往左数第 k 个也就是下标n - k的元素。我记得自己第一次提交时写的是sort(nums.begin(), nums.end()); return nums[nums.size() - k];输出正确但后来面试官问我“为什么是n - k”时我愣了一下才反应过来。其实想清楚就很简单数组升序后最大的元素在n - 1第二大的在n - 2依此类推第 k 大的就是n - k。这里千万不能把“第 k 大”当成“从左边数的第 k 个”那是第 k 小的位置。2.2 暴力解法的复杂度边界排序法的时间复杂度是 O(n log n)空间复杂度取决于排序实现std::sort通常是 O(log n) 栈空间。对于 Leetcode 215 的常规数据规模来说这当然能过。但如果你在面试中只给出排序解法往往会被追问“能不能优化”因为题目真正想要的并不是全量排序而是一个能更快定位到目标的方案。同理用小顶堆维护大小为 k 的窗口遍历完数组后堆顶就是第 k 大复杂度是 O(n log k)。这种方案适合数据量极大、无法一次性全部载入内存的场景因为只需要流式处理每个元素。它的空间复杂度是 O(k)当 k 远小于 n 时非常实用。本文重点讨论的是快速选择方案它在时间均摊上更优而且它从头到尾都在复用快速排序的partition过程——理解了它等于同时复习了快速排序。3. 快速排序的分治模型快速选择就是它的“单边剪枝版”3.1 partition 的本质是什么要讲快速选择必须先讲 partition。快速排序的核心动作不是“交换”而是“选定一个基准元素然后通过一系列交换把数组分成两部分左边都不大于基准值右边都不小于基准值”。在 partition 结束的这一刻基准值所在的位置就是它在最终有序序列中的位置。举个例子。假设数组是[3, 1, 4, 1, 5, 9, 2, 6]我们随便选一个基准比如取最后一个元素 6partition 完毕后6 会移动到一个位置pos使得[0, pos)区间内的元素全部 6(pos, n-1]区间内的元素全部 6。不管后续怎么继续排序6 永远停在这个位置上了。这就是快速排序“每次确定一个元素的最终位置”的核心机制。标准循环不变量是这样的维护一个区间[0, i]表示已处理的小于等于基准的部分一个游标j从区间的左边界往右扫描遇到小于等于基准的元素就把它交换到前面来。我在 C 里最常用的是“挖坑填数法”或“交换法”写法不同但本质一致。快速选择算法用的 partition 不仅负责把数组划分开更关键的是它返回了基准的最终下标。3.2 为什么快速选择只需要递归一侧普通快速排序在 partition 之后要对基准左边和右边两个子区间分别递归排序时间复杂度期望是 O(n log n)。但第 215 题只要求找第 k 大这意味着我们只关心目标下标target n - k位置的元素其他位置的顺序根本不需要完全排好。于是快速选择就来了做一次 partition 后拿到基准的最终位置pos。如果pos target那基准值恰好就是我们要找的第 k 大元素直接返回如果pos target说明目标在右半边只需要递归处理[pos 1, right]如果pos target说明目标在左半边只需要递归处理[left, pos - 1]。这个“只走一侧”就是剪枝。普通快排要递归两侧而快速选择每次递归只处理一侧从直观上就比快排快。我最初觉得这只是“少了一半的工作量”但后来算复杂度才发现它带来的收益是巨大的——均摊从 O(n log n) 直接降到了 O(n)。3.3 均摊 O(n) 的几何级数直观证明这里用一个很感性的方式推导复杂度方便记忆。假设 partition 非常理想每次都能把区间大致对半分。第一次处理的规模是 n第二次大概是 n/2第三次是 n/4……总工作量近似为 n n/2 n/4 ... 2n所以期望复杂度是 O(n)。这个推导虽然省略了细节但能帮我们快速理解为什么“每次只处理一半”比“每次处理完整的两半”划算。完整快排的工作量模型是每层都处理 n 个元素一共 log n 层所以是 O(n log n)而快速选择每层处理 n/2^k 个元素呈几何级数缩减加起来就是收敛的 O(n)。注意这里的 O(n) 是“平均期望复杂度”不是严格的最坏情况。如果 partition 每次选择的基准都恰好把数组分成极度不平衡的两部分比如每次都取到最小值或最大值那递归深度会变成 n复杂度会退化成 O(n^2)。这个退化问题我会在第 6 部分专门展开也是面试官最喜欢追问的细节点。4. C 实现快速选择的完整代码与逐步推演4.1 最朴素的版本固定取最右元素为基准我先把最快能跑的版本写出来代码尽量贴近我平时做题的风格注释会很详细。#include vector #include algorithm using namespace std; class Solution { public: int findKthLargest(vectorint nums, int k) { int n nums.size(); int target n - k; // 第 k 大 升序后的第 n-k 个位置 int left 0, right n - 1; while (true) { int pos partition(nums, left, right); if (pos target) { return nums[pos]; } else if (pos target) { left pos 1; } else { right pos - 1; } } } private: int partition(vectorint nums, int left, int right) { int pivot nums[right]; int i left; // i 指向当前已确认 pivot 的区间末尾的下一个位置 for (int j left; j right; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[right]); return i; } };这里的partition是经典的“循环内交换”写法i左边全是小于等于 pivot 的元素j负责向右扫描发现符合条件的元素就换到i的位置然后i后移。扫描结束之后把 pivot 从最右边换到i的位置这样 pivot 就落在了它最终应该在的位置上。findKthLargest用的是循环而非递归因为每一轮 partition 之后目标区间的边界就更新了循环改写非常自然。这种写法也避免了递归栈溢出的隐患实际跑 Leetcode 大数组时更安全。4.2 递归版本的写法对比我有时候在面试中也会直接写递归版因为它更贴近快速排序的思考方式。贴上递归版的实现int quickSelect(vectorint nums, int left, int right, int target) { int pos partition(nums, left, right); if (pos target) return nums[pos]; if (pos target) return quickSelect(nums, pos 1, right, target); return quickSelect(nums, left, pos - 1, target); } int findKthLargestRecursive(vectorint nums, int k) { int n nums.size(); return quickSelect(nums, 0, n - 1, n - k); }递归版和循环版本质上没有区别都是一个“一直收敛区间直到找到目标位置”的过程。面试中我会优先写递归版因为代码更紧凑也更容易向面试官解释思路但心里知道循环版是迭代版本连递归栈都不需要遇到极端数据更稳。4.3 手动走一遍 partition看清楚下标怎么变光看代码可能还不够直观我手动走一个例子。数组[3, 2, 1, 5, 6, 4]目标k 2所以target 6 - 2 4也就是要找升序后下标 4 的元素。第一轮 partitionleft0right5pivot 取nums[5]4。扫描过程如下初始i0j从 0 开始。j0nums[0]3 4swap(nums[0], nums[0])i 变 1。j1nums[1]2 4swap(nums[1], nums[1])i 变 2。j2nums[2]1 4swap(nums[2], nums[2])i 变 3。j3nums[3]5 4跳过。j4nums[4]6 4跳过。扫描结束swap(nums[3], nums[5])数组变成[3, 2, 1, 4, 6, 5]返回 pos3。现在pos3 target4说明第 4 位置的元素在右半边[4, 5]。下一轮只处理[4, 5]区间数组是[3, 2, 1, 4, 6, 5]left4, right5pivot 取nums[5]5。扫描中nums[4]6 5跳过结束后 swap(nums[4], nums[5])得到[3, 2, 1, 4, 5, 6]pos4。刚好pos target返回nums[4]5。手动走一遍你就能很清楚地看到第二轮只处理了两个元素整个数组左侧的[3, 2, 1, 4]完全没动。这就是“剪枝”的直观体现。5. 基准值选择的工程化改进随机化与三数取中5.1 固定取最右元素的劣化场景前面的朴素版取nums[right]作为基准这在某些特殊输入上会非常吃亏。假设输入数组已经是一个升序数组比如[1, 2, 3, 4, 5, 6]每次取最右元素作为 pivot它恰好是整个区间的最大值。这样 partition 完成后pivot 被放到最右端左半部分几乎包含所有其他元素每次递归几乎只能排除一个元素复杂度直接退化到 O(n^2)。这种情况在 Leetcode 的测试数据中确实存在例如某些精心构造的例子专门让你“用最右基准”时超时。这也是我在实际提交中碰到过一次超时后真正重视起来的问题——光会写朴素版是不够的必须在基准选择上做文章。5.2 随机化基准最简单的工程解法最常用且最容易实现的优化就是随机选择基准。方法是生成一个[left, right]范围内的随机下标然后把该位置的元素和nums[right]交换之后的逻辑完全不变。这样任何固定的数据分布都不可能稳定地让 partition 每次都取到最坏情况期望复杂度就被“打散”到了 O(n log n)快排或 O(n)快选。C 实现时可以用random库也可以直接用rand()但要注意不同编译器下rand()的可移植性。我一般用std::mt19937配合uniform_int_distribution这样随机性更均匀向量子化的担心也少一些。#include random int randomPartition(vectorint nums, int left, int right) { static mt19937 gen(random_device{}()); uniform_int_distributionint dist(left, right); int pivotIndex dist(gen); swap(nums[pivotIndex], nums[right]); return partition(nums, left, right); }5.3 三数取中不依赖随机数也有效的策略如果你不想依赖随机数生成器另一个经典方案是三数取中median-of-three取nums[left]、nums[mid]、nums[right]三者的中间值作为基准。这个策略对近似有序的数据特别有效因为它避免了取到最大值或最小值的极端情况。int medianOfThree(vectorint nums, int left, int right) { int mid left (right - left) / 2; if (nums[left] nums[mid]) swap(nums[left], nums[mid]); if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[mid] nums[right]) swap(nums[mid], nums[right]); // 此时 nums[mid] 是三者中位数 swap(nums[mid], nums[right]); return partition(nums, left, right); }实际上很多 C 标准库的排序实现都会综合使用多种优化策略。我们在刷题层面用随机化就足以应对 Leetcode 的测试了。不过三数取中在某些嵌入式或线上环境不允许引入随机数中更实用值得掌握。5.4 双指针交换法 partition 的另一种写法除了前面那种“快慢指针”式的 partition还有一种常见写法是双指针从两端向中间走左指针找大于 pivot 的元素右指针找小于 pivot 的元素找到后交换。这种写法在某些场景下交换次数更少读起来也更符合“左右开弓”的直觉。int partitionTwoPointer(vectorint nums, int left, int right) { int pivot nums[left]; while (left right) { while (left right nums[right] pivot) --right; nums[left] nums[right]; while (left right nums[left] pivot) left; nums[left] nums[right]; // 你可能会觉得这行有 bug仔细看这是挖坑填数的核心 } // 实际标准写法的最后一步是 nums[left] pivot nums[left] pivot; return left; }等等上面这段我故意留了个小坑因为挖坑填数法很容易写错。正确版本应该是先用一个变量保存 pivot然后右指针找到小于 pivot 的数字填到左指针的位置左指针找到大于 pivot 的数字填到右指针的位置最后左右指针相遇时把 pivot 填回去。我平时更推荐快慢指针的写法因为它不容易出错、更好调试。双指针写法适合你已经对 partition 非常熟练之后再去掌握不然容易把自己绕晕。6. 那些年我踩过的坑重复元素、边界条件和复杂度6.1 重复元素会造成死循环吗一个常见问题是如果数组里大量重复元素比如[2, 2, 2, 2, 2]partition 会不会陷入死循环答案是如果你用的是“小于等于 pivot 换到前面”的写法重复元素会被均匀地分布在 pivot 两侧partition 照样能正常返回一个位置。我的实现里用的是nums[j] pivot这个条件所以重复元素不会导致死循环。但如果你的 partition 写成“只有小于 pivot 才交换等于不交换”重复元素就可能全部堆在 pivot 一侧导致区间划分极度不平衡。所以在实现中要留意这个细节当 pivot 存在大量重复值时等值元素必须能被分配到两侧而不是总停留在同一侧。6.2left right还是left right循环版快速选择的边界条件是很多人容易写错的地方。我的习惯是初始区间是[0, n-1]只要left right就继续循环在left right的情况下理论上不该出现因为一定存在一个target位置在[0, n-1]范围内循环迟早会收敛到pos target但如果你写的是while (left right)那可能在left right时遗漏最后的检查。稳妥起见我推荐用while (true)并在内部区分三种情况这样最直观也不会出边界错误。递归版的边界条件同样如此如果pos target就处理右边如果pos target就处理左边递归调用一定能保证最终收敛因为区间每次都在缩小。6.3 最坏情况 O(n^2) 的典型输入我前面提到升序数组会绑架固定取末尾 pivot 的写法这里再多说一句不仅是升序降序数组取末尾元素同样会退化成 O(n^2)。如果排序算法的面试题考察你“是否了解快排的弱点”这类退化输入几乎是必问的。随机化可以极大降低最坏情况的概率但理论上随机化也不能完全消除最坏情况。工程上还有一种更彻底的思路BFPRT中位数的中位数算法它通过精心挑选 pivot 保证严格 O(n) 最坏复杂度但实现复杂度高常数项也大在刷题场景很少用。知道这个概念就足够了。6.4 实测中的一次超时经历我自己第一次提交第 215 题时用的是固定最右 pivot 的朴素版结果在一个大数组用例上直接超时。当时的第一反应是“怎么可能 O(n) 也会超时”后来一分析才发现那个用例很可能是特意构造的近乎有序的数据让朴素版退化成了 O(n^2)。换成随机化版本后提交立刻就过了。那次之后我在所有涉及快排/快选的题目里都会默认使用随机基准不再纠结“是不是这个用例没那么坏”。这个教训也提醒我分析复杂度一定要考虑最坏情况不能只盯着平均情况自作多情。7. 从第 215 题延伸出去的三个思考7.1 堆方案与快速选择的对比选型除了快速选择第 215 题的另一个经典解法是小顶堆。我用一张表把两种方案的适用场景梳理一下方案时间复杂度空间复杂度适用场景排序后取下标O(n log n)O(log n)代码最短但只适合小数据小顶堆O(n log k)O(k)数据流/超大数组只需要维护前 k 个快速选择期望 O(n)最坏 O(n^2)O(log n)一次性数组追求速度内存可容纳全部数据如果数据是流式的或者 n 无限大而 k 较小堆方案是首选。如果数据已经全部在内存里且你不想引入额外 O(k) 的开销快速选择更合适。我面试时通常会先说“两种都可以”然后再根据面试官给出的约束条件选一个往下展开这比一上来就写代码更能体现思考层次。7.2 标准库函数std::nth_element的底层就是快选C 标准库提供了一个直接可用的函数std::nth_element它的语义就是把第 n 个位置上的元素放到它排序后应该在的位置左边都小于等于它右边都大于等于它——本质上就是快速选择。它的平均复杂度也是 O(n)。在允许使用标准库的工程场景中我会直接用它来替代手写快速选择因为标准库实现针对当前编译器和指令集做了很多优化性能往往比自己写的强。但作为面试准备你还是得能手写底层逻辑不然面试官问一句“nth_element怎么实现的”就直接露怯了。std::nth_element(nums.begin(), nums.begin() n - k, nums.end()); return nums[n - k];7.3 从“找第 k 大”到“找 Top K”的转化第 215 题解决了“第 k 大”的定位问题而 Top K 问题经常会要求返回前 k 个最大或最小的元素不要求这 k 个元素内部有序。此时快速选择同样适用做一次快选把target n - k的元素定位好它左侧所有元素就是前 k 个最大无序。复杂度依然是 O(n)而最简单的排序方案需要 O(n log n)。如果你要求返回的前 k 个元素必须有序那可以在快选之后对左侧区间再排一次序总复杂度 O(n k log k)这在 k 远小于 n 时比全排序划算很多。这个组合思路在真实业务中也非常常见比如从海量日志中找到最热的 k 个关键词。8. 几个亲手验证过的代码细节与建议8.1 使用swap前别忘记包含头文件因为第 215 题代码很短很多人会顺手省略头文件结果在本地编译时报错swap不是标准库函数。其实只要包含vector有些编译器会顺带把std::swap暴露出来但不保证所有环境都这样。稳妥做法是显式包含algorithm或utility这样在任何标准 C 编译器下都能跑。8.2 注意n - k下标的隐式类型问题nums.size()返回的是size_t是无符号整数k是int。如果直接写int target nums.size() - k;当nums.size()小于k时会发生无符号整数下溢变成一个巨大的正数。虽然题目保证k合法但如果你把代码内部复用到其他场景这里就是一个隐患。我习惯先转成int n nums.size();再计算避免混用无符号和有符号数。8.3 递归栈溢出不是玩笑虽然快速选择的期望递归深度是 O(log n)但在极端退化情况下深度会变成 O(n)。如果你在面试中写递归版然后面试官问“如果输入特别糟糕怎么办”随机化是答案之一但更好的预防方案是直接用循环版本。我平时给出的推荐版本就是第 4 部分的while(true)循环代码因为它没有递归栈风险也不会在极端输入下爆栈。8.4 关于“等号”写在哪里我想多说两句partition 里的比较条件nums[j] pivot和nums[j] pivot看似差别不大但影响不小。使用时等于 pivot 的元素不会通过交换进入前段导致 pivot 的等值元素全挤到某一侧遇到大量重复元素时容易让区间划分失衡。使用是最稳妥的选择这也是我推荐用的原因。如果想再优化一点可以使用类似三路快排的思路把等于 pivot 的元素单独放在中间区这样重复元素多时的性能也不会退化但代码复杂度会高不少。第 215 题用双路划分已经足够了。8.5 做题时的几个常见误区总结把第 k 大当成第 k 小直接返回nums[k]结果错误忘记把k转换成下标n - k导致始终在错误区间查找partition 写完没有把 pivot 放回最终位置导致后续区间划分错乱递归版本在left right时没有保护出现越界访问。这些错误我一个一个都犯过写这篇文章时反复对照代码检查才意识到基本都是“边界条件不清晰”和“枢轴最终位置理解不到位”这两个原因。9. 最后分享一点个人做题心得第 215 题是我很早就想透彻的一道题因为它串联了排序、分治、复杂度分析、随机化这几个非常重要的算法主题。复盘下来我觉得最值得记住的一句话是不要只背快速选择的代码要理解“为什么每次只需要递归一侧”。这个“单侧递归”的思想还能用在很多地方比如二分查找的变体、矩阵中的搜索、甚至某些分治优化问题上。如果你现在正在刷 Leetcode 备战面试我的建议是这道题至少手写三遍。第一遍直接写朴素版跑通后故意用近乎有序的大数据测试一次感受一下超时第二遍改成随机化版本对比两种写法的时间差异第三遍把循环版和递归版都写一遍确保自己能在白板上不假思索地写出来。这样三轮下来你对 partition 和复杂度模型的理解会比单纯背代码深得多。另外如果你在面试中被问到这道题除了给出解法之外可以主动提一下“堆方案适合流式数据”“随机化消除最坏依赖”“std::nth_element的底层就是快选”这三个扩展点。这会让面试官觉得你不只是会刷题而是对工程选型有真实的思考。我在模拟面试中带过几个同学能说到这一层的印象分往往明显更好。最后一个小技巧快速选择不仅能解决第 215 题还经常被用在“找中位数”“寻找第 k 小的距离对”等问题中。如果你把 partition 的代码封装成一个内部工具函数遇到这些变体题时就能直接复用省下很多调试时间。祝你能在一次次的“手动走数组”中真正把快速排序的分治直觉内化成自己的算法肌肉记忆。