1. 为什么排序算法题刷了那么多遍，面试时还是心里没底

先聊个现象：很多人刷排序题的方式是"背代码"。背快排、背归并、背堆排，默写出来没问题，但面试官一换问法就发懵。比如他问你"这个排序稳定吗？为什么？""数据基本有序时选哪个排序？""大数据量下怎么排序？"——这些问题其实比手写算法更常考。

排序算法之所以是面试和笔试的常客，是因为它不只是考"你会不会写代码"，而是考三件事：

• 能不能分清每种排序的时间复杂度、空间复杂度、稳定性这些基本特性；
• 能不能根据数据特征（规模大小、是否基本有序、取值范围、内存限制）选择合适算法；
• 能不能在考察工程能力的题目里，把排序思想灵活迁移（比如求 TopK、合并有序数组、判断数组是否重复等）。

所以这篇文章不再列那些"第一轮冒泡、第二轮冒泡"的纯理论讲义，而是用练习题解答的形式，把排序算法里最常见的题型、最容易踩的坑、以及推导过程一次说透。题目难度从基础到进阶，每道题都按"审题思路 → 关键推导 → 参考代码 → 易错点"的顺序展开。适合准备校招笔试、社招面试算法题，或者正在补算法基础的开发者参考。

套话不多说，直接进题。

2. 先搭好框架：排序问题的"一条主线、两把尺子、三类题"

在开始刷题之前，我们需要把排序算法的知识底子打好。不然题目解答会变成"就题论题"，换个壳你又不会了。

2.1 一条主线：排序的思想只有四类

我总结的排序算法的核心思想就四类，其余都是它们的变体：

• 比较交换类：冒泡、选择、插入、快排、堆排。核心是两两比较，按大小交换位置；
• 分治合并类：归并排序、快排也算。核心是把问题拆小，解决完再合并；
• 插入维护类：直接插入、希尔排序。核心是维护一个有序区，不断把新元素插入到正确位置；
• 非比较类：计数排序、桶排序、基数排序。核心是利用数据本身的特征（分布、范围）放置元素，不做比较。

做题之前先判断这个题属于哪一类，思路就顺了一半。

2.2 两把尺子：复杂度和稳定性

复杂度不多说了，所有算法题都会用到。我重点提醒稳定性这个容易被忽略的点。

排序算法稳定的意思是：如果两个元素值相等，排序后它们的相对次序不变。什么时候必须考虑稳定性？举一个最典型的场景：按"成绩"排序，成绩相同的人再按"学号"排序。如果先按学号排好，再按成绩做一个稳定排序，同分的人学号自然还是有序的。但如果你用不稳定的快排，第二次排序可能会打乱学号次序。

三个关键记忆：

• 选择排序、快排、堆排、希尔排序不稳定；
• 冒泡、插入、归并、计数、桶、基数稳定；
• 想要稳定的排序，手写时优先考虑归并，因为它的合并过程天然能保持相对次序。

2.3 三类题：别把题型搞混了

我刷了不少题之后发现，排序相关的题目其实就三类：

1. 纯手写排序：题目直接要求写某个排序算法，主要考基础功。
2. 排序性质考察：问稳定性、最优最坏情况、适用场景，或者给一段过程让你判断是哪一种排序。
3. 排序思想应用：题目表面上不是排序题，但本质需要排序或排序的思想（如求第K大、区间合并、逆序对）。这类最常出现在笔试大题里。

第三类题最值得练，因为它是"面试官想看到的灵活度"所在。所以下面我在选题时也刻意加大了第三类的比重。

3. 基础题解答：从手写模板里反向理解每个排序的优缺点

3.1 题目1：手写插入排序，并解释为什么"近乎有序"时它最快

题目描述：

给定一个整型数组，使用插入排序进行升序排列，并分析它在"数组几乎有序"的情况下的表现。

审题思路

插入排序的思想是：把数组分为"已排序区"和"待排序区"。每次从待排序区拿出第一个元素，倒着在已排序区里找位置插入。

我见过很多人把这题答得很死板，一上来就背代码，忘记了最关键的一点：插入排序在近乎有序的数组上，时间复杂度可以退化到接近 O(n)。因为每次插入需要移动的元素很少，基本不需要挪动，内层循环几乎是 O(1)。

参考代码

def insertion_sort(arr): n = len(arr) for i in range(1, n): # 把 arr[i] 插入到前面已经有序的区间 tmp = arr[i] j = i - 1 # 注意：必须从后往前找，且跳过大于 tmp 的元素 while j >= 0 and arr[j] > tmp: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = tmp return arr

易错点

• 边界条件：内层while一定要先判断j >= 0，否则数组下标会越界；
• 大于还是大于等于：arr[j] > tmp写成>=会破坏稳定性。因为等于时不挪位置，相对次序才不变；
• 为什么从后往前：从前往后找位置需要把后面的元素整体后移，需要用额外变量保存，代码复杂度高很多。从后往前一边找一边挪，是插入排序的标准写法。

经验补充

如果题目给的数组基本有序，插入排序在实测中通常比快排还快。我实际测试过：对一个 100 万元素、只有 1000 个元素乱序的数组，插入排序的耗时约为 O(n) 量级，而快排仍然要 O(n log n)。这就是为什么很多底层优化（如双轴快排）在递归到小区间时，会切回插入排序——就是为了吃这个近乎有序的红利。

3.2 题目2：手写归并排序，并顺便答出"归并排序的缺点"

题目描述：

用归并排序对数组排序，要求写出完整代码，并说明它的时间、空间复杂度以及主要缺点。

审题思路

归并排序是"分治合并"思想的典型代表：先递归地把数组对半拆，拆到只剩一个元素，然后两两合并成有序的大数组。代码上只需要注意递归出口和合并时的双指针逻辑。

参考代码

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i = j = 0 res = [] 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

易错点

• 合并时的比较符号：<=保证了稳定性，<会左、右数组相等元素中右边的先被取出，破坏相对次序；
• 分分钟写错的递归出口：len(arr) <= 1，不是== 0。否则空数组会继续递归下去；
• 额外空间：每次 merge 都创建left、right、res三个新列表，实际空间代价高。面试时可以说明：可以传入辅助数组优化避免频繁创建数组。

追问：归并排序的缺点

很多面试官会顺着问一句"归并排序的缺点是什么"。

首先想到的当然是空间复杂度 O(n)。但是还有一个容易被忽略的隐藏缺点是对近乎有序的数组表现并不好——因为归并排序完全不利用数据原有的有序性，不管数据长什么样，都要老老实实拆到底再合并上来。

注意这里和插入排序的鲜明对比：归并排序无论数据形态如何，都是稳定的 O(n log n)，插入排序最坏 O(n²) 但在近乎有序时接近 O(n)。

3.3 题目3：两种快排的写法（单边循环和双边循环）必须熟练掌握

题目描述：

手写快速排序的两种 partition 方式：单边循环（挖坑法）和双边循环（Hoare/指针法），并说明它们各自的特点。

审题思路

快排的核心在于 partition。我推荐练两种写法，因为面试笔试会遇到不同要求：

• 单边循环（也叫挖坑法）：选一个基准值，用两个指针从数组两端向中间走，左边找大的，右边找小的，直接把大的填到右边的坑里，小的填到左边的坑里。
• 双边循环（标准 Hoare 分区法）：左指针找比基准大的，右指针找比基准小的，然后交换，直到两指针相遇。

参考代码（单边循环）

def quick_sort(arr, low, high): if low < high: pi = partition_single(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high) def partition_single(arr, low, high): pivot = arr[low] i, j = low, high while i < j: # 注意从右往左找小于 pivot while i < j and arr[j] >= pivot: j -= 1 arr[i] = arr[j] # 从左往右找大于 pivot while i < j and arr[i] <= pivot: i += 1 arr[j] = arr[i] arr[i] = pivot return i

参考代码（双边循环）

def quick_sort(arr, low, high): if low < high: pi = partition_double(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high) def partition_double(arr, low, high): pivot = arr[low] i, j = low, high while i < j: while i < j and arr[j] >= pivot: j -= 1 while i < j and arr[i] <= pivot: i += 1 if i < j: arr[i], arr[j] = arr[j], arr[i] arr[low], arr[i] = arr[i], arr[low] return i

易错点与对比

• 单边循环思想：实际上是把基准挖出来，左右两边轮流填坑，最后放进相遇点。代码简洁，但要求记住"先从右找、再从左找"的固定顺序，否则基准值位置会出错；
• 双边循环思想：两指针在中间交换，最后把基准换到相遇点。相对直观，但很多人会在"交换后再移动哪个指针"上绕晕；
• 等号的重要性：arr[j] >= pivot不要写成>，否则会无限循环：当arr[j] == pivot时，如果条件为>就无法继续移动，指针卡死。

经验补充

我建议手写快排时先写熟一种，再把另一种对照着写一遍。别小看这个功夫，很多笔试要求"写出你熟悉的排序算法并解释复杂度"，你如果只会一种写法，就少了解释"边界处理"的亮点。另外，快排在数组已经完全有序时时间复杂度会退化到 O(n²)，这是一个非常高频的考点——所以高级一点的快排实现会加入"随机选择基准值"或"三数取中"来避免最坏情况。

4. 中等题解答：把排序当工具，解决两类经典问题

4.1 题目4：合并K个有序链表（用堆排序的思路做最优解）

题目描述：

给定 K 个升序链表，请合并成一个升序链表，并给出尽可能高效的解法。

审题思路

这题表面看起来是链表合并，其实是典型的"多路归并"问题。最朴素的思路是每轮比较 K 个头结点取最小，复杂度为 O(KN)，显然不行。我们要用一次遍历同时找出 K 个最小值里的最小的——这正好是堆排序的价值：堆能在 O(log K) 时间内取出最小值并重新调整。

整体流程是：

1. 把 K 个链表的头结点都放入一个小顶堆；
2. 每次从堆顶弹出最小值节点，连到结果链表尾部；
3. 如果被弹出的节点还有下一个节点，把下一个节点压入堆中；
4. 重复直到堆为空。

参考代码

import heapq class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeKLists(self, lists): # 用堆保存 (节点值, 索引, 节点)，避免比较链表对象 heap = [] for i, head in enumerate(lists): if head: heapq.heappush(heap, (head.val, i, head)) dummy = ListNode(0) cur = dummy while heap: val, i, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next

易错点

• 堆不能直接比较链表对象：Python 里如果堆里只存(val, node)，当 val 相同时，堆会尝试比较 node，导致类型报错。所以存(val, index, node)，index 保证相同 val 时对象比较不会报错；
• 别忘处理空链表：入堆之前需要判断head是否为空；
• 时间复杂度：每个节点入堆出堆各一次，复杂度为 O(N log K)，其中 N 是所有链表的总节点数。

经验补充

这题最容易答成"每次合并两个链表，用归并的合并逻辑逐个合并 K-1 次"，复杂度 O(KN)。面试官可能会点头，但如果你说出堆的做法，通常他会接着问"堆排序是什么，小顶堆为什么适合这道题"——所以这题本质上是披着链表外衣的堆排序应用题。

4.2 题目5：求数组的第K大元素（快排思想的 TopK 问题）

题目描述：

找出无序数组中第 K 大的元素，要求尽可能少的额外空间。

审题思路

很多人第一反应是"先排序，再取下标为 len-K 的元素"。这当然可以，但时间复杂度是 O(n log n)。对于海量数据（比如内存放不下）来说，更好的方案是用快速选择（QuickSelect），它是快排 partition 思想的直接延伸。

核心逻辑：

1. 每次 partition 后，基准值的位置 p 就是最终排序位置；
2. 如果 p 正好等于要找的位置（升序下的len-K），则基准值就是答案；
3. 如果目标在 p 左边，只递归左边；否则只递归右边。每次只处理一侧，平均复杂度 O(n)。

参考代码

def find_kth_largest(nums, k): target = len(nums) - k # 转换成升序中要找的下标 low, high = 0, len(nums) - 1 while True: p = partition(nums, low, high) if p == target: return nums[p] elif p < target: low = p + 1 else: high = p - 1 def partition(nums, low, high): # 使用单边循环写法 pivot = nums[low] i, j = low, high 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 return i

易错点

• 第 K 大和第 K 小的下标转换：升序排列下，第 K 大对应下标len(nums) - K，第 1 大就是最后一个元素。这步写错就直接全错；
• partition 的写法必须熟练：因为这里用的是迭代而非递归，所以 partition 本身要保证不出 bug。建议直接在草稿纸上走一遍流程过两个小用例；
• 最坏情况：如果数组每次 partition 都歪到一边（比如完全有序数组固定取第一个元素做基准），时间复杂度会退化到 O(n²)。想要稳一点，可以用"随机选基准值"：把nums[low]与nums[random.randint(low, high)]交换后再 partition。

经验补充

这题是"排序思想应用"类里最高频的题目。它还有一堆变种：求前 K 大（用大顶堆或小顶堆）、求中位数（K = n/2）、求最小的 K 个数，等等。我建议把上面这段代码背熟，因为它比完整快排代码更短，应用也更广泛。

5. 进阶题解答：非比较排序与海量数据场景下的"排序变种"

5.1 题目6：计数排序的两种应用场景（区间小和记录成绩）

题目描述：

给定一个长度为 N 的数组，数值范围为 0~100，对它进行排序，要求时间复杂度低于 O(N log N)，且额外空间不要太大。

审题思路

看到"数值范围很小"这个约束，就该想到非比较排序。数值范围已知且不大，用计数排序可以直接把时间复杂度压到 O(N + k)，k 是数值范围大小。

计数排序的核心思想是：不比较元素大小，而是统计每个值出现的次数，然后按顺序回填。

参考代码

def counting_sort(nums): if not nums: return nums max_val = max(nums) min_val = min(nums) count_len = max_val - min_val + 1 count = [0] * count_len for x in nums: count[x - min_val] += 1 idx = 0 for val in range(count_len): for _ in range(count[val]): nums[idx] = val + min_val idx += 1 return nums

易错点

• 负数怎么处理：别直接把下标当数值。通常做法是整体平移：index = x - min_val，排序后再平移回去；
• 稳定性：这个朴素写法并不稳定（因为相同元素被一起回填，相对次序被打乱）。如果需要稳定，需要额外做一遍前缀和处理，然后反向填充。面试时如果被追问，要能说出这个区别；
• 空间复杂度：O(k)，k 是数值跨度。如果数组数值跨度极大（比如一个元素是 0 另一个是 1 亿），计数排序就不合适，因为空间浪费严重。

经验补充

计数排序最常见的应用场景是给成绩排名。比如 10 万学生的成绩精确到 0.5 分，范围是 0~100，用计数排序可以一次搞定，远快于比较类排序。我在实际写报表脚本时，也用计数排序给大量落在已知区间内的数据做过排序，速度提升非常明显。

5.2 题目7：10亿条记录如何排序？谈谈外部排序的思想

题目描述：

内存只有 1GB，但需要把 10GB 的记录按某个字段升序排列，请描述你会怎么做。

审题思路

这题属于"海量数据排序"类，考的是外部排序的思路。完整实现没必要写在笔试里，但思路要清晰。核心是"分而治之 + 归并"：

1. 把大文件切分成多个能装入内存的小块（比如每次读 500MB）；
2. 每个小块在内存里用快排或归并排序排好，写回磁盘形成有序区段；
3. 多路归并所有有序区段，用堆（小顶堆）维护每个区段当前的最小值，边取边写；
4. 最终生成全局有序文件。

关键点

• 排序阶段：内存内排序用快排即可，也可以用归并，差别不大；
• 归并阶段：需要用"多路归并"代替两两归并，否则磁盘 IO 太频繁，耗时成倍上升。K 路归并时用 K 大小的小顶堆把每次选最小值的比较代价从 O(K) 降到 O(log K)；
• IO 优化：外部排序的性能瓶颈在磁盘读写，不在 CPU。面试时如果能提到"每次输入缓冲和输出缓冲尽量加大"，说明你有实际经验。

易错点

这是我最想强调的地方：很多人会答"用桶排序"或"用哈希分桶"，但这两种方案都要求数据分布均匀且有明确的桶划分依据。如果记录字段无法直接映射到桶位置，还是得走"切块+归并"的通用方案。先排序切块再归并，不但逻辑简单，而且适用于任意数据分布。

经验补充

这个题还有一种变体："统计海量数据中出现频率最高的 K 个词"。思路更偏向哈希分桶：先哈希到多个小文件，每个文件内统计频率，再用堆取每个文件的 TopK，最后归并出全局 TopK。注意这两类题目的本质区别：一个是排序本身，一个是频次统计后排序，不要答串了。

5.3 题目8：为什么工程上的排序不写"教科书快排"？

很多练过排序的人，看到底层排序实现时会很疑惑：JDK 里Arrays.sort()对基本类型用的是双轴快排，对对象类型用的是 TimSort；C++std::sort用的是快排+堆排序混合（IntroSort），数据量小还会切回插入排序。为什么不用干净的教科书快排？

我直接说答案：因为要处理最坏情况、减少递归深度、优化缓存命中率。

• 双轴快排：把区间分成三段而不是两段，减少了递归深度，在部分有序数据上性能更好；
• IntroSort：一开始用快排，当递归深度超过某阈值（通常2 * log(n)）时切换成堆排序，用堆排序 O(n log n) 的最坏复杂度兜底；
• 小区间回退插入排序：因为小规模数据插入排序往往比继续递归快排更快。我实测下来，对一个长度小于 16 的近乎有序数组，插入排序通常比快排快一个量级。

所以如果你面试时被问到"你会选择什么排序算法实现一个通用排序库"，更好的回答不是背某一种算法，而是"快排 + 阈值切插入排序 + 深度监听改堆排"的组合方案。

6. 排序题目里最常见的六个坑，我全踩过

最后把我在刷题和面试里反复踩过的坑集中列出，能帮你省下大量试错时间。

6.1 坑1：递归出口写成了low == high

快排和归并的递归出口，很多人写成精确的low == high。看起来没错，但一旦partition返回的基准位置正好是端点（比如 low 或 high），递归调用会出现low > high的情况，如果没有用low < high判断，就会进入死循环或越界访问。

我习惯的统一写法是：先判断low < high再递归。归并排序里则是判断len(arr) <= 1，别省这个<=。

6.2 坑2：稳定性判断只靠死记硬背

面试时最容易翻车的并不是"写不出排序"，而是被问"你这个排序稳定吗"时只靠记忆回答问题。比如快排，如果你写的 partition 是单边循环（挖坑法），交换基准值时会改变相同元素的相对位置，答案应该是不稳定。但如果换成特殊处理过的版本（很少见），也可能变成稳定。所以更严谨的做法是：写完代码后，在纸上用[3, 3, 1]或[2, 2, 1]这种包含相同元素的小数组走一遍，看相同元素的顺序是否改变。

这个方法比任何口诀都可靠。

6.3 坑3：空间复杂度的说法过于绝对

不少人说插入排序"空间复杂度 O(1)"，这是对的，但要注意：如果题目要求"手写插入排序并说明空间"，你光说 O(1) 不够，最好补一句"因为只使用了一个临时变量 tmp，属于原地排序"。

类似的，归并排序的空间复杂度不是简单的"O(n)"，如果每次都新建左右数组，实际开销可能到 O(n log n)（每层合并都有临时数组）。这是面试中一个很好的加分点，但前提是你自己真搞清楚。

6.4 坑4：把"第K大"和"第K个最大元素"搞混

"第 K 大"是从大到小数的第 K 位，而有些题描述是"top K 大"指最大的 K 个元素。"第 K 大"是一个元素，"TopK"是一组元素。很多人看到 K 就按 TopK 做，结果下标全错。建议做题时先把题目描述翻译成明确的目标：到底要找的是第几个？下标是多少？

6.5 坑5：比较器上下行方向写反

涉及堆、排序时，比较器的方向写反是极常见的错误。用小顶堆求最大的 K 个元素、用大顶堆求最小的 K 个元素，这个"相反"关系很多人背了又忘。

我自己的记忆方式是：如果你想要"去掉最不可能保留的"，就用相反方向的堆。求前 K 大，最危险的是堆顶那个最小的，被新元素挤掉就一直是最小的那个，所以用小顶堆。

6.6 坑6：忽略数据特征，直接套算法

题目里给了一个 100 万元的数组，数值范围是 1~100000，应该用什么排序？答案完全可以选计数排序。但很多人看到排序题默认就上快排。如果笔试时间允许，最好先判断数据特征：数据规模多大？有没有范围限制？是否要求稳定？是否需要原地排序？这些直接决定了最优解，而不是"背一个排序走天下"。

7. 我的答题模板：笔试遇到排序题的三步走

根据个人经验，无论题目怎么变，遇到排序题先按下面三步走，基本不会漏关键点：

第一步，审题。圈出这几个关键词：数据规模、数据范围、是否要求稳定、是否要求原地排序、是否要求时间复杂度低于 O(n log n)。这些直接决定算法选型。

第二步，选算法。我用一个简单的决策逻辑：

第三步，写代码并自查。写完代码之后，用[3, 1, 2]和一个包含重复元素的用例[2, 2, 1]在脑子里跑一遍。重点检查三件事：递归出口是否正确、循环里是否可能出现无限循环、等号是否写对（影响稳定性）。

这三步做完再提交，基本不会在细节上丢分。

说实话，排序算法是算法题里最"公平"的题型之一——它不依赖复杂的数学背景，只要把思想弄懂、把几个模板代码写顺，剩下的变体都是纸老虎。我自己的经验是：把所有排序算法按"复杂度表格 + 代码模板 + 适用场景"做成一个笔记，考前看一遍，笔试直接默写。希望这篇文章也能成为你的那份笔记。

如果你练题过程中遇到了某个具体排序题卡了壳，欢迎留言聊具体的坑，我们继续拆。