1. 为什么排序算法题刷了那么多遍面试时还是心里没底先聊个现象很多人刷排序题的方式是背代码。背快排、背归并、背堆排默写出来没问题但面试官一换问法就发懵。比如他问你这个排序稳定吗为什么数据基本有序时选哪个排序大数据量下怎么排序——这些问题其实比手写算法更常考。排序算法之所以是面试和笔试的常客是因为它不只是考你会不会写代码而是考三件事能不能分清每种排序的时间复杂度、空间复杂度、稳定性这些基本特性能不能根据数据特征规模大小、是否基本有序、取值范围、内存限制选择合适算法能不能在考察工程能力的题目里把排序思想灵活迁移比如求 TopK、合并有序数组、判断数组是否重复等。所以这篇文章不再列那些第一轮冒泡、第二轮冒泡的纯理论讲义而是用练习题解答的形式把排序算法里最常见的题型、最容易踩的坑、以及推导过程一次说透。题目难度从基础到进阶每道题都按审题思路 → 关键推导 → 参考代码 → 易错点的顺序展开。适合准备校招笔试、社招面试算法题或者正在补算法基础的开发者参考。套话不多说直接进题。2. 先搭好框架排序问题的一条主线、两把尺子、三类题在开始刷题之前我们需要把排序算法的知识底子打好。不然题目解答会变成就题论题换个壳你又不会了。2.1 一条主线排序的思想只有四类我总结的排序算法的核心思想就四类其余都是它们的变体比较交换类冒泡、选择、插入、快排、堆排。核心是两两比较按大小交换位置分治合并类归并排序、快排也算。核心是把问题拆小解决完再合并插入维护类直接插入、希尔排序。核心是维护一个有序区不断把新元素插入到正确位置非比较类计数排序、桶排序、基数排序。核心是利用数据本身的特征分布、范围放置元素不做比较。做题之前先判断这个题属于哪一类思路就顺了一半。2.2 两把尺子复杂度和稳定性复杂度不多说了所有算法题都会用到。我重点提醒稳定性这个容易被忽略的点。排序算法稳定的意思是如果两个元素值相等排序后它们的相对次序不变。什么时候必须考虑稳定性举一个最典型的场景按成绩排序成绩相同的人再按学号排序。如果先按学号排好再按成绩做一个稳定排序同分的人学号自然还是有序的。但如果你用不稳定的快排第二次排序可能会打乱学号次序。三个关键记忆选择排序、快排、堆排、希尔排序不稳定冒泡、插入、归并、计数、桶、基数稳定想要稳定的排序手写时优先考虑归并因为它的合并过程天然能保持相对次序。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) 时间内取出最小值并重新调整。整体流程是把 K 个链表的头结点都放入一个小顶堆每次从堆顶弹出最小值节点连到结果链表尾部如果被弹出的节点还有下一个节点把下一个节点压入堆中重复直到堆为空。参考代码import heapq class ListNode: def __init__(self, val0, nextNone): 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 思想的直接延伸。核心逻辑每次 partition 后基准值的位置 p 就是最终排序位置如果 p 正好等于要找的位置升序下的len-K则基准值就是答案如果目标在 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 题目710亿条记录如何排序谈谈外部排序的思想题目描述内存只有 1GB但需要把 10GB 的记录按某个字段升序排列请描述你会怎么做。审题思路这题属于海量数据排序类考的是外部排序的思路。完整实现没必要写在笔试里但思路要清晰。核心是分而治之 归并把大文件切分成多个能装入内存的小块比如每次读 500MB每个小块在内存里用快排或归并排序排好写回磁盘形成有序区段多路归并所有有序区段用堆小顶堆维护每个区段当前的最小值边取边写最终生成全局有序文件。关键点排序阶段内存内排序用快排即可也可以用归并差别不大归并阶段需要用多路归并代替两两归并否则磁盘 IO 太频繁耗时成倍上升。K 路归并时用 K 大小的小顶堆把每次选最小值的比较代价从 O(K) 降到 O(log K)IO 优化外部排序的性能瓶颈在磁盘读写不在 CPU。面试时如果能提到每次输入缓冲和输出缓冲尽量加大说明你有实际经验。易错点这是我最想强调的地方很多人会答用桶排序或用哈希分桶但这两种方案都要求数据分布均匀且有明确的桶划分依据。如果记录字段无法直接映射到桶位置还是得走切块归并的通用方案。先排序切块再归并不但逻辑简单而且适用于任意数据分布。经验补充这个题还有一种变体统计海量数据中出现频率最高的 K 个词。思路更偏向哈希分桶先哈希到多个小文件每个文件内统计频率再用堆取每个文件的 TopK最后归并出全局 TopK。注意这两类题目的本质区别一个是排序本身一个是频次统计后排序不要答串了。5.3 题目8为什么工程上的排序不写教科书快排很多练过排序的人看到底层排序实现时会很疑惑JDK 里Arrays.sort()对基本类型用的是双轴快排对对象类型用的是 TimSortCstd::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)。这些直接决定算法选型。第二步选算法。我用一个简单的决策逻辑条件组合推荐算法数据量小如 n 1000插入排序数据基本有序插入排序要求稳定且时间 O(n log n)归并排序数据量大、无额外空间要求快排数据量大、不允许最坏退化堆排 / IntroSort 混合数据范围小整数计数排序 / 桶排序 / 基数排序内存有限、数据规模超大外部排序分块 归并第三步写代码并自查。写完代码之后用[3, 1, 2]和一个包含重复元素的用例[2, 2, 1]在脑子里跑一遍。重点检查三件事递归出口是否正确、循环里是否可能出现无限循环、等号是否写对影响稳定性。这三步做完再提交基本不会在细节上丢分。说实话排序算法是算法题里最公平的题型之一——它不依赖复杂的数学背景只要把思想弄懂、把几个模板代码写顺剩下的变体都是纸老虎。我自己的经验是把所有排序算法按复杂度表格 代码模板 适用场景做成一个笔记考前看一遍笔试直接默写。希望这篇文章也能成为你的那份笔记。如果你练题过程中遇到了某个具体排序题卡了壳欢迎留言聊具体的坑我们继续拆。
