做面试官或者旁观别人笔试的时候经常能看到一个很有意思的现象一提到“排序”很多人完全不慌因为第一反应是直接调用内置排序函数可一旦被要求“手写冒泡排序”或者“解释一下快速排序为什么快”不少人就开始卡壳。这倒不一定是基础差而是排序在日常开发里被当成了现成工具很少有人把它当成训练边界控制和复杂度直觉的教材。这篇文章就围绕刷题平台上最常被考察的五种经典算法——冒泡排序、选择排序、插入排序、快速排序、计数排序把它们的核心思想、标准模板、易错点以及刷题场景中的真实用法讲透。不管你是刚准备面试的初学者还是想系统整理排序模板的进阶玩家应该都能从中捞到点东西。我会尽量用写业务代码时的大白话来讲不堆术语每一步都说明白“为什么这么做”。1. 刷题场景下的排序算法手写排序到底在考什么先说一个很多人没想明白的问题既然刷题平台允许直接调用sorted()、Arrays.sort()为什么面试官还是执着于让你手写排序我的理解是排序是少数几种能同时考察三项底层能力的题型。第一项是对循环边界的敏感度。冒泡排序的内层循环到哪结束选择排序的最小值下标从哪开始扫插入排序的 while 条件顺序能不能写反这些细节看起来小但真发给候选人手写十个人里至少有两个人会越界或者多算一轮。边界条件从来不是“细心”两个字能概括的它背后是对数组索引和循环不变量的真正掌控。第二项是对稳定性和原地性的理解。面试官很喜欢追问一句“这个排序稳定吗为什么”你要是只背结论“选择排序不稳定”却说不清楚是因为跨越式交换破坏了相对顺序那这题基本就被判为死记硬背。第三项是复杂度直觉。五种算法里前四种是比较排序最后一种是计数排序。为什么计数排序能突破 O(n log n) 的下界因为它不比较。这背后牵扯出的是“比较排序理论下界”和“空间换时间”两个重要思维模型。刷题越到后期你会发现真正考排序的题目几乎都不是让你排个序就完事而是让你用排序思想去解决“求第 K 大”“按频率排序”“统计逆序对”这类变形题。所以我的建议是不要嫌弃排序太基础把五种算法当成五把钥匙。它们各自锁着一个思维训练点——冒泡锁相邻交换选择锁极值定位插入锁局部有序快速锁分治划分计数锁值域映射。把这五把钥匙都摸熟了后面做很多题都能顺手开锁。2. 冒泡与选择排序边界条件决定成败的基础功2.1 冒泡排序的正确姿势与常见错法冒泡排序的思想大概是最容易解释的从前往后两两比较如果前一个比后一个大就交换这样每一轮都会把当前未排序区域里的最大值“冒”到最后面。一张 Python 模板如下def bubble_sort(nums): n len(nums) for i in range(n): swapped False for j in range(0, n - i - 1): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] swapped True if not swapped: break return nums代码里最容易被写错的地方是内层循环的n - i - 1。为什么不是n - 1因为每跑完一轮i末尾的i个位置已经放好了本轮最大的那几个数它们不需要再参与比较。如果写成n - 1功能上不错但会多出大量无效比较。面试时让候选人优化八成要先指出这一点。另外一个常被忽略的细节是swapped标记。这个标记的意义在于如果某轮扫描下来一次交换都没发生说明数组已经整体有序直接跳出循环即可。加了这一步后对于完全有序的数组冒泡排序只需要一轮扫描复杂度退化到 O(n)。这个细节如果你能在代码里主动写出来会是个不错的加分点。冒泡排序的稳定性和坑在哪里稳定性相等元素不会交换所以是稳定排序。空间复杂度原地交换O(1)。时间复杂度平均和最坏 O(n²)。说实话刷题时我几乎不会用冒泡排序做答案。它真正的价值在于理解“相邻交换”这个基本动作。比如有一类题只允许交换相邻元素问最少交换多少次能把数组排成某种顺序这个问题的本质就是在求逆序对数量而逆序对统计的标准做法是归并排序。冒泡排序其实就是“每次只消除一个逆序对”的朴素实现理解了这层关系你再去学归并排序的优化逻辑会顺畅得多。2.2 选择排序的不稳定性与“前 k 轮”思路选择排序的核心思想更直接每轮从未排序部分挑出最小值放到已排序部分的末尾。def selection_sort(nums): n len(nums) for i in range(n): min_idx i for j in range(i 1, n): if nums[j] nums[min_idx]: min_idx j nums[i], nums[min_idx] nums[min_idx], nums[i] return nums这个代码比冒泡还好写但它的经典坑是稳定性。举个例子[5a, 5b, 1]第一轮找到最小值 1直接和第一个位置的 5a 交换结果变成[1, 5b, 5a]两个 5 的相对顺序反了。原因是选择排序做的是一次“跨越式交换”而不是相邻交换它可以把一个元素直接扔到很远的位置所以相同元素的相对顺序没法保证。这提醒我们一件事刷题时如果明确要求稳定排序选项里就不要考虑选择排序也别考虑快速排序的基础实现优先考虑冒泡、插入、归并、计数。选择排序在刷题里的一个变体思路值得知道如果只要求选出最小或最大的前 k 个元素理论上可以只跑 k 轮选择排序每轮 O(n)总复杂度 O(nk)。我在一次笔试里就这样干过题目是“从一百万个整数里选出最小的 100 个”结果提交超时。事后复盘才意识到这种场景下正确选择是建一个小顶堆或者直接用快速选择而不是选择排序跑 100 轮。这个问题也说明一个道理面试考选择排序不是让你拿它当最终答案而是看你知不知道它的复杂度边界在哪里。3. 插入排序被低估的工程价值与链表场景3.1 扑克牌式的逐个插入逻辑插入排序的思路人人都会打牌时抓到一张新牌把它插到手里已经排好序的牌堆中的合适位置。代码写出来也相当精简def insertion_sort(nums): n len(nums) for i in range(1, n): tmp nums[i] j i - 1 while j 0 and nums[j] tmp: nums[j 1] nums[j] j - 1 nums[j 1] tmp return nums很多人第一次写插入排序会把它写成一个for内部套for、每次都交换相邻元素的版本。那种写法也能跑但效率差一些而且不够优雅。正确的姿势是先把当前元素tmp存下来前面的元素逐个往后挪最后把tmp放到空出来的位置。这种做法把“交换”变成了“覆盖”数组访问次数少一些也更贴近工业实现。这里有个稳定性的关键细节while 判断条件是nums[j] tmp而不是nums[j] tmp。如果写成大于等于遇到相同元素时还会继续往后挪把后来的元素插到原本相同元素的前面就破坏了稳定性。正确写法是在相等时停止让新元素停在相同元素之后从而保持稳定。3.2 为什么说它在工程里被低估插入排序表面上就是个 O(n²) 的排序但它有两个其他 O(n²) 算法没有的特性。第一个特性是“自适应”。如果待排序数组基本有序每次 while 通常只比较一两次就能找到位置整体复杂度可以降到接近 O(n)。刷题中这个特性通常体现在“动态维护有序序列”的场景比如你已经维护了一个有序数组现在频繁地插入一个新值要求插入后仍然有序。直接用插入排序的一趟逻辑把新值从数组末尾往前找位置往往比每次调用sorted()重建整个数组更快。第二个特性是“低常数 局部性”。在小规模数据上插入排序的真实运行速度不慢甚至能打赢部分 O(n log n) 算法。很多标准库的排序实现比如快速排序的工程优化版内部都有一个阈值当待排区间长度小于 16 或 32 时停止递归改用插入排序收尾。原因是快排递归调用的函数栈开销在小区间上会淹没排序收益。这个优化你完全可以在自己写快排时应用。另外插入排序是链表排序的天然好选择。因为链表不能随机访问很多基于“选中间元素”的排序实现起来都很费劲但插入排序本来就只依赖“从当前位置往前找插入点”而这个操作在链表里也就是几个指针的事。刷题平台上的“链表插入排序”题就是直接把插入排序的逻辑迁移到链表上理解了数组版本链表版本只需要把“往前挪”改成“遍历找插入位置”。我实际写代码时栽过一个小跟头while 条件里如果先判断nums[j] tmp再判断j 0数组下标会越界。正确写法必须把j 0放在前面Python 的短路求值会保证 j 为 -1 时不再访问数组。这个排列顺序虽然只需要一秒钟就能改过来但面试现场紧张时很容易写反建议背模板时顺便把这一条背进肌肉记忆。4. 快速排序partition 是灵魂快速选择是变身4.1 经典快排模板与两种分区写法快排为什么叫“快速”因为它把一个大数组切成两半各自递归排序每一层都做线性扫描理想情况下总共 O(n log n) 次比较。写快排之前必须先写对 partition。我最常用的是 Lomuto 分区它的逻辑简单且不容易出边界问题def partition(nums, left, right): pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] return i def quick_sort(nums, left, right): if left right: return p partition(nums, left, right) quick_sort(nums, left, p - 1) quick_sort(nums, p 1, right)Lomuto 分区的理解方式是维护一个“小于 pivot 的区域边界指针 i”每遇到一个比 pivot 小的元素就把它扔进这个区域区域右扩一格。把整个区间扫完之后pivot 本身的位置自然就在 i 上。另一种更高效的 Hoare 分区则是左右双指针相向移动左边找一个大于 pivot 的右边找一个小于 pivot 的然后交换直到两个指针相遇。Hoare 的交换次数更少但边界处理更麻烦尤其容易在指针相遇时写出死循环。我自己面试时一般先写 Lomuto因为正确性优先。等回答完正确性之后再主动说“如果用 Hoare 分区可以常数更快但边界情况需要多处理”这种主动补充分解动作其实更见功底。4.2 最坏情况从哪来以及三路快排的思路快排看起来很完美但它有一个致命弱点当数组已经有序或者接近有序、且每次选到的 pivot 都是最大或最小值时一次分区只能分出一个元素去固定位置递归深度变成 O(n)整体复杂度退化成 O(n²)。解决办法常见的就三个随机选 pivot。从概率上避免每次都踩到最坏点这是最简单有效的办法。三数取中。取左、中、右三个位置的中位数作为 pivot工程实现里很常用因为能兼顾“数据有序”和“随机性较差”两类场景。三路快排。当数组中存在大量重复元素时普通快排会反复处理重复值。三路快排把区间分成“小于 pivot”“等于 pivot”“大于 pivot”三段只递归两端中间全部跳过。这个思路还有一个面试中很著名的应用场景叫“荷兰国旗问题”数组里只有 0、1、2 三种值要求一次遍历排好序。用到的就是三路分区的思想。关于递归栈的空间复杂度很多人会忽略。快排不是 O(1) 空间因为递归需要栈空间平均是 O(log n)最坏退化成 O(n)。面试官问“快速排序空间复杂度是多少”的时候你答“平均 O(log n)”然后再补一句“最坏 O(n)但随机化可以规避”就比单背一个 O(log n) 要好得多。4.3 快速选择求第 K 大元素的骨灰级套路快排最精彩的变形是把“递归排序整个区间”改成“只递归目标所在的区间”。因为在 partition 之后pivot 的位置 p 已经意味着在最终排序结果中它是第 p 个数从 0 计数。那我们要找第 k 大的元素就只需要判断目标索引和 p 的关系决定往左还是往右。第 K 大的常见转换是先求 len(nums) - K也就是“从 0 开始计数的第 len-K 小”。然后套快速选择def quick_select(nums, left, right, k): if left right: return nums[left] p partition(nums, left, right) if p k: return nums[p] elif p k: return quick_select(nums, p 1, right, k) else: return quick_select(nums, left, p - 1, k)这里有几个实操细节值得重点标出来递归区间是p 1和p - 1千万不要包含 p 本身否则区间永远不变直接死循环。快速选择平均复杂度 O(n)但最坏也是 O(n²)。同样用随机 pivot 来规避。该算法会原地修改数组因为 partition 本质上在交换元素。如果题目要求不能改动原数组要么复制一份要么改用堆。如果你调用一次 partition 之后发现 p 恰好等于目标索引立刻返回不用再排剩下的任何元素这就是“部分排序”思想的精髓。刷题时很多“前 K 大”或“第 K 大”的题目都能用快速选择尤其是数据规模很大、堆的 O(n log k) 也可能超时的场景。但需要提示的是快速选择的结果依赖原数组被修改如果后续还要用原数组必须提前备份。5. 计数排序当值域有限时用空间换时间的非比较选手5.1 基础版计数排序统计次数后直接填充计数排序跳出“比较”的框架因此能在特定条件下做到 O(n k)其中 k 是值域大小。核心思想只有一句话用数组下标当值下标对应的元素存“这个值出现了多少次”。def counting_sort(nums): if not nums: return [] max_val max(nums) count [0] * (max_val 1) for x in nums: count[x] 1 res [] for v, c in enumerate(count): res.extend([v] * c) return res用生活化的例子解释就是一个班同学年龄只有 6 岁到 12 岁老师不需要两两比较谁大谁小只需要按年龄报数统计“7 岁几个人8 岁几个人”然后按年龄从小到大把所有同学列出来。这段基础版代码在刷题里能应对大多数“非负整数、范围不大、不必稳定”的场景。但要注意它的限制条件数据必须是非负整数或者可以映射成非负整数。负数要先平移区间。值域不能太大。比如max_val到 10⁹count数组直接爆炸。基础版不是稳定排序。因为它是按“数值从小到大 计数”填充的完全丢掉了原始顺序。5.2 稳定版计数排序前缀和与反向填充如果题目要求稳定也就是相同值的元素在输出时保留原始相对顺序那就需要升级成前缀和版本的计数排序。def counting_sort_stable(nums): if not nums: return [] max_val max(nums) count [0] * (max_val 1) for x in nums: count[x] 1 for i in range(1, len(count)): count[i] count[i - 1] res [0] * len(nums) for x in reversed(nums): count[x] - 1 res[count[x]] x return res这里的关键是最后一步为什么要反向遍历原数组。前缀和count[x]表示“小于等于 x 的元素总共有多少个”那 x 在结果数组中的最后一个位置就是count[x] - 1。从原数组末尾开始扫描每放一个 x就把count[x]减一这样遇到第二个相同的 x 时它会被放到那个位置的前一格从而保持相对顺序不变。我在一次刷题中就吃过基础版的亏题目要求把任务按出现次数从高到低排序如果次数相同则按原始顺序输出。我第一版直接用了基础版计数排序结果相同次数的任务顺序全乱了提交后一脸茫然半天才反应过来是稳定性的问题。后来加上了前缀和与反向填充一次通过。5.3 计数排序在刷题中的高频场景计数排序最常见的刷题场景有这么几类字符串和字母排序。比如只包含小写字母的字符串开 26 个大小的桶O(n) 就能排完。按频率排序。先统计每个元素出现次数再把出现次数作为“值”去排序。很多“按频率升序/降序输出”的题目本质就是建一个频次数组然后对频次值做计数排序。年龄、分数、星级这类小范围数值排序。还要提醒一点别把计数排序和桶排序、基数排序混为一谈。计数排序是每个值一个桶桶排序是把值域分成若干区间区间内再做其他排序基数排序是按数字的位进行多轮排序。三者各有各的适用前提但评论区里最常见的误区就是管桶排序叫计数排序。6. 五种算法横向对比与刷题时的决策思路6.1 一张表说明全部关键属性排序算法平均时间复杂度最坏时间复杂度额外空间稳定性是否原地冒泡排序O(n²)O(n²)O(1)稳定是选择排序O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(1)稳定是快速排序O(n log n)O(n²)O(log n)不稳定是计数排序O(n k)O(n k)O(k)可稳定实现否这张表不是拿来背的面试官大概率会追问“为什么快速排序平均 O(n log n)”“为什么计数排序能 O(n)”这类问题。你要能做到每一条都能展开说明。6.2 刷题时看到题目条件怎么选排序拿到一道题先别急着写排序代码先看数据规模和数据特征。如果 n 很小比如小于 50并且需要稳定排序直接插入排序最简单。如果只要求选出最大或最小的某个值别用完整排序用快速选择或堆更合适。如果数据是有限范围的整数比如年龄、分数直接用计数排序把复杂度压到 O(n)。如果数组很大且对稳定性没有要求快速排序配上随机 pivot 是最经典的选择。如果数组基本有序插入排序的实战表现会出奇地好虽然理论复杂度还是 O(n²)。我也总结过一个简单口诀范围小用计数基本有序用插入第 K 个用快选稳定性要求高就别碰选择和快排。6.3 把模板刻进肌肉记忆的练习方法关于模板的背诵我见过很多错误的练习方式拿那五种排序每天默写二十遍但只是默写代码不理解变量含义。这样一旦题目变形就僵住了。我更推荐“三步练习法”第一步先看懂模板。每行代码都要能回答“这个变量的作用是什么”“这个循环为什么是这个边界”。第二步改一个细节跑一遍。比如把插入排序的改成观察结果变化用肉眼验证稳定性理论。第三步做两道变形题。比如分别用快速选择和堆排序做同一道“求第 K 大元素”题对比两种解法在性能上的差异。我在刷题平台上见过很多人直接用内置sorted()就把题过了这当然没错但如果你准备的是面试一定要自己手写过至少一遍基础模板。面试官看的是你的思考过程而不是最终结果。6.4 排序思想延伸出去的经典变形题排序从来不是终点它在刷题里更像一把万能扳手。真正的高频考点往往是它的变形求逆序对数量核心是归并排序冒泡排序的朴素解释就是每次交换消除一个逆序对。求第 K 大 / 前 K 小核心是快速选择或堆。荷兰国旗问题三路快排的直接应用。按奇偶排序双指针不需要完整排序。按字母频率排序先统计再用桶或计数排序。这些变形题看起来五花八门但内核都指向同一个能力理解排序不是“排完就完”而是“排完之后每个位置都有明确语义”。一旦你有了这种视角很多题就不会只停留在调用sorted()的水平上。最后分享一点个人体会。我早期刷题时特别喜欢追求代码简短能用一行sorted()解决的绝不写第二行。后来慢慢发现真正让我在面试里稳住阵脚的反而是那些看起来最基础的排序模板。它们逼着我把循环边界、稳定性、空间复杂度这些概念反复打磨到直觉层面再遇到复杂变形题时就不容易慌。建议你也别嫌这五类排序简单抽一个下午把它们一个个手写跑通再试着回答一遍“为什么这样写不会越界”那感觉和单纯看文章是完全不同的。 
长河君 · 2026/10/22 19:28:51 · 阅读 1.2k 手写排序算法：五类经典排序模板与面试要点详解
做面试官或者旁观别人笔试的时候经常能看到一个很有意思的现象一提到“排序”很多人完全不慌因为第一反应是直接调用内置排序函数可一旦被要求“手写冒泡排序”或者“解释一下快速排序为什么快”不少人就开始卡壳。这倒不一定是基础差而是排序在日常开发里被当成了现成工具很少有人把它当成训练边界控制和复杂度直觉的教材。这篇文章就围绕刷题平台上最常被考察的五种经典算法——冒泡排序、选择排序、插入排序、快速排序、计数排序把它们的核心思想、标准模板、易错点以及刷题场景中的真实用法讲透。不管你是刚准备面试的初学者还是想系统整理排序模板的进阶玩家应该都能从中捞到点东西。我会尽量用写业务代码时的大白话来讲不堆术语每一步都说明白“为什么这么做”。1. 刷题场景下的排序算法手写排序到底在考什么先说一个很多人没想明白的问题既然刷题平台允许直接调用sorted()、Arrays.sort()为什么面试官还是执着于让你手写排序我的理解是排序是少数几种能同时考察三项底层能力的题型。第一项是对循环边界的敏感度。冒泡排序的内层循环到哪结束选择排序的最小值下标从哪开始扫插入排序的 while 条件顺序能不能写反这些细节看起来小但真发给候选人手写十个人里至少有两个人会越界或者多算一轮。边界条件从来不是“细心”两个字能概括的它背后是对数组索引和循环不变量的真正掌控。第二项是对稳定性和原地性的理解。面试官很喜欢追问一句“这个排序稳定吗为什么”你要是只背结论“选择排序不稳定”却说不清楚是因为跨越式交换破坏了相对顺序那这题基本就被判为死记硬背。第三项是复杂度直觉。五种算法里前四种是比较排序最后一种是计数排序。为什么计数排序能突破 O(n log n) 的下界因为它不比较。这背后牵扯出的是“比较排序理论下界”和“空间换时间”两个重要思维模型。刷题越到后期你会发现真正考排序的题目几乎都不是让你排个序就完事而是让你用排序思想去解决“求第 K 大”“按频率排序”“统计逆序对”这类变形题。所以我的建议是不要嫌弃排序太基础把五种算法当成五把钥匙。它们各自锁着一个思维训练点——冒泡锁相邻交换选择锁极值定位插入锁局部有序快速锁分治划分计数锁值域映射。把这五把钥匙都摸熟了后面做很多题都能顺手开锁。2. 冒泡与选择排序边界条件决定成败的基础功2.1 冒泡排序的正确姿势与常见错法冒泡排序的思想大概是最容易解释的从前往后两两比较如果前一个比后一个大就交换这样每一轮都会把当前未排序区域里的最大值“冒”到最后面。一张 Python 模板如下def bubble_sort(nums): n len(nums) for i in range(n): swapped False for j in range(0, n - i - 1): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] swapped True if not swapped: break return nums代码里最容易被写错的地方是内层循环的n - i - 1。为什么不是n - 1因为每跑完一轮i末尾的i个位置已经放好了本轮最大的那几个数它们不需要再参与比较。如果写成n - 1功能上不错但会多出大量无效比较。面试时让候选人优化八成要先指出这一点。另外一个常被忽略的细节是swapped标记。这个标记的意义在于如果某轮扫描下来一次交换都没发生说明数组已经整体有序直接跳出循环即可。加了这一步后对于完全有序的数组冒泡排序只需要一轮扫描复杂度退化到 O(n)。这个细节如果你能在代码里主动写出来会是个不错的加分点。冒泡排序的稳定性和坑在哪里稳定性相等元素不会交换所以是稳定排序。空间复杂度原地交换O(1)。时间复杂度平均和最坏 O(n²)。说实话刷题时我几乎不会用冒泡排序做答案。它真正的价值在于理解“相邻交换”这个基本动作。比如有一类题只允许交换相邻元素问最少交换多少次能把数组排成某种顺序这个问题的本质就是在求逆序对数量而逆序对统计的标准做法是归并排序。冒泡排序其实就是“每次只消除一个逆序对”的朴素实现理解了这层关系你再去学归并排序的优化逻辑会顺畅得多。2.2 选择排序的不稳定性与“前 k 轮”思路选择排序的核心思想更直接每轮从未排序部分挑出最小值放到已排序部分的末尾。def selection_sort(nums): n len(nums) for i in range(n): min_idx i for j in range(i 1, n): if nums[j] nums[min_idx]: min_idx j nums[i], nums[min_idx] nums[min_idx], nums[i] return nums这个代码比冒泡还好写但它的经典坑是稳定性。举个例子[5a, 5b, 1]第一轮找到最小值 1直接和第一个位置的 5a 交换结果变成[1, 5b, 5a]两个 5 的相对顺序反了。原因是选择排序做的是一次“跨越式交换”而不是相邻交换它可以把一个元素直接扔到很远的位置所以相同元素的相对顺序没法保证。这提醒我们一件事刷题时如果明确要求稳定排序选项里就不要考虑选择排序也别考虑快速排序的基础实现优先考虑冒泡、插入、归并、计数。选择排序在刷题里的一个变体思路值得知道如果只要求选出最小或最大的前 k 个元素理论上可以只跑 k 轮选择排序每轮 O(n)总复杂度 O(nk)。我在一次笔试里就这样干过题目是“从一百万个整数里选出最小的 100 个”结果提交超时。事后复盘才意识到这种场景下正确选择是建一个小顶堆或者直接用快速选择而不是选择排序跑 100 轮。这个问题也说明一个道理面试考选择排序不是让你拿它当最终答案而是看你知不知道它的复杂度边界在哪里。3. 插入排序被低估的工程价值与链表场景3.1 扑克牌式的逐个插入逻辑插入排序的思路人人都会打牌时抓到一张新牌把它插到手里已经排好序的牌堆中的合适位置。代码写出来也相当精简def insertion_sort(nums): n len(nums) for i in range(1, n): tmp nums[i] j i - 1 while j 0 and nums[j] tmp: nums[j 1] nums[j] j - 1 nums[j 1] tmp return nums很多人第一次写插入排序会把它写成一个for内部套for、每次都交换相邻元素的版本。那种写法也能跑但效率差一些而且不够优雅。正确的姿势是先把当前元素tmp存下来前面的元素逐个往后挪最后把tmp放到空出来的位置。这种做法把“交换”变成了“覆盖”数组访问次数少一些也更贴近工业实现。这里有个稳定性的关键细节while 判断条件是nums[j] tmp而不是nums[j] tmp。如果写成大于等于遇到相同元素时还会继续往后挪把后来的元素插到原本相同元素的前面就破坏了稳定性。正确写法是在相等时停止让新元素停在相同元素之后从而保持稳定。3.2 为什么说它在工程里被低估插入排序表面上就是个 O(n²) 的排序但它有两个其他 O(n²) 算法没有的特性。第一个特性是“自适应”。如果待排序数组基本有序每次 while 通常只比较一两次就能找到位置整体复杂度可以降到接近 O(n)。刷题中这个特性通常体现在“动态维护有序序列”的场景比如你已经维护了一个有序数组现在频繁地插入一个新值要求插入后仍然有序。直接用插入排序的一趟逻辑把新值从数组末尾往前找位置往往比每次调用sorted()重建整个数组更快。第二个特性是“低常数 局部性”。在小规模数据上插入排序的真实运行速度不慢甚至能打赢部分 O(n log n) 算法。很多标准库的排序实现比如快速排序的工程优化版内部都有一个阈值当待排区间长度小于 16 或 32 时停止递归改用插入排序收尾。原因是快排递归调用的函数栈开销在小区间上会淹没排序收益。这个优化你完全可以在自己写快排时应用。另外插入排序是链表排序的天然好选择。因为链表不能随机访问很多基于“选中间元素”的排序实现起来都很费劲但插入排序本来就只依赖“从当前位置往前找插入点”而这个操作在链表里也就是几个指针的事。刷题平台上的“链表插入排序”题就是直接把插入排序的逻辑迁移到链表上理解了数组版本链表版本只需要把“往前挪”改成“遍历找插入位置”。我实际写代码时栽过一个小跟头while 条件里如果先判断nums[j] tmp再判断j 0数组下标会越界。正确写法必须把j 0放在前面Python 的短路求值会保证 j 为 -1 时不再访问数组。这个排列顺序虽然只需要一秒钟就能改过来但面试现场紧张时很容易写反建议背模板时顺便把这一条背进肌肉记忆。4. 快速排序partition 是灵魂快速选择是变身4.1 经典快排模板与两种分区写法快排为什么叫“快速”因为它把一个大数组切成两半各自递归排序每一层都做线性扫描理想情况下总共 O(n log n) 次比较。写快排之前必须先写对 partition。我最常用的是 Lomuto 分区它的逻辑简单且不容易出边界问题def partition(nums, left, right): pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] return i def quick_sort(nums, left, right): if left right: return p partition(nums, left, right) quick_sort(nums, left, p - 1) quick_sort(nums, p 1, right)Lomuto 分区的理解方式是维护一个“小于 pivot 的区域边界指针 i”每遇到一个比 pivot 小的元素就把它扔进这个区域区域右扩一格。把整个区间扫完之后pivot 本身的位置自然就在 i 上。另一种更高效的 Hoare 分区则是左右双指针相向移动左边找一个大于 pivot 的右边找一个小于 pivot 的然后交换直到两个指针相遇。Hoare 的交换次数更少但边界处理更麻烦尤其容易在指针相遇时写出死循环。我自己面试时一般先写 Lomuto因为正确性优先。等回答完正确性之后再主动说“如果用 Hoare 分区可以常数更快但边界情况需要多处理”这种主动补充分解动作其实更见功底。4.2 最坏情况从哪来以及三路快排的思路快排看起来很完美但它有一个致命弱点当数组已经有序或者接近有序、且每次选到的 pivot 都是最大或最小值时一次分区只能分出一个元素去固定位置递归深度变成 O(n)整体复杂度退化成 O(n²)。解决办法常见的就三个随机选 pivot。从概率上避免每次都踩到最坏点这是最简单有效的办法。三数取中。取左、中、右三个位置的中位数作为 pivot工程实现里很常用因为能兼顾“数据有序”和“随机性较差”两类场景。三路快排。当数组中存在大量重复元素时普通快排会反复处理重复值。三路快排把区间分成“小于 pivot”“等于 pivot”“大于 pivot”三段只递归两端中间全部跳过。这个思路还有一个面试中很著名的应用场景叫“荷兰国旗问题”数组里只有 0、1、2 三种值要求一次遍历排好序。用到的就是三路分区的思想。关于递归栈的空间复杂度很多人会忽略。快排不是 O(1) 空间因为递归需要栈空间平均是 O(log n)最坏退化成 O(n)。面试官问“快速排序空间复杂度是多少”的时候你答“平均 O(log n)”然后再补一句“最坏 O(n)但随机化可以规避”就比单背一个 O(log n) 要好得多。4.3 快速选择求第 K 大元素的骨灰级套路快排最精彩的变形是把“递归排序整个区间”改成“只递归目标所在的区间”。因为在 partition 之后pivot 的位置 p 已经意味着在最终排序结果中它是第 p 个数从 0 计数。那我们要找第 k 大的元素就只需要判断目标索引和 p 的关系决定往左还是往右。第 K 大的常见转换是先求 len(nums) - K也就是“从 0 开始计数的第 len-K 小”。然后套快速选择def quick_select(nums, left, right, k): if left right: return nums[left] p partition(nums, left, right) if p k: return nums[p] elif p k: return quick_select(nums, p 1, right, k) else: return quick_select(nums, left, p - 1, k)这里有几个实操细节值得重点标出来递归区间是p 1和p - 1千万不要包含 p 本身否则区间永远不变直接死循环。快速选择平均复杂度 O(n)但最坏也是 O(n²)。同样用随机 pivot 来规避。该算法会原地修改数组因为 partition 本质上在交换元素。如果题目要求不能改动原数组要么复制一份要么改用堆。如果你调用一次 partition 之后发现 p 恰好等于目标索引立刻返回不用再排剩下的任何元素这就是“部分排序”思想的精髓。刷题时很多“前 K 大”或“第 K 大”的题目都能用快速选择尤其是数据规模很大、堆的 O(n log k) 也可能超时的场景。但需要提示的是快速选择的结果依赖原数组被修改如果后续还要用原数组必须提前备份。5. 计数排序当值域有限时用空间换时间的非比较选手5.1 基础版计数排序统计次数后直接填充计数排序跳出“比较”的框架因此能在特定条件下做到 O(n k)其中 k 是值域大小。核心思想只有一句话用数组下标当值下标对应的元素存“这个值出现了多少次”。def counting_sort(nums): if not nums: return [] max_val max(nums) count [0] * (max_val 1) for x in nums: count[x] 1 res [] for v, c in enumerate(count): res.extend([v] * c) return res用生活化的例子解释就是一个班同学年龄只有 6 岁到 12 岁老师不需要两两比较谁大谁小只需要按年龄报数统计“7 岁几个人8 岁几个人”然后按年龄从小到大把所有同学列出来。这段基础版代码在刷题里能应对大多数“非负整数、范围不大、不必稳定”的场景。但要注意它的限制条件数据必须是非负整数或者可以映射成非负整数。负数要先平移区间。值域不能太大。比如max_val到 10⁹count数组直接爆炸。基础版不是稳定排序。因为它是按“数值从小到大 计数”填充的完全丢掉了原始顺序。5.2 稳定版计数排序前缀和与反向填充如果题目要求稳定也就是相同值的元素在输出时保留原始相对顺序那就需要升级成前缀和版本的计数排序。def counting_sort_stable(nums): if not nums: return [] max_val max(nums) count [0] * (max_val 1) for x in nums: count[x] 1 for i in range(1, len(count)): count[i] count[i - 1] res [0] * len(nums) for x in reversed(nums): count[x] - 1 res[count[x]] x return res这里的关键是最后一步为什么要反向遍历原数组。前缀和count[x]表示“小于等于 x 的元素总共有多少个”那 x 在结果数组中的最后一个位置就是count[x] - 1。从原数组末尾开始扫描每放一个 x就把count[x]减一这样遇到第二个相同的 x 时它会被放到那个位置的前一格从而保持相对顺序不变。我在一次刷题中就吃过基础版的亏题目要求把任务按出现次数从高到低排序如果次数相同则按原始顺序输出。我第一版直接用了基础版计数排序结果相同次数的任务顺序全乱了提交后一脸茫然半天才反应过来是稳定性的问题。后来加上了前缀和与反向填充一次通过。5.3 计数排序在刷题中的高频场景计数排序最常见的刷题场景有这么几类字符串和字母排序。比如只包含小写字母的字符串开 26 个大小的桶O(n) 就能排完。按频率排序。先统计每个元素出现次数再把出现次数作为“值”去排序。很多“按频率升序/降序输出”的题目本质就是建一个频次数组然后对频次值做计数排序。年龄、分数、星级这类小范围数值排序。还要提醒一点别把计数排序和桶排序、基数排序混为一谈。计数排序是每个值一个桶桶排序是把值域分成若干区间区间内再做其他排序基数排序是按数字的位进行多轮排序。三者各有各的适用前提但评论区里最常见的误区就是管桶排序叫计数排序。6. 五种算法横向对比与刷题时的决策思路6.1 一张表说明全部关键属性排序算法平均时间复杂度最坏时间复杂度额外空间稳定性是否原地冒泡排序O(n²)O(n²)O(1)稳定是选择排序O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(1)稳定是快速排序O(n log n)O(n²)O(log n)不稳定是计数排序O(n k)O(n k)O(k)可稳定实现否这张表不是拿来背的面试官大概率会追问“为什么快速排序平均 O(n log n)”“为什么计数排序能 O(n)”这类问题。你要能做到每一条都能展开说明。6.2 刷题时看到题目条件怎么选排序拿到一道题先别急着写排序代码先看数据规模和数据特征。如果 n 很小比如小于 50并且需要稳定排序直接插入排序最简单。如果只要求选出最大或最小的某个值别用完整排序用快速选择或堆更合适。如果数据是有限范围的整数比如年龄、分数直接用计数排序把复杂度压到 O(n)。如果数组很大且对稳定性没有要求快速排序配上随机 pivot 是最经典的选择。如果数组基本有序插入排序的实战表现会出奇地好虽然理论复杂度还是 O(n²)。我也总结过一个简单口诀范围小用计数基本有序用插入第 K 个用快选稳定性要求高就别碰选择和快排。6.3 把模板刻进肌肉记忆的练习方法关于模板的背诵我见过很多错误的练习方式拿那五种排序每天默写二十遍但只是默写代码不理解变量含义。这样一旦题目变形就僵住了。我更推荐“三步练习法”第一步先看懂模板。每行代码都要能回答“这个变量的作用是什么”“这个循环为什么是这个边界”。第二步改一个细节跑一遍。比如把插入排序的改成观察结果变化用肉眼验证稳定性理论。第三步做两道变形题。比如分别用快速选择和堆排序做同一道“求第 K 大元素”题对比两种解法在性能上的差异。我在刷题平台上见过很多人直接用内置sorted()就把题过了这当然没错但如果你准备的是面试一定要自己手写过至少一遍基础模板。面试官看的是你的思考过程而不是最终结果。6.4 排序思想延伸出去的经典变形题排序从来不是终点它在刷题里更像一把万能扳手。真正的高频考点往往是它的变形求逆序对数量核心是归并排序冒泡排序的朴素解释就是每次交换消除一个逆序对。求第 K 大 / 前 K 小核心是快速选择或堆。荷兰国旗问题三路快排的直接应用。按奇偶排序双指针不需要完整排序。按字母频率排序先统计再用桶或计数排序。这些变形题看起来五花八门但内核都指向同一个能力理解排序不是“排完就完”而是“排完之后每个位置都有明确语义”。一旦你有了这种视角很多题就不会只停留在调用sorted()的水平上。最后分享一点个人体会。我早期刷题时特别喜欢追求代码简短能用一行sorted()解决的绝不写第二行。后来慢慢发现真正让我在面试里稳住阵脚的反而是那些看起来最基础的排序模板。它们逼着我把循环边界、稳定性、空间复杂度这些概念反复打磨到直觉层面再遇到复杂变形题时就不容易慌。建议你也别嫌这五类排序简单抽一个下午把它们一个个手写跑通再试着回答一遍“为什么这样写不会越界”那感觉和单纯看文章是完全不同的。