说起力扣刷题，排序题目是我最早碰、也最晚想明白的一类。刚开始我以为"过一遍快排和归并就能应付"，结果连续几道题把我按在地上摩擦——不是不会写排序，而是不知道题目想让我用什么排序、为什么这么排序、边界条件又藏在哪里。这篇算是我对排序题的一轮完整复盘：三套必须背到肌肉记忆的模板、自定义比较器里那些一踩一个准的坑、排序思维怎么迁移到区间合并和 TopK 这类变形题，最后是一条我自己验证过的刷题路线。适合刚开始刷力扣的同学，也适合刷了一阵子但每次遇到"自定义排序"就发怵的朋友。

1. 先看考点分布：排序题远不止"把数组排好"

1.1 三个层次的排序题

我在带新人梳理题库时，习惯把排序题拆成三个层次看。

第一层是"裸排序"，给你一个数组让你排序。这种题在力扣上几乎不会直接出现，因为调一下内置 sort 就结束了，出题人没必要考这个。第二层是"自定义排序"，给一堆对象、区间、字符串，让你按某种规则重新排列，本质考的是比较器的表达能力和对排序稳定性的理解。第三层是"排序思维"，表面看根本不是排序题，但最优解偏偏依赖排序，典型的如合并区间、求第 K 大、统计逆序对、安排会议室。

这三个层次对应三种能力：模板记忆能力、规则表达能力、抽象建模能力。面试官真正想看的是第三层，因为工作里"把一堆数据排一下"从来不是难点，难的是你知不知道什么时候该把它变成排序问题。这一点其实是刷排序题最大的收获，比背熟十个模板都值。

1.2 从高频考点反推复习重点

把力扣排序标签下的题目过一遍，你会发现高频方向非常集中，我列个表给你参照：

复习策略也应该按这些方向组织，而不是"今天把快排背一遍，明天背堆排"。我见过太多人抱着这个思路刷了两周，结果遇到一道自定义排序题直接懵掉，因为背模板练不出规则表达的能力。

1.3 最常见的复习误区

很多人刷排序题最大的误区是"一律用库函数一把梭"。刷题时你当然可以用库函数，但如果你连一次手写快排都写不利索，到了面试手写排序的环节一定会露馅。更隐蔽的问题是，库函数在配了特殊比较器之后更容易出 bug，比如比较器忘记处理相等情况，在某些语言里会直接导致崩溃，在另一些语言里则表现为排序结果"看起来差不多但就是不对"。

我的建议是：刷题阶段大胆用库函数，但每周固定抽出时间手写一遍三大模板，写到闭眼能出的程度。这笔账怎么算都不亏。

2. 三套必须背到肌肉记忆的排序模板

2.1 快速排序：随机化 pivot 和三路划分

快排的核心是 partition。我见过太多人背模板时把 pivot 固定在第一个位置，遇到近乎有序的输入直接退化到 O(n²)。力扣的评测数据未必会卡你，但面试官最爱的追问就是"如果输入已经有序会怎样"，这时候你要是答不上来随机化 pivot 和 introsort，印象分会掉得很难看。

先给一套标准的随机化快排模板，Python 写法：

import random def quick_sort(nums, l, r): if l >= r: return # 随机选 pivot，避免有序输入导致退化 idx = random.randint(l, r) nums[l], nums[idx] = nums[idx], nums[l] pivot = nums[l] i, j = l, r 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, l, i - 1) quick_sort(nums, i + 1, r)

注意那两个内层循环的符号。左边找大于 pivot 的，右边找小于 pivot 的，符号写反了就会出现死循环或者把相等元素来回交换。如果你要处理大量重复元素的场景，建议直接上三路划分（小于、等于、大于三段），否则在全是相同数字的数组上，普通快排依然会退化。

另外提一句，C++ 的std::sort是 introsort 实现，快排退化时自动切到堆排，所以日常工程代码不需要自己处理这个风险；但面试手写算法时，你必须能讲清楚这个机制。

2.2 归并排序：稳定且能顺带统计逆序对

归并排序的特点是两个"天然"：天然稳定，天然能统计逆序对。很多排序题的最优解就是建立在归并过程上的，所以这套模板必须写得极其熟练。

def merge_sort(nums, l, r): if l >= r: return 0 mid = (l + r) // 2 cnt = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r) i, j, k = l, mid + 1, 0 tmp = [0] * (r - l + 1) while i <= mid and j <= r: if nums[i] <= nums[j]: tmp[k] = nums[i] i += 1 else: tmp[k] = nums[j] j += 1 cnt += mid - i + 1 # 左边剩余元素都比 nums[j] 大 k += 1 while i <= mid: tmp[k] = nums[i] i += 1 k += 1 while j <= r: tmp[k] = nums[j] j += 1 k += 1 nums[l:r+1] = tmp return cnt

这段代码里最值得品的是cnt += mid - i + 1这一行。归并时只要右侧当前元素小于左侧当前元素，那么左侧 i 之后的所有元素都大于它，这些全部构成逆序对，所以不需要逐个遍历，一次就能累加完。这也是归并解法能到 O(n log n) 的原因。

归并在链表排序上还有一个额外优势：不需要额外数组，直接把指针拆开再合并，空间是 O(1)。链表版归并是高频面试题，建议单独练一遍快慢指针找中点+递归合并的写法。

2.3 手写堆：TopK 问题的标配

堆排序本身作为排序算法考得不多，但它的变体——用堆解决 TopK、第 K 大、数据流中位数——出现频率极高。我建议重点掌握的不是堆排序的完整流程，而是怎么用堆维护一个固定大小的集合。

求"第 K 大元素"最反直觉的一点是：你要维护的是小顶堆，而不是大顶堆。堆里永远只留最大的 K 个元素，堆顶就是这 K 个里最小的，也就是全局第 K 大。每个新元素进来，如果比堆顶大，就弹出堆顶再入堆，否则直接丢弃。这样整体复杂度是 O(n log K)，K 远小于 n 时非常划算。

import heapq def find_kth_largest(nums, k): heap = [] for x in nums: if len(heap) < k: heapq.heappush(heap, x) elif x > heap[0]: heapq.heapreplace(heap, x) return heap[0]

手写堆的完整模板也要会，尤其是 shiftUp 和 shiftDown 的边界条件。面试时如果让你用堆实现一个优先队列，写不出来是很尴尬的。我自己的技巧是：把heapq的行为当作基准，写完手写堆之后用随机数组和库函数对拍一遍，能对上就说明边界没问题。

3. 自定义比较器：一个符号写反就能让整个排序失效

3.1 三种主流语言的比较器写法

自定义比较器是排序题里翻车率最高的环节。先看写法，再讲坑。

Python 优先用key，不够用再上functools.cmp_to_key：

from functools import cmp_to_key def compare(a, b): # 返回负数表示 a 排前面 if a[1] != b[1]: return b[1] - a[1] # 分数降序 return a[0] - b[0] # 分数相同时编号升序 sorted(people, key=cmp_to_key(compare))

C++ 里注意 lambda 必须满足严格弱序，即返回 true 表示第一个参数排在第二个前面：

sort(v.begin(), v.end(), [](const vector<int>& a, const vector<int>& b) { if (a[1] != b[1]) return a[1] > b[1]; return a[0] < b[0]; });

Java 则实现Comparator接口，compare返回负数、零、正数：

Arrays.sort(people, (a, b) -> { if (a[1] != b[1]) return Integer.compare(b[1], a[1]); return Integer.compare(a[0], b[0]); });

写法本身不难，难在三个地方：返回值符号、相等元素处理、比较器的传递性。

3.2 稳定性陷阱：看起来一样，细节全不一样

很多人在排序时默认"相等元素会保持原有顺序"，但这个假设在工程排序里并不成立。Python 的sorted底层是 Timsort，稳定；但 C++ 的std::sort是 introsort，不稳定；Java 对对象数组的Arrays.sort是稳定的归并，对基本类型数组却是不稳定的双轴快排。

如果你自定义的比较器只比较了一个字段，而第二字段刚好相等，那么两个排序结果可能完全不同。比如按分数降序排一批学生，分数相同的两个人，稳定排序会保留原数组顺序，不稳定排序则结果不确定。所以当你需要"先按分数降序，分数相同按学号升序"时，必须在比较器里把两个条件都写全，不要指望稳定性帮你兜底。

3.3 溢出与传递性：两个隐藏大佬

先说溢出。经典的"把数组排成最大数"那类题，如果你用整数拼接来比较，a + b转换成数字后很容易超过 int 范围，一溢出整个比较逻辑就全乱了。正确做法是转成字符串，直接比较字符串拼接x + y和y + x的字典序。这是字符串比较，没有溢出问题，也天然满足传递性。

再说传递性。比较器必须满足：如果compare(a, b) < 0且compare(b, c) < 0，那么compare(a, c) < 0。一旦违反，C++ 的 sort 会直接进入未定义行为——可能崩溃，可能结果乱序；Python 的cmp_to_key也会给你一个逻辑上自相矛盾的顺序。最常见的违反方式就是比较逻辑里掺了"和位置相关的判断"或者"依赖某个全局状态的判断"。

我踩过最典型的坑是把x + y > y + x ? x 在前 : y 在前写反成x + y <= y + x，结果最大数问题的答案差了一个字符，还花了大半个小时才通过测试用例定位到是符号问题。

3.4 实例拆解：字典序拼接最大数

这个问题的解法思路很干净：把数字转字符串，排序规则是"谁拼接后更大谁排前面"，最后把排序结果拼起来。注意两个边缘情况：数字可能包含 0，全部是 0 时结果不能是"000...0"而要返回单个"0"。

def largest_number(nums): strs = list(map(str, nums)) def cmp(a, b): if a + b > b + a: return -1 elif a + b < b + a: return 1 return 0 strs.sort(key=cmp_to_key(cmp)) if strs[0] == '0': return '0' return ''.join(strs)

这道题把所有自定义排序的坑一次性集中了：字符串比较规避溢出、严格弱序保证正确性、特判全零避免前导零。想练自定义比较器，这一题是首选。

4. 排序思维迁移：区间合并、TopK 与逆序对是怎么借力的

4.1 区间合并：先排序再线性扫描

合并区间的经典做法是先按左端点排序，再维护一个当前区间。为什么排序能让问题变简单？因为排序保证了后续区间的左端点不会比之前的更小，这样我们只需要关注"下一个区间的左端点是否落进当前右端点覆盖的范围"，一次扫描就能完成，不用反复回溯。

def merge(intervals): intervals.sort(key=lambda x: x[0]) res = [] for s, e in intervals: if not res or s > res[-1][1]: res.append([s, e]) else: res[-1][1] = max(res[-1][1], e) return res

这里还有个容易被忽略的细节：合并时要取max(res[-1][1], e)，因为新区间的右端点可能完全包住当前区间。如果你直接res[-1][1] = e，遇到[1, 10]和[2, 5]这种包含关系就错了。这个坑我见过不下五个人踩。

区间插入是这类题的变种，思路也依赖排序：因为原区间已经有序，插入时只需要线性走一遍，合并重叠部分即可，不需要重新排序。

4.2 TopK 与第 K 大：堆、快速选择、计数排序的三选一

求第 K 大/前 K 高频这类题，有三个看似相近但适用场景不同的方案，我放在一起对比：

实际刷题时，K 很小用堆最稳；K 接近 n/2 时堆的复杂度就变成 O(n log n)，不如快速选择；数据范围在可控范围内的 TopK 用桶排序或计数排序，代码最短也最快。有意思的是，前 K 高频元素那题官方题解还给出过基于快排的 partition 思路，本质上是在"排序数组"上做部分排序，这也印证了排序思维的迁移价值。

4.3 逆序对：归并过程的天然副产物

统计逆序对的题目，如果用暴力双层循环，复杂度 O(n²)，数据量一大必挂。归并排序之所以能顺手统计，是因为它在合并两个有序子数组时，天然知道"右侧某个元素比左侧剩下多少个元素小"。这其实就是我前面代码里cnt += mid - i + 1的逻辑。

这类题的核心价值在于提醒你：很多"计数类"问题，答案往往藏在某个排序或扫描过程的中间状态里。如果你只会调库函数，是永远看不到这一层的——库函数把过程封装了，而解题需要的是过程本身。

4.4 桶排序与计数排序：什么时候该想起它们

桶排序和计数排序不是万能的，但特定场景下是降维打击。判断标准只有一个：数据值的分布范围是否远小于数据量。比如给年龄排序（值域 0~150）、给成绩排序（0~100）、统计字符串字符频率（26 或 128 个），这些场景用计数排序只需要一趟扫描和一次回填，复杂度 O(n + k)，k 是值域。

力扣上有一类"颜色分类"的题，本质就是只含 0/1/2 三种元素的三路划分，也叫"荷兰国旗问题"。它考察的正是快排 partition 思想，而不是真的让你去调排序算法。所以刷排序题时，看到"值域很小"或者"元素种类有限"的提示，第一反应就应该是计数或三路划分，而不是 sort。

5. 实测踩坑记录：六个浪费过我时间的 bug 复盘

下面这些坑每一个都让我至少浪费过半小时以上，写出来当反面教材。

坑一：Python 递归栈溢出。手写快排/归并用递归实现时，数据量到十万以上，默认递归深度会爆。解决办法不是改迭代，而是先想清楚这题是否真的需要手写完整排序，还是只用到排序思想。真正需要时，用sys.setrecursionlimit提高上限，或者改迭代版本。

坑二：快排固定 pivot 退化。这个前面说过，最直观的复现方式是拿一个已经升序的数组去跑固定选第一个元素的快排，你会看到递归深度接近 n，栈直接崩掉。复现一次之后，你就再也不会省随机化那行代码了。

坑三：比较器返回值符号搞反。Java 里compare(a, b)返回负数表示 a 在前，C++ 里返回 true 表示 a 在前，Python 的 key 是升序，cmp_to_key是负数在前。三个语言三个规则，混着刷题时特别容易串。我现在的习惯是每道自定义排序题，先写一个小测试用例验证排序方向，确认无误再进入主体逻辑。

坑四：相等元素处理不当导致死循环。快排的 partition 里，如果判断条件写成严格的<和>而不是<=和>=，两个指针在遇到相等元素时可能互相穿越，陷入死循环。这个 bug 的诡异之处在于，普通数据上可能跑得好好的，只有出现大量重复元素时才炸。

坑五：依赖排序稳定性。前面说过的稳定性陷阱。我印象最深的一次是写一个按第二关键字升序、第一关键字降序的排序，只写了第一关键字降序，以为稳定排序会保留第二关键字的原始顺序，结果数据预处理时顺序已经被动过，全盘皆输。从此我养成了"比较器必须完整表达所有排序条件"的习惯。

坑六：整数拼接溢出。最大数那类题，用整数比较x + y与y + x，值一大就溢出。这个坑的隐蔽之处在于，小数据测试都可能通过，只有当测试用例里出现接近 int 上限的数字时才崩。排查的方法很简单：把比较逻辑改成字符串之后，问题立刻消失。

6. 一条能直接照抄的排序题刷题路线

6.1 第一阶段：把手写模板练成条件反射

建议花一到两周，只做四件事：手写快排、手写归并、手写堆排、手写链表归并。每天一遍，直到不需要看参考代码。判断标准是：随便给你一个随机数组，你能在十分钟内把快排写对，并且能解释清楚为什么随机化 pivot、为什么内层循环的符号要这样写。

这个阶段不需要刷太多题，核心是把"手写排序"的肌肉记忆建立起来。写完之后用 Python 的sorted或 C++ 的std::sort对拍，任何不一致就逐行检查。

6.2 第二阶段：按题型专项突破

接下来两三周，按题型刷，而不是按标签刷：

• 自定义排序：最大数、按身高重建队列、根据频率排序这类型；
• 区间问题：合并区间、插入区间、无重叠区间；
• TopK 类：第 K 大、前 K 高频、数据流中位数；
• 链表排序：排序链表、对链表插入排序；
• 计数/桶思想：颜色分类、数组中的逆序对、第一个缺失的正数。

每做完一类，停下来总结一下"这类题共同依赖了排序的哪个特性"。你会发现自定义排序类依赖比较器的正确性，区间类依赖左端点有序后的线性扫描，TopK 类依赖堆或 partition。总结出这个规律，比刷十道题都有用。

6.3 第三阶段：模拟面试里讲清楚排序题

刷题和面试是两回事。面试官让你手写快排时，真正考察的是你能不能讲清楚三件事：为什么平均是 O(n log n)、为什么最坏会退化、怎么规避退化。让你写自定义排序时，考察的是比较器的完整性和边界处理。

我的建议是找一道你做过的排序题，用手机录音，给自己讲解一遍完整思路：先讲暴力解，再讲优化点，再讲复杂度，最后讲边界用例。听一遍回放你会惊讶于自己表达得有多啰嗦。练几次之后，面试时就能做到"代码没写，思路已经讲完了"。

6.4 我的个人习惯

最后分享一个我坚持了很久的习惯：每周挑一个晚上，不借助任何资料，白板手写一遍三大排序模板，再随机挑一道本周刷过的排序变形题重新做一遍。这个动作坚持了两个月之后，排序题基本不会再因为"代码不熟"或"边界没想清"而出错。刷题这事，数量当然重要，但把一类题吃透、把背后的思维迁移出来，才是真正能带到工作里的能力。