企业官网建设流程全解析

第K个最大元素和排序数组，这两道题放在一起刷，效率是分开刷的两倍。912题表面上只是让你实现一个排序，215题则让你在不需要完整排序的前提下找到第K个最大元素；可一旦你理解快排的partition本质上是把元素放到“最终位置”，就会意识到后面这道题完全可以用前面那道题的技巧来解。这篇文章不打算列一堆互不相关的题解，而是以我自己的刷题视角，把两道题的共同底层逻辑、每种解法的适用场景，以及我踩过的退化与边界坑，一次性讲明白。适合刚刷完基础数组题、想把手写排序和TopK类问题彻底吃透的人。

1. 先看清楚题：这两道题到底在考什么

1.1 一道全排序，一道“半排序”

912题，排序数组：输入一个整数数组，返回升序排列。表面上这题简单到人人会做，打开Python一行nums.sort()就结束。但我建议你把它当成一次“手写排序算法”的体检：快排能不能写对？堆排的下标调整能不能一次通过？归并的边界处理是不是干净的？很多人真到了手写这一步才发现自己只是会“调用”排序，而不是会“实现”排序。

215题，数组中的第K个最大元素：输入一个数组和整数K，返回第K大的元素。比如[3,2,1,5,6,4]，K=2，答案是5。这题有个很反直觉的点：你不需要让整个数组有序，就能回答“第K大”的问题。它是一道典型的“部分排序”题目，考的是你能否把复杂问题拆解成更省时间的操作。

1.2 为什么这两道题适合捆绑学习

如果把所有数组题按“对顺序的依赖程度”排个序：全排序是100%，找一个最大元素是0%，找第K个最大元素大概在60%——你只需要保证前K个或者某个特定位置有序就够了。

这种“部分有序”的需求在工程里非常常见。比如排行榜要看Top 10，不需要把100万用户全部排好序，只需要找出分数最高的10个。再比如推荐系统里取最相关的K条新闻，也不用把整个候选集全部排序，只要快速挑出TopK。所以215这类TopK问题不是面试官的刁难，而是把真实需求抽象成的一道算法题。

而912题的价值在于：它逼你把排序的每种流派都过一遍。快排、堆排、归并是三大主流，各有各的适用场景。把它们吃透，你就等于掌握了处理“全排序”和“部分排序”的两套基础工具。面试时追问也从这里来：你用了快排，那最坏时间复杂度是多少？怎么避免退化？你能不能改一下变成找第K大？——这套追问路径恰好就是912到215的思考路径。

1.3 两道题背后共同的“partition”基因

这才是把两道题放一起讲最关键的地方。快速排序每次选择一个基准元素pivot，然后通过partition操作，把小于pivot的放左边、大于pivot的放右边；完成后，pivot已经处于整个数组最终排序时的正确位置。既然我们知道pivot的最终下标，那问题就转化了：

• 如果pivot的下标恰好是目标位置，直接返回；
• 如果目标位置在pivot左边，就只递归左边；
• 否则只递归右边。

这就是快速选择（QuickSelect）算法，也是215题最优解之一的底层原理。所以你在912题里写出的每一个partition，搬到215题里稍加改造，就是一类新解法。很多视频课把它们拆开讲，其实挺可惜的，因为它们根本就是一脉相承。

2. 912题实操：三种排序实现的完整拆解

2.1 快速排序：面试频率最高的写法

快排的思路，我用一句话概括：选一个基准，把所有比它小的放到左边，比它大的放到右边，然后对左右递归。这个“放”的过程就是partition。

先给一种最常见的原地写法，我建议每一个细节你都亲手敲一遍：

import random def quick_sort(nums, left, right): if left >= right: return pivot_idx = random.randint(left, right) nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left] 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)

有几个细节值得单独说：

• 为什么必须随机选pivot？因为当输入接近有序时，固定选第一个元素会让partition极度不平衡，递归深度变成O(n)，时间复杂度退化成O(n^2)。随机化之后，出现这种最坏情况的概率变得极低。
• 为什么双指针交替赋值而不是每步都swap？因为这样省一次临时变量交换，常数更小；但代价是写法不够直观，很多人第一次写容易漏退出条件。
• nums[j] >= pivot和nums[i] <= pivot里的等号不能省。少了等号，遇到重复元素时指针可能不推进，陷入死循环。

排序数组912题用这个写法已经能过测试。但同样是快排，另一个方向是把分区写成“三路划分”，专门处理大量重复元素。它的核心是把数组分成三块：小于pivot、等于pivot、大于pivot，这样重复元素不用再进入递归，效率更高。后面讲215题的退化问题时会再回到三路划分。

2.2 堆排序：原地、最坏情况也更稳

堆排序的核心认知是：完全二叉树 + 大顶堆。升序排序用大顶堆，每次把堆顶（最大值）换到末尾，堆长度减一，再重新调整。实现分两步：建堆和调整。

def heapify(nums, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and nums[left] > nums[largest]: largest = left if right < n and nums[right] > nums[largest]: largest = right if largest != i: nums[i], nums[largest] = nums[largest], nums[i] heapify(nums, n, largest) def heap_sort(nums): n = len(nums) # 建堆：从最后一个非叶子节点开始向上调整 for i in range(n // 2 - 1, -1, -1): heapify(nums, n, i) # 逐个取出堆顶 for i in range(n - 1, 0, -1): nums[0], nums[i] = nums[i], nums[0] heapify(nums, i, 0)

我一直觉得堆排序是“原理想通、代码却容易写崩”的代表。新手最常见的坑是数组下标：left = 2*i + 1、right = 2*i + 2，很多人写成2*i，建堆时下标全乱。第二个坑是heapify的递归参数，调整完一个子树后一定要继续向下heapify，否则小元素“沉不下去”。

堆排序的优点是原地排序，额外空间O(1)，最坏时间复杂度也是O(n log n)，不会被输入顺序坑到。缺点是它不稳定（相等的元素可能交换相对顺序），而且常数额外大，实际性能往往不如优化的快排。所以工程里它不常被直接用，但它“堆顶就是最大/最小”这个特性，在TopK问题里反而大放异彩，正好对应215题的堆解法。

2.3 归并排序：稳定是它最大的招牌

归并排序用一句话概括：把数组对半切开，分别排好序，再把两个有序段合到一起。

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

为什么归并是稳定的？因为合并两个有序段时，只有当左边元素严格大于右边元素才会取右边的元素；相等的元素永远先取左边的，相对顺序保持原样。

归并的缺点是每次递归都切出新数组，空间复杂度O(n)。如果想做成原地归并会很麻烦，而且常数通常很大。工程里归并的重要场景是“外排序”：数据量大到内存装不下时，把数据分块排序落盘，再对多个有序块做多路归并。另一个经典场景是链表排序，链表不像数组能随机访问，快排和堆排都不好实现，但归并只要沿着next指针走就行，所以链表排序题目的标准解就是归并排序。

如果912题只要求能过，我更推荐你在面试中用三路划分的快排；如果面试官追问稳定性和外排序场景，归并的理解就派上用场了。

2.4 工程上为什么你很少手写排序

有人会问：既然语言里都有sorted()，为什么还要手写？我的看法是：工程上确实不该因为“显摆技术”去手写排序，内置排序的实现融合了大量优化——Python的TimSort是归并+插入的混合体，能利用数据中已有的有序片段；C++的std::sort是IntroSort，兼顾快排的平均速度和堆排的最坏保证。这些不是一个人一天能超越的。

但算法题和工程不同。面试官让你写快排，不是想让你证明“我不会调用sort”，而是想观察你对分治的理解、对退化的意识、对复杂度的计算。912题就是这样一个“安全环境”下的练习场：写错代价小，反馈快，特别适合把手写排序的肌肉记忆练出来。等你做215题时，这份肌肉记忆就能直接变成快速选择的实现基础。

3. 215题实操：第K大元素的四种解法与选型

3.1 排序法：最直白，也最容易被追问

一句代码的事：

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

复杂度O(n log n)。在面试中，这通常作为“第一反应”说出来没问题，但你要立刻意识到：它做了大量多余工作。你要的只有第K大，可排序把每一个元素都安排到了最终位置。这就像你要找班里分数排第十的人，却先把整个年级的成绩全部重新排了一遍。

所以面试官基本都会接着问：“能不能别排全序？”——这正好引出下面两种解法。我建议即使面试官不问，你也在答案里主动展开，能体现你很清楚两种方案的复杂度差异。

3.2 堆解法：海量数据和流式场景的标配

思路说起来挺反直觉：要找第K大的元素，我们维护一个大小为K的最小堆。堆里存的是目前见过的“最大的K个数”，其中堆顶就是这K个数里最小的，也就是整个数组第K大的元素。

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

逐行解释一下：

• heapq是Python默认的最小堆。我们只维护K个元素，所以遍历每个数时先放入，一旦超过K就弹出最小的，留下的永远是最大的K个。
• 循环结束后，堆里恰好是数组里最大的K个数，堆顶是这K个数中最小的，它就是全局第K大。
• 时间复杂度O(n log K)。当K远小于n时，比排序的O(n log n)省很多；更重要的是，它天然适合数据流场景——数据是一个个进来的，甚至不知道总量多大，你只需要一个容量K的堆，内存占用固定，完全不需要一次性把所有数都存下来。

我在真实项目里做实时热点榜单，用的就是这个思路。热搜接口每秒钟会推过来很多条点击数据，内存里维护一个大小100的堆，每次只保留热度前100的候选词，再配合定期刷新榜单，几分钟一次的频率根本不用全量重排。

有的教程会写“找第K大用小顶堆，找第K小用大顶堆”，这个口诀容易记反。我自己总结的记法是：堆顶必须是答案。答案如果是“第K大的数”，K个大数中谁最小谁来当代表，所以堆顶要最小，就是用最小堆。

3.3 快速选择：平均O(n)的解法，值得手写一遍

既然912题的快排partition能把pivot放到最终位置，那么第K大的问题就变成：不断做partition，如果pivot的位置正是目标位置就返回，否则只处理pivot所在位置的那一侧。

import random def findKthLargest(nums, k): n = len(nums) target = n - k # 第K大在升序数组中的下标 def partition(left, right): pivot_idx = random.randint(left, right) pivot = nums[pivot_idx] nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] store = left for i in range(left, right): if nums[i] <= pivot: nums[store], nums[i] = nums[i], nums[store] store += 1 nums[store], nums[right] = nums[right], nums[store] return store left, right = 0, n - 1 while left <= right: pos = partition(left, right) if pos == target: return nums[pos] elif pos < target: left = pos + 1 else: right = pos - 1

这段代码里有几个关键点：

• target = n - k是升序数组里“第K大”的下标。比如[1,2,3,4,5]里第2大的数是4，下标是3，也就是n - k = 5 - 2 = 3。这里千万不要写成k - 1，那是降序排列的下标。
• partition用“快慢指针”写法：store是已处理区间里“小于等于pivot”的边界，i遍历除pivot外所有元素。这个写法比双边收缩更好控制，不容易死循环。
• 为什么不是递归而是while？因为每一轮我们都只往一侧收缩，用迭代可以避免递归深度问题，也更清晰。如果写成递归，左闭右闭区间的边界容易出错，我见过很多人在right = pos - 1和递归参数间来回改，最后改晕。

复杂度上，快速选择的平均时间复杂度是O(n)，因为第一次partition处理n个元素，第二次只处理大约n/2个，加起来是n + n/2 + n/4 + ...，收敛到2n。但最坏情况仍是O(n^2)（比如每次pivot都选到最值、且输入极度不平衡），所以随机化pivot是必须的。

在215题这种场景，测试数据通常比较常规，快速选择完全够用；如果面试官故意问“全是重复元素怎么办”，就需要下面这个升级版：三路划分快速选择。

3.4 四种解法的横向选型

用一张表收拢一下：

真实面试中我的建议顺序：先答排序法建立直觉，再主动给出堆解法体现工程思维，最后用快速选择展示你对快排partition的深度理解。三条路都走一遍，这道题基本就拿满了。

4. 实战避坑：那些让我debug到怀疑人生的细节

4.1 全相同的数组：普通partition的退化问题

先说一个隐藏得很深的坑。数组如果是[1,1,1,1,...,1]，普通快排每次随机选的pivot都是1，partition会把所有元素放到pivot左边或右边，划分极度不平衡，快排退化接近O(n^2)。

处理方案有两个。一个是三路划分：把等于pivot的元素集中放在中间，递归只处理小于和大于的两侧。因为等于pivot的区域已经不需要再处理，全是重复元素时，一轮partition就结束，时间复杂度O(n)。

def quick_select_3way(nums, left, right, target): 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 if target < lt: return quick_select_3way(nums, left, lt - 1, target) elif target > gt: return quick_select_3way(nums, gt + 1, right, target) return pivot

另一个方案是前面代码里的随机pivot + 分区时用<=和>=同时把等于元素往两侧推。但随机只能降低概率，不能根除退化；三路划分则是从结构上消灭这个隐患。刷题时我建议直接用三路，面试官会眼前一亮。

4.2 递归深度：Python的1000层限制

912题快排如果用递归写法，最坏情况下递归深度可能到n。Python默认递归深度上限是1000，一旦数据是降序排列又恰好每次pivot选在最边上的元素，就会直接RecursionError。这也是我上面215题快速选择坚持用while迭代的一个原因：规避递归深度限制，代码也更稳。

如果912题一定要递归，可以引入随机pivot大幅降低退化概率，再配合三路划分。题目给的输入规模一般不会故意卡递归深度，但养成好习惯总没错。顺带一提，面试时如果你主动说“我用迭代避免了递归栈溢出”，这是个很好的加分点。

4.3 第K大和第K小的下标迷思

这大概是215题评论区出现频率最高的一类错误。升序数组中，第K大元素的下标是n - k；降序数组中，第K大元素的下标是k - 1。很多人把快速选择写成找k - 1，结果对着一半用例报错。

我的建议是：所有代码里统一用升序视角，因为大多数语言排序默认升序，思维负担最小。写之前先在注释里写清楚target = n - k，再开始写partition。如果你觉得自己容易搞混，可以用一个小例子自测：[1,2,3,4,5]，K=2，答案显然是4，n - k = 3，下标3正好是4。

4.4 堆解法里“用大顶堆还是小顶堆”的混乱

这个坑和上一个类似，都是方向问题。求第K大，维护最小堆；求第K小，维护最大堆。理由再强调一遍：第K大的答案等于“最大的K个数里最小的那个”，这个“代表”是堆顶，它就必须是堆里最小的，也就是最小堆。

Python的heapq只有最小堆，想用最大堆要取负数入堆。如果你面试时写的是Java，PriorityQueue默认也是最小堆，求第K小才要用Collections.reverseOrder()。这种语言层面的差异很容易在紧张时写反，建议出门前先默写一遍。

4.5 我在本地反复验证过的几个数据体会

再分享一下我调试时的直观感受。用10万个随机整数测试：排序法大约几十毫秒；堆K=10时更快，但K接近n时不明显；快速选择的常数很小，通常比堆更快。但如果数组几乎有序，固定选第一个元素当pivot的快排会明显变慢，而随机化pivot后感知不到差异。这个现象建议你自己跑一次，比背几张复杂度表记得牢。

另外，哪怕题目给的测试用例不多，手写快排时也建议用random.randint而不是固定下标，这个习惯直接迁移到215题就能省很多麻烦。我在最初练习时固定选nums[left]，遇到构造好的近乎有序的大数组，瞬间超时，排查半天才意识到是pivot选择的问题——这就是一遍遍调试换来的经验。

5. 从题目到工程：排序与TopK的真实应用

网上很多人刷完215题就认为它只是面试题，我不同意。TopK问题的工程形态非常多，我在两类真实系统里反复用过这个思路。

第一类是排行榜和热点榜单。以我做过的一个内容社区推荐系统为例，每天有几十万条内容产生，需要展示“本周热度Top20”。如果每次请求都把所有内容按热度排一次序，代价太高。实际做法是：维护一个容量20的小顶堆，流式遍历新内容，凡是比堆顶热度高的就替换堆顶，最终堆里就是Top20。这与215题的堆解法几乎一模一样，只是多了一个“实时更新”的动作。

第二类是推荐系统的粗排截断。在粗排阶段，可能有几千条候选，但精排模型只接受几百条，怎么截断？直接用快速选择思想的“部分排序”就能搞定：只需要知道TopN是哪些元素，连中间那些元素的顺序都不需要精确。某些实现里还会用到nlargest这类内置函数，底层就是堆或者快速选择的变体。

这些场景共通点是：不需要完美的全序，只需要知道前K个或者某个位置的元素。如果你在912题里把各种排序实现练熟了，在215题里理解了partition和堆这两种武器，工程里碰到这类需求，你的第一反应就不再是“全量load排序”，而是“我可以用堆流式处理”或者“我可以做一次部分排序”。这就是算法题和工程能力之间最真实的连接。

我自己现在写代码，遇到排序需求时，脑子里会自动弹出复杂度对比：数据量小、只需要一次，直接排序；数据量大、还在增长，考虑堆；数据能进内存但追求速度，快速选择；多路有序文件合并，归并。这套判断不是看题看出来的，是这两道题反复手写、踩坑、复盘之后长在身上的。