企业官网建设流程全解析

刷到算法系列第二十一篇，这次把 LeetCode 上的 215 题“数组中的第 K 个最大元素”和 912 题“排序数组”放在一起讲。很多人是分开刷这两题的，但我强烈建议把它们当成一组来练。912 题考的是排序基本功，215 题则是把排序思想“削”到一半——你不需要把整个数组排好，只要找到第 K 大的那个值。先刷 912 再刷 215，你会发现后者其实就是快速排序里那个分区过程（Partition）的变体。这篇文章会把快速排序、归并排序、快速选择、堆排序四种解法全部讲透，手写代码、复杂度推演、边界条件、面试考察点都覆盖到，适合正在刷题准备面试的人，也适合想把排序基础打扎实的同学。

1. 为什么这两道题必须放在一起刷

1.1 一道排序题，一道“伪排序题”

912 题非常直接：给一个整数数组，把它升序排序。你实际写出来的解法可以有很多，快速排序、归并排序、堆排序都行，甚至直接调用系统排序函数也能过。但这道题作为算法题的价值不在“过”，而在于你能不能在不借助现成函数的情况下写出一个稳定、正确、复杂度达标的排序算法。

215 题表面上是在“找数”：找出数组中第 K 个最大的元素。很多人的第一反应是先排序，排完之后取倒数第 K 个。这个思路正确，但排序做了大量多余工作——数组里只有第 K 大的位置是你关心的，其他位置排不排好根本没影响。所以 215 题真正考察的是快速选择（Quickselect），一种“不用排完也能找到答案”的思想。

这两道题放在一起刷，逻辑就通了：912 题教你完整排一遍，215 题逼你思考“我只想知道一个位置，能不能少排一点”。后者的答案是能，而且能把平均复杂度从 O(n log n) 降到 O(n)。

1.2 从 912 到 215：分治思想的自然延伸

快速排序的核心是分区。选定一个基准值（pivot），把小于它的放左边，大于它的放右边，然后这个基准就到了它最终该在的位置。分区完成之后，基准值在整个数组中的排名是确定的——它左边有若干个比它小的，右边有若干个比它大的。

这个性质非常关键。如果你要找的是“第 K 大”，换算成升序排列中的下标 target = n - K，那么一次分区之后，pivot 的下标如果正好是 target，你就直接得到了答案。如果 pivot 的下标比 target 小，说明目标在右半边，只递归右半边；如果 pivot 的下标比 target 大，说明目标在左半边，只递归左半边。

看到没有？这就是快排“两边都递归”变成“只递归一边”的过程。912 题是整棵递归树全展开，215 题是每次砍掉一半。理解了这一层，两道题就不再是孤立的知识点，而是同一个分区思想下的两种产物。

2. 912 题之快速排序：手撕核心代码

2.1 分区过程是快排的心脏

快速排序之所以叫“快速”，靠的就是分区这一步。我写快排时常用“挖坑法”：取最左边的元素作为基准值，把这个位置挖成一个坑，然后从右往左找比基准小的元素填坑，再从左往右找比基准大的元素填坑，两边交替移动，直到左右指针相遇，最后把基准值放回相遇的位置。

def quick_sort(nums, left, right): if left >= right: return pivot = nums[left] i, j = left, right while i < j: while i < j and nums[j] >= pivot: j -= 1 nums[i] = nums[j] while i < j and nums[i] <= pivot: i += 1 nums[j] = nums[i] nums[i] = pivot quick_sort(nums, left, i - 1) quick_sort(nums, i + 1, right)

这个写法的好处是直观，每一轮循环都保持一个“坑位”，不用额外申请数组空间，属于原地排序。需要注意两点：右指针一定要先动，否则最后基准值归位的位置会出错；比较条件里的等号不能随便去掉，否则遇到和基准值相等的元素时，指针可能越过对方导致死循环。

2.2 递归框架与复杂度推演

快排的递归框架很简洁：先分区，再对左右两个子区间分别递归。理想情况下，每次分区都能把数组对半分，递归树的深度是 O(log n)，每一层所有子区间加起来的总工作量是 O(n)，所以平均时间复杂度是 O(n log n)。

空间复杂度严格来说是 O(log n)，因为递归调用要占用系统栈，不是 O(1) 的原地排序。这一点面试官经常问，很多人只记得时间，把空间说成 O(1)，其实不对。

最坏情况发生在每次分区都极度不平衡的时候，比如数组已经有序，而你每次取最左边元素作为基准值。这种情况下，每次分区只确定一个元素的位置，剩下的 n-1 个元素还要继续递归，递归树变成一条链，时间复杂度退化到 O(n^2)。这正是快排“快但不够稳”的原因，所以实际写代码时，强烈建议随机选基准值或者取左、中、右三个位置的中间值。

2.3 重复元素的致命陷阱：三路快排

上面那个“挖坑法”代码，放在力扣 912 上能过，但有一个隐患：如果数组里大量元素等于基准值，比如一万个重复数字，那么每次分区实际上只把一个基准值放到正确位置，其余相等的元素全挤到一侧，整体复杂度同样会退化到 O(n^2)。这个问题在面试中很容易被追问，解决办法是三路快排——把数组分成小于基准、等于基准、大于基准三块。

import random def quick_sort_3way(nums, left, right): if left >= right: return pivot = nums[random.randint(left, right)] lt, i, gt = left, left, right while i <= gt: if nums[i] < pivot: nums[lt], nums[i] = nums[i], nums[lt] lt += 1 i += 1 elif nums[i] > pivot: nums[i], nums[gt] = nums[gt], nums[i] gt -= 1 else: i += 1 quick_sort_3way(nums, left, lt - 1) quick_sort_3way(nums, gt + 1, right)

三路快排的关键在于维护一个等于基准值的中间区间。扫描指针 i 遇到小于基准的元素，就把它和左边界的元素交换，并把左边界右移；遇到大于基准的元素，就把它和右边界交换，并把右边界左移，i 不动，因为换过来的元素还没检查过；等于基准的元素直接跳过。一轮结束后，所有等于基准的元素都已经就位，递归时完全跳过中间这段，大量重复数据下效率极高。

这个版本虽然在 912 这种“普通数据”上不一定比普通快排快多少，但碰上全等、接近全等的用例，稳定性好得多。工程上很多排序库之所以在数据量小时切换插入排序、数据量大时用三路快排或 Timsort，就是为了规避这些退化场景。

3. 912 题之归并排序：稳妥的备选方案

3.1 归并的完整实现

归并排序的思路和快排正好相反。快排是先分区再递归，归并是先递归到底再合并。它的核心操作是合并两个已经有序的子数组，这个合并过程是稳定的，也就是说相等元素的相对顺序不会改变。

def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) res = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res.extend(left[i:]) res.extend(right[j:]) return res

这个写法每次递归都会创建新的切片和结果数组，好理解但空间开销偏大。面试时如果能改成在原数组上使用辅助数组归并，会更加分。做法是：每次归并前，把 nums 左闭右开区间的内容复制到辅助数组，然后双指针从辅助数组写回原数组。

归并排序的时间复杂度无论什么情况都是 O(n log n)，不会像快排那样退化，这是它最大的优势。空间复杂度 O(n)，需要额外数组存放归并结果，这也是它不如快排“省”的地方。

3.2 快排和归并的面试对比

面试时问排序，快排和归并的对比几乎是必考题。我自己总结了一张对照表，关键信息一目了然：

从这张表能看出，快排的优势在原地在位、额外空间小，性能常数也小；归并的优势在稳定且最坏情况可预期。实际工程里，像大数据量的外部排序，数据量大到内存装不下，归并排序就非常合适，因为它可以分块读写磁盘。而面试中如果你能主动说出“为什么很多排序库默认用快排而不是归并”，再补一句“但最后的优化版本其实是混合算法”，面试官对你的评价会明显不一样。

4. 215 题之快速选择：找到第 K 大的最优解

4.1 从“排完再取”到“定位即返回”

现在重点来了。215 题最暴力的解法是排序后取下标，代码三行：

def find_kth_largest(nums, k): nums.sort() return nums[len(nums) - k]

这个解法能过，但如果你在面试里这么做，面试官大概率会追问一句：能不能不用完整排序？因为排序做了大量无用功。想想看，如果 n 等于一千万，K 等于 5，你真的要把一千万个数全部排好吗？只需要知道最大的 5 个是谁，其他 999 万个元素的顺序根本无所谓。

快速选择就是用一次分区，直接判断基准值的位置是不是目标位置。如果不是，只递归包含目标的那一半，另一半直接扔掉。这就把“排序整个数组”缩减成了“每次扔掉一半”，单次分区是 O(n)，总共 O(n + n/2 + n/4 + ...) = O(2n)，也就是 O(n)。

4.2 索引换算：第 K 大到底是第几个

这里有一个特别容易搞混的地方。第 K 大是最直观的说法，但我们的快排分区默认产生的是“升序位置”，所以要把第 K 大换算成升序下标。

举个例子：数组 [3, 2, 1, 5, 6, 4]，第 1 大是 6，第 2 大是 5。升序排列是 [1, 2, 3, 4, 5, 6]，第 1 大的 6 在升序下标 5，第 2 大的 5 在升序下标 4。规律就是：第 K 大 = 升序下标 n - K，下标从 0 开始。这个换算关系一定要记牢，写代码时一个符号错，结果就全反了。

建议写一个辅助函数 quick_select(nums, left, right, target)，target 就是换算后的升序下标，主函数里统一调用。这样逻辑清晰，不容易搞混边界。

4.3 复杂度直觉：为什么平均是 O(n)

很多初学者看到“平均 O(n)”会觉得奇怪：排序都至少要 O(n log n)，你不排序怎么可能更快？关键在于每次分区后只处理一半数据。

假设第一次分区花了 cn 的时间（常数 c 乘数组长度），分区后运气正常，目标大概率在其中的一半里，那么第二次分区处理 n/2 个元素，耗时 cn/2，第三次 cn/4，以此类推。总时间就是 cn + cn/2 + cn/4 + ... = cn*(1 + 1/2 + 1/4 + ...) = 2c*n。去掉常数，就是 O(n)。

这个等比求和过程可以类比成“每次扔掉一半沙子，但每次处理的工作量也在减半”。所以快速选择的平均表现非常优秀，处理一千万个元素找第 K 大，几毫秒就能完成。最坏情况同样是 O(n^2)，发生在每次分区都极其不平衡的时候，解决办法和快排一样——随机选基准值。加上随机化之后，在实际绝大概率不会触发最坏情况。

快速选择推荐使用三路分区版本，因为它能直接跳过大量等于基准值的元素，在数据里重复值很多时更稳：

import random def quick_select_3way(nums, left, right, target): if left > right: return None pivot = nums[random.randint(left, right)] lt, i, gt = left, left, right while i <= gt: if nums[i] < pivot: nums[lt], nums[i] = nums[i], nums[lt] lt += 1 i += 1 elif nums[i] > pivot: nums[i], nums[gt] = nums[gt], nums[i] gt -= 1 else: i += 1 if target < lt: return quick_select_3way(nums, left, lt - 1, target) elif target > gt: return quick_select_3way(nums, gt + 1, right, target) else: return nums[target] def find_kth_largest(nums, k): target = len(nums) - k return quick_select_3way(nums, 0, len(nums) - 1, target)

这段代码的关键是分区结束后三个区间清清楚楚：nums[left..lt-1] 都小于基准，nums[lt..gt] 都等于基准，nums[gt+1..right] 都大于基准。然后判断 target 落在哪个区间，如果落在中间等于段，直接返回，因为那个位置的值就是基准值本身。

5. 215 题之堆解法：数据流场景的答案

5.1 大小为 K 的最小堆实现

快速选择虽然快，但它需要能直接访问整个数组。如果数据不是一次性全部给出，而是像数据流一样源源不断输入，快速选择就无能为力了。这时候要用堆。

思路很简单：维护一个大小为 K 的最小堆，遍历数组时，如果堆还没满就直接往里塞；如果堆满了并且当前元素比堆顶大，就把堆顶弹出，把当前元素塞进去。遍历结束后，堆里留下的就是整个数组中最大的 K 个元素，堆顶就是这 K 个里面最小的，也就是第 K 大的那个。

import heapq def find_kth_largest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap[0]

Python 里的 heapq 是系统自带的堆，默认就是最小堆。每插入一个元素是 O(log k)，总共 n 个元素，总时间复杂度 O(n log k)。当 K 远小于 n 时，这个复杂度相当能打。比如 K = 1，堆里永远只有一个元素，复杂度退化成 O(n)；K = n/2 时才是 O(n log n)，但那种情况直接用排序反而简单。

这里有一个小优化点：当堆的长度等于 K 之后，没必要每一次都先 push 再 pop。可以比较一下当前元素和堆顶，如果当前元素比堆顶小，直接跳过，省掉一次堆的调整操作。虽然对复杂度没有量级上的影响，但能减少常数时间，数据量大时能感受到差别。

5.2 堆解法、快选、排序怎么选

这三种方法各有适用场景，面试中往往要求你给出权衡。排序最简单，代码不易出错，适合 K 很接近 n 或者数组规模不大的情况。快速选择平均最快，但会修改原数组的顺序，而且对数据流不友好。堆解法支持在线处理，不需要一次读入全部数据，内存占用稳定为 O(K)，但常数时间比快选大一些。

实际面试时，我建议先把快速选择写出来，体现你对排序思想的理解深度；然后主动提一句“如果数据是流式的，可以用大小为 K 的堆”，展现出你会针对场景选方案的工程思维。这两手同时亮出来，比只会一种解法要沉稳得多。

6. 刷题中的边界坑与面试建议

6.1 索引与边界自查表

这两道题代码都不长，但边界条件极其容易出错。我自己刷的时候踩过不少次，总结了一张自查表，每写完解法都对着过一遍：

• K = 1 时，target = n - 1，快速选择应该能直接定位到最大值。
• K = n 时，target = 0，定位到最小值。
• 数组长度为 1 时，left 和 right 相等，快速选择要有 left == right 的终止条件。
• 空数组和越界访问，LeetCode 一般保证输入合法，但自己写测试时要注意。
• 快速选择里递归调用时，如果 target 落在等于段，直接返回；如果落在小于段，递归区间是 left 到 lt - 1，千万别把 lt 或 gt 传错。
• 堆解法里，当 len(heap) 大于 K 时要 pop，不然堆里元素超过 K，堆顶就不是第 K 大了。

这些坑的特点是不跑特殊用例根本发现不了。我练题时习惯把像 [1]、[1, 2]、[3, 3, 3, 3] 这种特殊用例先跑一遍，通过之后再提交，能省掉不少罚款时间。

6.2 分区写法的三种流派

不同教材和题解里，分区函数有三种常见写法，了解它们的区别对读别人代码很有帮助。

第一种是 Hoare 分区，双指针从两端往中间扫描，相向而行，遇到该交换的就交换。它访存次数少，但基准值最终位置不太好确定，代码稍绕。第二种是 Lomuto 分区，用一个慢指针维护小于区间的边界，基准值取最右元素，代码比较短，适合教学。第三种就是我前面用的挖坑法，从最左挖坑、双指针交替填坑，代码好记，但重复元素的退化问题需要三路快排来兜底。

我的建议是：学习阶段三种都写一遍，体会它们维护区间的方式差异；面试时选择自己最熟的一种，但一定要能解释清楚为什么这样写不会死循环、不会越界。

6.3 把两道题串起来刷的建议

刷题讲究综合训练。912 和 215 正好构成一个组合：先练手写快排，再练在这个基础上做减法得到快速选择。我推荐的练习顺序是：先独立写出 912 的普通快排，然后写出 912 的三路快排版本，再做 215 的快速选择。做完之后，把三路分区那段代码复制到快速选择里，你会发现只需要改动递归部分，就完成了从“排序”到“选择”的跨越。

之后可以再看看归并排序，想一想如果 215 题要求输出前 K 大的全部元素（而不是只输出第 K 大），堆和快选各自怎么改。这样一道题变成了一串题，复习效率比孤立刷要高得多。

我个人在实际操作中的体会是：快速排序的“分区”是整个排序算法里最值得花时间吃透的概念。只要你真正理解了分区完成后基准值的位置就是它最终的位置，那么第 K 大、第 K 小、找中位数、甚至荷兰国旗问题，都会一下子豁然开朗。如果你现在还在背代码阶段，不用急，把分区这段多写几遍，写到自己能默写出每一步为什么这样做，再去刷 215 会顺手很多。最后再分享一个调试小技巧：快速选择写出后，找一组数据手动走一遍递归，画出每次分区后 target 所在区间的变化，确认递归参数没传错，比任何调试器都管用。