有没有过这种经历第二天就要面试了晚上突然想起来排序算法还没系统过一遍。平时刷过不少题但真要自己在白板上手写一个快速排序写到一半就开始犹豫基准元素到底怎么放、递归边界怎么处理。说实话这种忐忑太正常了因为排序算法这一块光看教程和收藏夹文章是真的不顶用必须手写、必须理解每一个选择背后的原因。这篇文章就是为这个场景准备的“临时抱佛脚手册”。目标非常纯粹用最短的时间把面试里最高频的排序算法考点一次性理清楚。不管是明天面试还是最近一周内要面花一晚上把下面的内容吃透重点代码手写两遍到了现场至少不会被“手写一个快排”这种题直接卡住。内容也适合工作多年、平时写业务代码多一点、一说到基础就心里发虚的工程师用来把底子补一补。1. 面试前先想明白排序算法到底在考什么1.1 面试官为什么反复问排序排序算法是计算机科学里最经典的一类问题它体量小但足够在十几分钟的面试过程中暴露一个人的代码功底。面试官在看你手写排序时真正在看的东西往往有几层数组索引的边界处理清不清楚、循环条件会不会差一、对复杂度的分析是背出来的还是真理解了、以及遇到特殊场景能不能主动调整方案。我见过不少候选人排序模板背得很熟但一被问“这个算法为什么不稳定”就卡住。原因很简单因为只背了代码没有理解机制。面试官问排序并不是真的要用你的排序代码去跑业务而是通过这一段代码快速判断你的工程直觉、基础扎实程度和临场分析能力。所以准备的重点不要放在“我会背多少种排序”而是要放在“我能不能把每一种排序的取舍讲清楚”。1.2 一张表背熟复杂度与稳定性面试前最优先要做的事不是急着写代码而是先把下面这张复杂度与稳定性对照表刻进脑子里。这张表几乎覆盖了面试里九成的排序算法基础题。排序算法最好时间复杂度平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序O(n log n)O(n^1.3)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定基数排序O(d(n r))O(d(n r))O(d(n r))O(n r)稳定记忆方法我可以提供一个自己一直在用的口诀稳定的是“冒插归计基”冒泡、插入、归并、计数、基数不稳定的是“希快选堆”希尔、快速、选择、堆。面试的时候被问到稳定性先讲出分组再展开原因基本就不会乱。这张表的额外空间一栏必须注意区分快排的 O(log n) 来自递归调用栈归并的 O(n) 来自合并时的临时数组堆排序是原地排序所以是 O(1)。这三点是追问率最高的地方。1.3 手写代码前的基本功比较与交换排序算法的手写代码本质上只有两个动作在反复出现比较和交换。但最基础的东西反而是最容易在紧张时翻车的地方。比如交换两个数组元素很多人在真正手写时会直接写出类似a, b b, a的高级语法其实这在面试白板上不是不行但要看你投的岗位对语言的要求。保险起见写一个多数场景都认的版本temp arr[i] arr[i] arr[j] arr[j] temp再有就是边界条件。写任何排序代码之前先问自己三个问题数组为空或只有一个元素时代码会不会索引越界数组里有重复元素时交换会不会打乱逻辑题目要求升序还是降序所有的比较符号是不是保持了一致。这三个问题看着简单但面试现场一紧张真的非常容易掉进去。2. 决胜基础三件套冒泡、选择、插入2.1 冒泡排序最不该写错的送分题冒泡排序的原理一句话就能说清每一轮从头到尾比较相邻元素把当前最大或最小的值一路交换到数组尾部。重复 n - 1 轮之后数组就排好了。面试官往往用它来热身实际上就是想看候选人能不能把这段代码写得干净、高效。很多人在写冒泡时内层循环边界喜欢写for j in range(n - 1)不去管前面已经排好的元素。这样结果虽然对但做了大量无效比较。更好的写法是让内层循环随着轮次递减def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果本轮没有发生交换说明数组已经有序 if not swapped: break return arr这里有个小细节值得拿出来讲swapped这个标志位就是常说的提前退出优化。最坏情况下它不改变 O(n²) 的复杂度但如果数据已经接近有序它能在一两轮扫描后直接结束最好情况下时间复杂度会降到 O(n)。面试官一眼看到这个标志位通常会觉得你写过真正的代码而不只是背过模板。2.2 选择排序交换次数最少的排序选择排序的思路比冒泡更直接每一轮从未排序区间里挑出最小值把它放到已排序区间的末尾。代码写出来是这样def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这个算法的优势在于交换次数非常少最多只有 n - 1 次交换。如果待排序的元素是体积很大的对象交换的代价远高于比较选择排序在简单排序里就更合适。但它的劣势也很明显无论原始数据多么接近有序每一轮都必须完整扫描后面的所有元素所以最好情况也都是 O(n²)。面试里涉及选择排序最常追问的是“为什么它不稳定”。这个问题值得好好准备一下。可以这样解释假设数组是 [5a, 5b, 3]两个相等的 5 本来按顺序排好第一轮找到最小元素 3把它换到开头这个过程中 5a 被迫移动到了原本 3 的位置于是 5a 和 5b 的相对顺序就被打破了。选择排序的跳跃式交换正是它不稳定性的根源。2.3 插入排序对“几乎有序”数据最友好的简单排序插入排序的原理很多人一上手就懂就像整理扑克牌从第二张开始每次把当前牌插入到前面已经排好的牌序列中。def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr这段代码有一个非常容易写错的细节内层循环比较的对象是key而不是arr[j 1]。因为arr[j 1]在移动过程中会被覆盖真正要插入的值早就保存在key里了。如果把它写成while j 0 and arr[j] arr[j 1]整个逻辑就会乱掉。插入排序在数据基本有序时表现极好接近 O(n)。这也是为什么一些工程级的排序实现比如复杂混合排序算法中的小数组优化会把阈值以下的子数组改用插入排序来处理。插入排序稳定的原因也值得掌握在循环里用的是严格的大于号只有当前值比 key 大时才把元素后移相等的元素不会跨过彼此因此相对顺序得到保留。3. 进阶四件套希尔、归并、快速、堆3.1 希尔排序插入排序的升级版希尔排序是插入排序的改进版本核心思想是先分组再排序按间隔 gap 把数组拆成若干子序列对每个子序列做插入排序接着缩小 gap重复这个过程直到 gap 等于 1此时数组已经接近有序最后做一次标准插入排序收尾。为什么分组能加速因为插入排序在数据几乎有序时效率最高而希尔排序每轮都在让数据越来越接近有序。gap 较大时元素跨得远可以让大幅值的元素快速移动到靠近最终位置的地方gap 缩小时组内元素变多但此时整体已经比较有序插入排序的代价就低了。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2 return arr如果面试官问“希尔排序为什么不稳定”答案是因为分组插入排序时相等的元素可能被分到不同的子序列它们会被跨组移动相对顺序无法保证。还要知道希尔排序的复杂度依赖 gap 序列常见的折半序列最坏情况下是 O(n²)平均大约 O(n^1.3)。能说出“业界有更好的序列比如 Sedgewick 序列”会是一个不错的加分点但不用展开太多毕竟把代码写对更重要。3.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这段代码里最值得盯住的是合并时的比较条件left[i] right[j]。这个小于等于号就是稳定性的关键当两边元素相等时优先取左侧数组的元素这样相等元素的相对顺序被完整保留。如果这里写成相等元素会被右侧的先取走稳定性就没了。归并排序的缺点是额外空间 O(n)优点是时间稳定在 O(n log n)不依赖输入数据的原始状态。面试中有一个经典变形题合并两个有序数组要求不额外开数组。解法是从两个数组的尾部开始比较较大的放在后面。这个从后往前的双指针写法建议自己推一遍因为它在很多实际场景里真的会用到。3.3 快速排序面试出现率最高务必一次写对快排在面试中的地位不用过多解释手写快排几乎可以算是一道必考题。核心是 partition 过程选一个基准元素把数组分成左边都小于等于基准、右边都大于等于基准的两部分然后递归处理左右子区间。这里我给出最常用的 Lomuto 分区写法以最后一个元素为基准def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1写这段代码最常翻车的地方是 partition 的返回值。i从low - 1开始扫描过程中每遇到一个不大于基准的元素i就加一最终i 1才是基准元素应该去的位置。如果忘记把基准元素交换回arr[i 1]或者返回值算差一位整个排序都会乱掉。快排的平均复杂度是 O(n log n)最坏情况下会退化到 O(n²)。最坏场景通常出现在有序数组上用固定位置选基准时。所以回答时最好主动补充工程实现会使用随机基准或三数取中来规避退化。快排的不稳定同样要会说清楚partition 过程是跳跃式交换相同元素可能在分区时被分到不同的区间相对顺序因此丢掉了。3.4 堆排序TopK 问题的钥匙堆排序利用二叉堆来排序分为两个阶段先自下而上把数组调整成一个大根堆再把堆顶当前最大值与数组末尾交换缩小堆的范围后重新调整重复这个过程直到全部排好。def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n len(arr) # 从最后一个非叶子节点开始建堆 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) return arr索引计算是这段代码最需要记牢的部分下标为 i 的节点左孩子是2 * i 1右孩子是2 * i 2。建堆循环从n // 2 - 1开始因为大于这个下标的节点都是叶子节点没必要调整。堆排序的时间复杂度稳定在 O(n log n)额外空间 O(1)但它属于不稳定排序原因是堆顶与末尾交换时相等元素的相对顺序无法预期。完整手写堆排序在面试里并不算高频但堆的思想会以“TopK 问题”的形式高频出现维护大小为 K 的小顶堆遍历一遍数据堆里留下的就是前 K 个最大值。这个实现建议提前练熟。4. 线性时间排序计数、桶、基数4.1 计数排序范围有限的整数神器计数排序不是基于比较的排序因此它能突破 O(n log n) 的理论下界达到 O(n k)。它的使用前提很明确待排序元素必须是非负整数而且数值范围不能太大否则辅助数组会占用过多空间。思路非常朴素统计每个元素值出现的次数再按数值顺序把元素回填到原数组。def counting_sort(arr, max_val): count [0] * (max_val 1) for num in arr: count[num] 1 idx 0 for i in range(len(count)): while count[i] 0: arr[idx] i idx 1 count[i] - 1 return arr这个写法最简单但严格来说它并不是稳定排序因为只是把相等的值一次性回填没有区分它们原有的先后顺序。如果要写出真正稳定的计数排序思路是先对 count 做前缀和得到一个“每个值最后应该放在输出数组的哪个位置”的映射然后从原数组末尾往前遍历回填。面试里如果被要求讲计数排序的稳定性能把这个前缀和的版本说清楚会显得很有深度。另外如果数组里有负数需要统一加偏移量把最小值变成 0排序完再减回去。这个补充也值得提一句。4.2 基数排序与桶排序海量数据的另类解法基数排序把整数按位拆分从最低位到最高位依次排序每一轮都要求使用稳定排序。它的复杂度是 O(d(n r))其中 d 是最大数的位数r 是基数。我实现时习惯直接基于桶来收集每一轮的结果def radix_sort(arr): if not arr: return arr max_num max(arr) exp 1 while max_num // exp 0: buckets [[] for _ in range(10)] for num in arr: digit (num // exp) % 10 buckets[digit].append(num) arr [num for bucket in buckets for num in bucket] exp * 10 return arr这段代码因为用桶收集天然保证了每轮收集时同一桶内的相对顺序不变即稳定的。它适合数据量大但位数不长且数值非负的场景比如手机号、学号、定长 ID 这类数据。面试中基数排序不常要求手写但能讲出“按位稳定排序”这个核心就够了。桶排序的思路是把数据均匀分到若干桶中每个桶内用其他排序算法或递归桶排序最后按桶顺序把所有元素取出。它的效率取决于桶的分布是否均匀最差情况下所有数据落进同一个桶复杂度退化。实际面试中单独考桶排序的题目不算多但它的思想经常出现在“海量数据求中位数”“大数据量分桶统计”一类题目中理解它的存在价值对于回答这类场景题很有帮助。5. 面试高频变形题5.1 TopK 问题三种解法递进讲TopK 是排序算法相关题目里出现频率最高的一道变形题常见问法是“找出数组中前 K 大的元素”或者“找出第 K 大的元素”。我在辅导别人准备这道题时通常建议按三种解法递进回答。第一种解法最简单全量排序后取前 K 个。时间复杂度 O(n log n)代码量很少但面试官大概率会追问能不能更快。第二种解法是用小顶堆维护一个大小为 K 的小顶堆堆顶是堆中最小的元素。遍历数组一旦遇到比堆顶大的元素就弹出堆顶并插入新元素。遍历结束后堆里的 K 个元素就是前 K 大。时间复杂度 O(n log K)空间 O(K)。当 K 远小于 n 时这个方案比全排序好很多。第三种解法是快选利用快排的 partition一次划分后基准元素所在的位置就是它的排名如果恰好是 K直接返回否则只递归处理包含第 K 大的那一侧。平均时间复杂度 O(n)最坏会退化到 O(n²)需要配合随机基准来规避。这三种解法建议按顺序讲解因为这是一个从“会用排序模板”到“理解排序思想”的递进。很多面试官就会顺着这个递进往下深挖你对 partition 的理解越透后续问题就越稳。5.2 稳定性场景问题排序顺序会不会被覆盖稳定性的概念抽象但面试官通常会用一个具体场景来考有一批员工已经按年龄升序排好现在要求再按薪资降序排序最终的顺序是什么正确答案是如果第二次排序用的是稳定排序结果会先按薪资降序排列薪资相同的员工内部仍然保持年龄升序如果第二次排序不稳定则薪资相同的那批员工顺序可能被重新打乱年龄升序的效果就没了。这个场景其实对应着多级排序的核心逻辑在数据库里执行多字段 ORDER BY 非常常见。理解了这个应用场景再去背稳定性就不容易忘了。面试时如果能主动说出“多级排序时稳定排序可以保证第一关键字排序结果不丢失”会是一个很亮眼的回答。5.3 解一道经典题逆序对计数另一个高频变形题是“求数组中的逆序对数量”。比如数组 [8, 4, 5, 3] 里的逆序对有 (8,4)、(8,5)、(8,3)、(4,3)、(5,3)一共 5 个。暴力解法是双层循环O(n²)面试官听到这个答案后通常会追问有没有更快的办法。更快的方法就是归并排序。在 merge 的过程中当左侧元素大于右侧元素时左侧从当前位置到最后的所有元素都比右侧这个元素大所以它们都构成逆序对。因此只需要在合并时把mid - i 1这个数量累加到计数器里即可。这道题考察的不是背模板而是在熟悉的分治框架里做一点变化。如果你能在手写归并排序的基础上顺带把逆序对计数出来面试官对你的分治理解和代码掌控力都会有很好的印象。这道题我强烈建议在突击阶段亲手实现一次因为它是归并排序出题率最高的变体。6. 突击期的几条实操建议临时抱佛脚阶段最忌讳贪多什么都想抓结果什么都没抓牢。按我的经验看优先级应该是这样冒泡、选择、插入三种基础排序先写熟然后重点死磕快速排序和归并排序堆排序只练关键路径建堆加 heapify。希尔、计数、基数排序认识原理和时间复杂度就够了绝大多数开发岗面试不会要求现场手写这三个除非岗位本身和底层引擎、数据基础设施强相关。手写频率比看代码重要得多。光看模板和口诀是没用的至少要保证快排和归并各完整手写三遍以上。第一次写慢很正常卡住就回去看重要的是每写一遍都要脱离参考代码。写到第三遍基本就能形成肌肉记忆面试现场即使紧张手也不会停。我见过不少候选人复杂度表背得很熟但真正在纸上写代码时不是忘记处理空数组就是分区索引差一位。所以最后想再强调一遍排序算法面试前能快速拉满的就是手写正确率。把那张复杂度表存到手机里每天抽十分钟默写一遍快排和归并三天后的你和现在的你完全是两个水平。面试时只要把核心代码写对了、复杂度讲清了、稳定性原因说透了排序这块基本就不会拖后腿。 
长河君 · 2026/10/14 6:57:49 · 阅读 1.2k 排序算法面试突击：复杂度、稳定性与手写代码全攻略
有没有过这种经历第二天就要面试了晚上突然想起来排序算法还没系统过一遍。平时刷过不少题但真要自己在白板上手写一个快速排序写到一半就开始犹豫基准元素到底怎么放、递归边界怎么处理。说实话这种忐忑太正常了因为排序算法这一块光看教程和收藏夹文章是真的不顶用必须手写、必须理解每一个选择背后的原因。这篇文章就是为这个场景准备的“临时抱佛脚手册”。目标非常纯粹用最短的时间把面试里最高频的排序算法考点一次性理清楚。不管是明天面试还是最近一周内要面花一晚上把下面的内容吃透重点代码手写两遍到了现场至少不会被“手写一个快排”这种题直接卡住。内容也适合工作多年、平时写业务代码多一点、一说到基础就心里发虚的工程师用来把底子补一补。1. 面试前先想明白排序算法到底在考什么1.1 面试官为什么反复问排序排序算法是计算机科学里最经典的一类问题它体量小但足够在十几分钟的面试过程中暴露一个人的代码功底。面试官在看你手写排序时真正在看的东西往往有几层数组索引的边界处理清不清楚、循环条件会不会差一、对复杂度的分析是背出来的还是真理解了、以及遇到特殊场景能不能主动调整方案。我见过不少候选人排序模板背得很熟但一被问“这个算法为什么不稳定”就卡住。原因很简单因为只背了代码没有理解机制。面试官问排序并不是真的要用你的排序代码去跑业务而是通过这一段代码快速判断你的工程直觉、基础扎实程度和临场分析能力。所以准备的重点不要放在“我会背多少种排序”而是要放在“我能不能把每一种排序的取舍讲清楚”。1.2 一张表背熟复杂度与稳定性面试前最优先要做的事不是急着写代码而是先把下面这张复杂度与稳定性对照表刻进脑子里。这张表几乎覆盖了面试里九成的排序算法基础题。排序算法最好时间复杂度平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序O(n log n)O(n^1.3)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定基数排序O(d(n r))O(d(n r))O(d(n r))O(n r)稳定记忆方法我可以提供一个自己一直在用的口诀稳定的是“冒插归计基”冒泡、插入、归并、计数、基数不稳定的是“希快选堆”希尔、快速、选择、堆。面试的时候被问到稳定性先讲出分组再展开原因基本就不会乱。这张表的额外空间一栏必须注意区分快排的 O(log n) 来自递归调用栈归并的 O(n) 来自合并时的临时数组堆排序是原地排序所以是 O(1)。这三点是追问率最高的地方。1.3 手写代码前的基本功比较与交换排序算法的手写代码本质上只有两个动作在反复出现比较和交换。但最基础的东西反而是最容易在紧张时翻车的地方。比如交换两个数组元素很多人在真正手写时会直接写出类似a, b b, a的高级语法其实这在面试白板上不是不行但要看你投的岗位对语言的要求。保险起见写一个多数场景都认的版本temp arr[i] arr[i] arr[j] arr[j] temp再有就是边界条件。写任何排序代码之前先问自己三个问题数组为空或只有一个元素时代码会不会索引越界数组里有重复元素时交换会不会打乱逻辑题目要求升序还是降序所有的比较符号是不是保持了一致。这三个问题看着简单但面试现场一紧张真的非常容易掉进去。2. 决胜基础三件套冒泡、选择、插入2.1 冒泡排序最不该写错的送分题冒泡排序的原理一句话就能说清每一轮从头到尾比较相邻元素把当前最大或最小的值一路交换到数组尾部。重复 n - 1 轮之后数组就排好了。面试官往往用它来热身实际上就是想看候选人能不能把这段代码写得干净、高效。很多人在写冒泡时内层循环边界喜欢写for j in range(n - 1)不去管前面已经排好的元素。这样结果虽然对但做了大量无效比较。更好的写法是让内层循环随着轮次递减def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果本轮没有发生交换说明数组已经有序 if not swapped: break return arr这里有个小细节值得拿出来讲swapped这个标志位就是常说的提前退出优化。最坏情况下它不改变 O(n²) 的复杂度但如果数据已经接近有序它能在一两轮扫描后直接结束最好情况下时间复杂度会降到 O(n)。面试官一眼看到这个标志位通常会觉得你写过真正的代码而不只是背过模板。2.2 选择排序交换次数最少的排序选择排序的思路比冒泡更直接每一轮从未排序区间里挑出最小值把它放到已排序区间的末尾。代码写出来是这样def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这个算法的优势在于交换次数非常少最多只有 n - 1 次交换。如果待排序的元素是体积很大的对象交换的代价远高于比较选择排序在简单排序里就更合适。但它的劣势也很明显无论原始数据多么接近有序每一轮都必须完整扫描后面的所有元素所以最好情况也都是 O(n²)。面试里涉及选择排序最常追问的是“为什么它不稳定”。这个问题值得好好准备一下。可以这样解释假设数组是 [5a, 5b, 3]两个相等的 5 本来按顺序排好第一轮找到最小元素 3把它换到开头这个过程中 5a 被迫移动到了原本 3 的位置于是 5a 和 5b 的相对顺序就被打破了。选择排序的跳跃式交换正是它不稳定性的根源。2.3 插入排序对“几乎有序”数据最友好的简单排序插入排序的原理很多人一上手就懂就像整理扑克牌从第二张开始每次把当前牌插入到前面已经排好的牌序列中。def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arr这段代码有一个非常容易写错的细节内层循环比较的对象是key而不是arr[j 1]。因为arr[j 1]在移动过程中会被覆盖真正要插入的值早就保存在key里了。如果把它写成while j 0 and arr[j] arr[j 1]整个逻辑就会乱掉。插入排序在数据基本有序时表现极好接近 O(n)。这也是为什么一些工程级的排序实现比如复杂混合排序算法中的小数组优化会把阈值以下的子数组改用插入排序来处理。插入排序稳定的原因也值得掌握在循环里用的是严格的大于号只有当前值比 key 大时才把元素后移相等的元素不会跨过彼此因此相对顺序得到保留。3. 进阶四件套希尔、归并、快速、堆3.1 希尔排序插入排序的升级版希尔排序是插入排序的改进版本核心思想是先分组再排序按间隔 gap 把数组拆成若干子序列对每个子序列做插入排序接着缩小 gap重复这个过程直到 gap 等于 1此时数组已经接近有序最后做一次标准插入排序收尾。为什么分组能加速因为插入排序在数据几乎有序时效率最高而希尔排序每轮都在让数据越来越接近有序。gap 较大时元素跨得远可以让大幅值的元素快速移动到靠近最终位置的地方gap 缩小时组内元素变多但此时整体已经比较有序插入排序的代价就低了。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2 return arr如果面试官问“希尔排序为什么不稳定”答案是因为分组插入排序时相等的元素可能被分到不同的子序列它们会被跨组移动相对顺序无法保证。还要知道希尔排序的复杂度依赖 gap 序列常见的折半序列最坏情况下是 O(n²)平均大约 O(n^1.3)。能说出“业界有更好的序列比如 Sedgewick 序列”会是一个不错的加分点但不用展开太多毕竟把代码写对更重要。3.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这段代码里最值得盯住的是合并时的比较条件left[i] right[j]。这个小于等于号就是稳定性的关键当两边元素相等时优先取左侧数组的元素这样相等元素的相对顺序被完整保留。如果这里写成相等元素会被右侧的先取走稳定性就没了。归并排序的缺点是额外空间 O(n)优点是时间稳定在 O(n log n)不依赖输入数据的原始状态。面试中有一个经典变形题合并两个有序数组要求不额外开数组。解法是从两个数组的尾部开始比较较大的放在后面。这个从后往前的双指针写法建议自己推一遍因为它在很多实际场景里真的会用到。3.3 快速排序面试出现率最高务必一次写对快排在面试中的地位不用过多解释手写快排几乎可以算是一道必考题。核心是 partition 过程选一个基准元素把数组分成左边都小于等于基准、右边都大于等于基准的两部分然后递归处理左右子区间。这里我给出最常用的 Lomuto 分区写法以最后一个元素为基准def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1写这段代码最常翻车的地方是 partition 的返回值。i从low - 1开始扫描过程中每遇到一个不大于基准的元素i就加一最终i 1才是基准元素应该去的位置。如果忘记把基准元素交换回arr[i 1]或者返回值算差一位整个排序都会乱掉。快排的平均复杂度是 O(n log n)最坏情况下会退化到 O(n²)。最坏场景通常出现在有序数组上用固定位置选基准时。所以回答时最好主动补充工程实现会使用随机基准或三数取中来规避退化。快排的不稳定同样要会说清楚partition 过程是跳跃式交换相同元素可能在分区时被分到不同的区间相对顺序因此丢掉了。3.4 堆排序TopK 问题的钥匙堆排序利用二叉堆来排序分为两个阶段先自下而上把数组调整成一个大根堆再把堆顶当前最大值与数组末尾交换缩小堆的范围后重新调整重复这个过程直到全部排好。def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n len(arr) # 从最后一个非叶子节点开始建堆 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) return arr索引计算是这段代码最需要记牢的部分下标为 i 的节点左孩子是2 * i 1右孩子是2 * i 2。建堆循环从n // 2 - 1开始因为大于这个下标的节点都是叶子节点没必要调整。堆排序的时间复杂度稳定在 O(n log n)额外空间 O(1)但它属于不稳定排序原因是堆顶与末尾交换时相等元素的相对顺序无法预期。完整手写堆排序在面试里并不算高频但堆的思想会以“TopK 问题”的形式高频出现维护大小为 K 的小顶堆遍历一遍数据堆里留下的就是前 K 个最大值。这个实现建议提前练熟。4. 线性时间排序计数、桶、基数4.1 计数排序范围有限的整数神器计数排序不是基于比较的排序因此它能突破 O(n log n) 的理论下界达到 O(n k)。它的使用前提很明确待排序元素必须是非负整数而且数值范围不能太大否则辅助数组会占用过多空间。思路非常朴素统计每个元素值出现的次数再按数值顺序把元素回填到原数组。def counting_sort(arr, max_val): count [0] * (max_val 1) for num in arr: count[num] 1 idx 0 for i in range(len(count)): while count[i] 0: arr[idx] i idx 1 count[i] - 1 return arr这个写法最简单但严格来说它并不是稳定排序因为只是把相等的值一次性回填没有区分它们原有的先后顺序。如果要写出真正稳定的计数排序思路是先对 count 做前缀和得到一个“每个值最后应该放在输出数组的哪个位置”的映射然后从原数组末尾往前遍历回填。面试里如果被要求讲计数排序的稳定性能把这个前缀和的版本说清楚会显得很有深度。另外如果数组里有负数需要统一加偏移量把最小值变成 0排序完再减回去。这个补充也值得提一句。4.2 基数排序与桶排序海量数据的另类解法基数排序把整数按位拆分从最低位到最高位依次排序每一轮都要求使用稳定排序。它的复杂度是 O(d(n r))其中 d 是最大数的位数r 是基数。我实现时习惯直接基于桶来收集每一轮的结果def radix_sort(arr): if not arr: return arr max_num max(arr) exp 1 while max_num // exp 0: buckets [[] for _ in range(10)] for num in arr: digit (num // exp) % 10 buckets[digit].append(num) arr [num for bucket in buckets for num in bucket] exp * 10 return arr这段代码因为用桶收集天然保证了每轮收集时同一桶内的相对顺序不变即稳定的。它适合数据量大但位数不长且数值非负的场景比如手机号、学号、定长 ID 这类数据。面试中基数排序不常要求手写但能讲出“按位稳定排序”这个核心就够了。桶排序的思路是把数据均匀分到若干桶中每个桶内用其他排序算法或递归桶排序最后按桶顺序把所有元素取出。它的效率取决于桶的分布是否均匀最差情况下所有数据落进同一个桶复杂度退化。实际面试中单独考桶排序的题目不算多但它的思想经常出现在“海量数据求中位数”“大数据量分桶统计”一类题目中理解它的存在价值对于回答这类场景题很有帮助。5. 面试高频变形题5.1 TopK 问题三种解法递进讲TopK 是排序算法相关题目里出现频率最高的一道变形题常见问法是“找出数组中前 K 大的元素”或者“找出第 K 大的元素”。我在辅导别人准备这道题时通常建议按三种解法递进回答。第一种解法最简单全量排序后取前 K 个。时间复杂度 O(n log n)代码量很少但面试官大概率会追问能不能更快。第二种解法是用小顶堆维护一个大小为 K 的小顶堆堆顶是堆中最小的元素。遍历数组一旦遇到比堆顶大的元素就弹出堆顶并插入新元素。遍历结束后堆里的 K 个元素就是前 K 大。时间复杂度 O(n log K)空间 O(K)。当 K 远小于 n 时这个方案比全排序好很多。第三种解法是快选利用快排的 partition一次划分后基准元素所在的位置就是它的排名如果恰好是 K直接返回否则只递归处理包含第 K 大的那一侧。平均时间复杂度 O(n)最坏会退化到 O(n²)需要配合随机基准来规避。这三种解法建议按顺序讲解因为这是一个从“会用排序模板”到“理解排序思想”的递进。很多面试官就会顺着这个递进往下深挖你对 partition 的理解越透后续问题就越稳。5.2 稳定性场景问题排序顺序会不会被覆盖稳定性的概念抽象但面试官通常会用一个具体场景来考有一批员工已经按年龄升序排好现在要求再按薪资降序排序最终的顺序是什么正确答案是如果第二次排序用的是稳定排序结果会先按薪资降序排列薪资相同的员工内部仍然保持年龄升序如果第二次排序不稳定则薪资相同的那批员工顺序可能被重新打乱年龄升序的效果就没了。这个场景其实对应着多级排序的核心逻辑在数据库里执行多字段 ORDER BY 非常常见。理解了这个应用场景再去背稳定性就不容易忘了。面试时如果能主动说出“多级排序时稳定排序可以保证第一关键字排序结果不丢失”会是一个很亮眼的回答。5.3 解一道经典题逆序对计数另一个高频变形题是“求数组中的逆序对数量”。比如数组 [8, 4, 5, 3] 里的逆序对有 (8,4)、(8,5)、(8,3)、(4,3)、(5,3)一共 5 个。暴力解法是双层循环O(n²)面试官听到这个答案后通常会追问有没有更快的办法。更快的方法就是归并排序。在 merge 的过程中当左侧元素大于右侧元素时左侧从当前位置到最后的所有元素都比右侧这个元素大所以它们都构成逆序对。因此只需要在合并时把mid - i 1这个数量累加到计数器里即可。这道题考察的不是背模板而是在熟悉的分治框架里做一点变化。如果你能在手写归并排序的基础上顺带把逆序对计数出来面试官对你的分治理解和代码掌控力都会有很好的印象。这道题我强烈建议在突击阶段亲手实现一次因为它是归并排序出题率最高的变体。6. 突击期的几条实操建议临时抱佛脚阶段最忌讳贪多什么都想抓结果什么都没抓牢。按我的经验看优先级应该是这样冒泡、选择、插入三种基础排序先写熟然后重点死磕快速排序和归并排序堆排序只练关键路径建堆加 heapify。希尔、计数、基数排序认识原理和时间复杂度就够了绝大多数开发岗面试不会要求现场手写这三个除非岗位本身和底层引擎、数据基础设施强相关。手写频率比看代码重要得多。光看模板和口诀是没用的至少要保证快排和归并各完整手写三遍以上。第一次写慢很正常卡住就回去看重要的是每写一遍都要脱离参考代码。写到第三遍基本就能形成肌肉记忆面试现场即使紧张手也不会停。我见过不少候选人复杂度表背得很熟但真正在纸上写代码时不是忘记处理空数组就是分区索引差一位。所以最后想再强调一遍排序算法面试前能快速拉满的就是手写正确率。把那张复杂度表存到手机里每天抽十分钟默写一遍快排和归并三天后的你和现在的你完全是两个水平。面试时只要把核心代码写对了、复杂度讲清了、稳定性原因说透了排序这块基本就不会拖后腿。