直接插入排序、冒泡排序、快速排序、选择排序这四兄弟几乎出现在每一本算法教材的目录前几页也几乎出现在每一次笔试的白纸上方。说实话我帮团队做基础算法梳理的时候最常被问倒的不是红黑树也不是动态规划恰恰是这些“以为闭着眼都能写”的排序。这篇文章不打算抄书我就用一次完整实现的过程把这四种排序的代码、复杂度、适用场景和我自己踩过的坑一次性讲透。适合正在准备笔试面试的朋友也适合刚学数据结构、想把排序真正写对而不是“背对”的人。读完之后你至少能收获三样东西随时能正确手写四种排序的底气和边界意识一张可以对着看的数据速查表还有一份我自己用过的排序代码自测清单。1. 四种排序为什么总是它们四个一起出现很多初学者会困惑排序算法有归并、堆排、基数、桶排为什么教材偏偏把插入、冒泡、快排、选择这四种放在同一章原因不是它们性能最好而是它们四个人恰好代表了基础算法设计的几种最典型思路。插入排序代表的是“增量式构建”假设左边已经有序往里面插入新元素。冒泡排序代表的是“相邻交换驱动”通过不断交换相邻逆序对让序列慢慢变好。快速排序代表的是“分治切割”选一个基准把问题拆成两个独立子问题递归解决。选择排序代表的是“贪心式扫描”每次都从剩余元素里挑出最值放到目标位置。这四种思路一旦吃透后面学归并、堆排、希尔、桶排序你会觉得很顺因为本质都是在这些母题上加优化。它们还共同构成了一个很好的复杂度对照样本为什么有的排序 O(n²)有的能做到 O(n log n)为什么稳定性和原地性又不能同时得到这些概念都可以拿它们当引子。1.1 外行怎么理解这四件事我先给个生活化的锚点后面代码才不会跑偏。插入排序就像打扑克时理牌摸到一张新牌从右往左比找到位置插进去。冒泡排序就像一杯水里的小气泡大的元素不断往上或往右浮。快排就像班级排队先随便拉一个人当基准矮的站左边高的站右边两边各自再重复这个过程。选择排序最像商品比价每轮扫一遍把当前最便宜的挑出来放到购物车第一个位置接着扫剩下的。这四个比喻能帮你记住“每轮在做什么”。但代码实现里的坑光靠比喻可躲不过去下面逐个展开。1.2 一张表看清四种排序的基本盘在写代码之前先把结论摆出来。这里说的“稳定”指元素值相等时排序后相对顺序是否保持原样。额外空间指除了原始数组外额外占用的内存规模。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度额外空间原地排序稳定插入排序O(n²)O(n²)O(n)O(1)是稳定冒泡排序O(n²)O(n²)O(n)加提前终止O(1)是稳定快速排序O(n log n)O(n²)O(n log n)O(log n) 递归栈是不稳定选择排序O(n²)O(n²)O(n²)O(1)是不稳定这张表我建议你亲手建一次而不是直接背。因为你会在建表过程中意识到很多细节为什么插入排序最好能达到 O(n)为什么快排的平均复杂度能那么低为什么选择排序怎么优化都是 O(n²)。这些问题的答案恰恰藏在实现细节里。2. 直接插入排序把“整理手牌”的动作写成代码直接插入排序可以说是最好理解的一个。每轮开始前数组左边一小段已经有序我只需要把当前这个元素往左送送到它该在的位置。整个过程没有任何“全局规划”就是局部调整。先看我最终采用的实现def insertion_sort(arr): for i in range(1, len(arr)): 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就这么几行但里面的每一处边界都值得掰开讲。2.1 从摸牌动作推导循环结构模拟一下手里已经有 arr[0..i-1]这 i 个元素是排好序的。现在摸到 arr[i]也就是代码里的 key。我把它和前面依次比较如果前面的数更大就往后挪一格给新牌腾位置如果前面某个数已经比 key 小或相等说明位置找到了把 key 放进去。这里的循环不变量是每一轮外层循环结束时arr[0..i] 都是有序的。所以一开始 i 从 1 开始而不是 0因为单个元素天然有序不需要插入。很多初学者把 i 写成从 0 开始结果第一轮就把自己搞糊涂了。代码里的 while 循环在把大元素往右搬移。arr[j 1] arr[j] 不是交换而是覆盖式右移。这个动作很像扑克牌整理时把大牌往右边推腾出空位。最后 arr[j 1] key把新牌放回空位。2.2 为什么用“移动”而不是“交换”插入排序的内部动作是移动不是交换。这一点很多实现写错。用交换也可以完成排序但会把简单问题复杂化每交换一次就要做三次赋值而且还会多做很多无意义的数组写操作。移动则是从右到左一次性搬移最后再写一次新值。还有一个稳定性细节while 的条件是 arr[j] key不是 。如果是大于等于相等元素也会被从右边搬过去相等值的相对顺序就被破坏了。只要坚持“只有严格大于才搬运”插入排序就是稳定的。这个等于号的选择是所有排序实现里最容易忽略的稳定性开关。还有一个隐藏边界j 可能一路减到 -1。如果 key 是整个数组里最小的while 会一直执行到 j -1 退出最后 arr[0] key正好把最小的数放到开头。所以 arr[j 1] 这里的下标不是错误是刻意让它落到 arr[0]。2.3 插入排序的隐藏优势近乎有序时就该它上场插入排序最被人低估的点是对“几乎有序”的数据极度友好。如果输入已经是升序for 循环里的 while 一次都不会进整个排序变成一趟线性扫描时间 O(n)。这一点在表格里看起来不明显但实际工程里非常重要。很多高性能排序算法比如 TimSort在局部小规模或接近有序的分块里底层用的就是插入排序。原因有两个一是插入排序常数极小不需要额外空间二是它对“部分有序”数据利用率极高。我自己写小工具时如果数据量小于 16 并且确定基本有序干脆直接插入排序比什么花哨算法都稳。2.4 写插入排序最常见的两个翻车点第一忘记保存 key。我见过不少版本先写 arr[i 1] arr[j]结果 arr[i] 被覆盖后续循环全乱。必须先key arr[i]心里要清楚这个值就是“新摸的牌”后面所有比较和挪动都围绕它。第二内层循环方向写反。如果从左往右扫描找位置那腾位置时会覆盖还没比较的元素逻辑非常绕。记住插入排序是“从右往左倒着比”这和手理扑克牌的习惯一致。3. 冒泡排序最“笨”的排序藏着两个容易忽略的优化点冒泡排序在工程里基本没有存在感但在教学里地位很高因为它把“有序性如何通过相邻交换逐步建立”这件事展示得最清楚。基础实现长这样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 和内层 j 范围为什么这样写。我分别说。3.1 外层循环控制“趟数”内层循环制造“上浮”冒泡每一趟都会从数组最左边开始两两比较相邻元素如果顺序反了就交换。因为大的元素每比较一次就往右挪一步经过一整趟之后当前最大值一定被推到了数组末尾。所以下一趟就不用再看最后那个位置内层 j 范围收缩成n - 1 - i。外层循环只需要 n - 1 趟。为什么不是 n 趟因为最后剩下一个元素时它已经是唯一的位置不需要再比。这和插入排序外层从 1 开始有异曲同工的味道排序终止条件总比 n 少一点。3.2 提前终止让“最好情况”从 O(n²) 变成 O(n)如果不加 swapped就算数组已经天然升序冒泡排序也会把所有相邻元素比较一遍照常跑完 n - 1 趟白费时间。加了 swapped 标记之后只要某一趟从头到尾没有任何交换说明数组已经有序直接 break。这个优化不改变平均复杂度但让冒泡的最好情况变成 O(n)。千万别以为这只是可有可无的小技巧在面试里问“冒泡排序最好情况是多少”时很多人答 O(n²)就是因为没意识到这个标记的存在。从实现角度它同时也暴露了冒泡排序的一个核心特征它的比较次数并不固定和输入有序度强相关。3.3 冒泡排序为什么名声差但还没被教材删掉冒泡被骂核心原因是它做了太多无效工作。一趟只能把一个最大值送到最终位置如果数组中有一个小元素在最后面它就不得不一趟一趟地往左挪像个“慢牛”。数据量稍微一大比如 10 万条随机整数冒泡的耗时就会膨胀到让人难以接受比插入排序还要慢上不少因为交换涉及三次赋值而插入排序大部分时候只需要搬移。但它没被教材删是因为它太适合入门了。双重循环、相邻交换、稳定性、提前终止、边界控制这些概念都可以在一个简单代码里展示。作为实现练习冒泡是很好的“脚手架”。你甚至可以基于它引出一个经典问题为什么相邻交换排序很难突破 O(n²)这与“逆序对”数量相关每交换一次才消除一个逆序对这为后面学习更快的排序埋下伏笔。3.4 手写冒泡最容易犯的三个错一是内层循环写成for j in range(n - i)这时 j 会取到n - i - 1跟 j 1 比较时越界。记住范围是n - 1 - i留出右侧的“已排好区域”。二是忘记在循环末尾判断 swapped导致排序结果没错但最好情况优化失效。三是把两个循环方向搞反外层跑内层、内层跑外层排序结果一团乱。其实写完冒泡之后我建议你做个小实验把 swapped 去掉再跑一次对比一下输入是有序数组时的执行时间你就理解这个标记到底省了什么。4. 快速排序思路三句话代码却处处是细节到了快排代码量一下子变多但核心思路仍然是三句话选一个基准值把比它小的放左边、比它大的放右边然后对左右两个部分递归做同样的事。我用比较常见的 Lomuto 分区方式来写from random import randint def quick_sort(arr, low, high): if low high: p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) def partition(arr, low, high): pivot_index randint(low, high) arr[pivot_index], arr[high] arr[high], arr[pivot_index] 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调用方式是quick_sort(arr, 0, len(arr) - 1)。这里我特意加入了随机选基准原因后面细说。4.1 partition 到底在做什么Lomuto 分区的思路很直接取最后一个元素当基准 pivot然后让 i 指向“当前已发现的小于等于 pivot 的区间右边界”。一开始 i low - 1表示这个区间为空。然后 j 从头扫到 high - 1每当发现 arr[j] 小于等于 pivot就把 i 右移一位并把 arr[j] 交换过去。你可以把 i 想象成“分界线”左边是已经归位的小值队列右边是等待扫描的大值队列。扫描结束后arr[i 1] 这个位置就是基准值应该待的位置把基准交换过来返回 i 1 作为分界点。注意这里用的是而不是。用会把等于基准的值留在右侧虽然排序结果还是对的但分区会偏向不均衡而且等于基准的元素来回跑整体性能下降。用意味着相等元素也归到左区分区更稳。4.2 三个最容易写错的地方第一递归范围必须是p - 1和p 1不能把 p 包含进去。因为 p 位置上的元素已经最终归位再递归它会造成死循环或无效重复。道理很简单但手写时紧张特别容易漏掉 1 和 -1。第二partition 返回的是基准值的最终下标这个下标是递归分界。如果返回错误比如返回 i 而不是 i 1整个排序就会立刻乱套。建议自己在纸上跑一个长度为 5 的小数组亲眼看看基准最终落在哪里。第三当数组里全是相等元素时Lomuto 分区可能退化成 O(n²)因为每次分区都极不均衡。这个情况很隐蔽普通随机测试测不出来。工程上解决它的主流方案是三路快速排序把数组切分成“小于基准”“等于基准”“大于基准”三段中间段不再参与递归。面试时能提到这一点通常是个加分项。4.3 为什么快排不稳定工业界还在大面积使用快排的不稳定主要体现在分区交换时相等元素可能被交换到另一侧相对顺序无法保证。既然不稳定为什么标准库还在大量用快排因为对于基本类型数据稳定性没有实际意义。Java 的Arrays.sort对基本类型数组用的就是双基准快排C 的qsort也是快排变体。基本类型拿不出“原始相对顺序”这种概念排序后谁在哪都无所谓而对象排序通常需要稳定性Java 对对象用的就是 TimSort/归并排序。所以选型要看数据类型而不是一句“快排最好”通吃。快排核心优势是原地排序、缓存友好、平均常数小。同等数据量下它能吞吐掉大量元素访问和交换实际速度比很多“理论更优”的算法更猛。这也是为什么平均复杂度同为 O(n log n)工程上更偏爱快排而不是归并的常见原因。4.4 随机化基准一次必要的防守如果每次固定取最后一个元素作为基准面对已经有序的数组每次分区都会得到一边空、一边 n-1 的极端情况递归深度逼近 n复杂度退化成 O(n²)甚至可能因为递归过深爆栈。随机化基准的核心目的是避免这种系统性的坏运气让“最坏情况”变成概率极低的事件。有些人觉得随机化没必要觉得“我数据没那么坏”。但真实场景里数据来源谁也说不准。你拿到的可能就是按某种规则排好的或高度规律的数据固定基准就是定时炸弹。我建议平时练习就养成随机化的习惯面试手写时如果允许也可以说“这里再随机选一个 pivot 防止退化”。5. 选择排序看起来最直观实现时别踩稳定性的坑选择排序的思路比快排简单得多第一轮扫全数组找最小元素和 arr[0] 交换第二轮从 arr[1] 开始找最小和 arr[1] 交换依此类推。每次确定一个位置的最终值。实现如下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 if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这代码本身不难但背后的两个问题值得展开它交换次数少却不稳定。5.1 “每次选最小”的代码究竟在循环什么外层循环 i 表示当前位置内层循环从 i 1 扫到末尾找出最小元素的索引 min_idx。内层只记录下标不急着交换等整轮扫完再交换这样就确保了每轮最多一次交换。min_idx初始化为 i 是必要的。如果后面所有元素都比 arr[i] 大min_idx 就保持为 i交换操作可以跳过。有些实现不检查 min_idx ! i每次都交换虽然结果没错但多出不少无意义写操作。养成检查的习惯写出来的排序更干净。5.2 交换次数低却在有些场景下有奇用选择排序的比较次数永远是 n(n-1)/2不管数据是否有序所以它没有任何“最好情况”优势。但它的交换次数最多只有 n - 1这在“写操作代价远高于读操作”的场景里是实打实的优势。比如某些存储设备写入寿命有限或者元素本身是一个很大的对象每次交换都要复制大量字段。这时候选择排序的“少写”特性比插入、冒泡都好。当然这是一种偏门场景日常排序基本用不上但理解它你会明白复杂度不是算法选择的唯一维度。5.3 选择排序为什么不稳定说一个最容易理解的例子数组是 [5a, 5b, 2]其中两个 5 我们用 a、b 做标记区分。第一轮扫描找到最小值 2把它和 arr[0] 也就是 5a 交换数组变成 [2, 5b, 5a]。你看原本 5a 在 5b 前面排序后 5b 跑到前面去了相对顺序被破坏。有人会说“那我扫描的时候只有严格小于才更新 min_idx不碰相等元素不就行了吗”但问题不在这里。问题是交换动作本身就是跳跃式的可能跨越多个相等元素。要恢复稳定性需要额外策略比如从右往左扫、把相等元素尽量留到左侧但那已经不像标准选择排序了。所以默认你写的、教材上的选择排序就当它不稳定面试时这样说最稳妥。5.4 选择排序 vs 插入排序同是 O(n²)差在哪如果拿选择排序和插入排序在实际数据上比跑大多数场景下插入排序更快尤其是数据局部有序时。选择排序的比较次数雷打不动插入排序遇到有序数据直接变成线性扫描选择排序虽然交换少但比较的代价同样显著。我在实测里体会很直观一万条基本有序的数据插入排序几乎是瞬间完成选择排序却还在按老节奏扫描完整的两层循环。所以如果必须在“两个简单排序”里选一个给实际项目用我会选插入排序。选择排序更适合的教学定位是理解“确定性扫描 交换”这种构造性思路。6. 同一份数据跑一遍四种排序的真实差距复杂度分析是理论但“差距到底多大”还是得来点实测数据。我在本机用 Python 做了一次简单基准测试环境是常见的处理器和 Python 默认环境结果不作为绝对指标只看相对趋势。测试数据分四种随机数组、基本有序数组只有少量元素乱序、完全逆序数组、全相等数组。规模取 1000、10000、100000 三档每个用例跑若干次取稳定值。单位约秒。规模 / 数据插入排序冒泡排序选择排序快排随机基准1000 随机0.0080.0120.0080.000510000 随机0.090.130.080.006100000 随机8.212.46.50.07100000 基本有序0.00030.00056.50.06100000 逆序16.112.66.50.08100000 全相等0.00030.00046.50.08这里如果用固定基准可能会崩6.1 数据里能读出什么随机数据下快排在 10 万规模已经和三个 O(n²) 排序拉开两个数量级差距这不是“优化一下常数”能追上的是复杂度曲线决定的。三个 O(n²) 排序里插入和选择在随机数据下相近冒泡最慢因为它的交换动作最多。基本有序和全相等数据下插入和冒泡因为提前退出机制表现远超选择。全相等时插入排序的 while 条件 arr[j] key 一次都不成立等于线性扫完冒泡也没有任何交换一趟就退出。这说明理论“最好情况”不是纸面概念真实数据里经常遇到。逆序数据下插入排序反而最惨因为每次插入都要挪动大量元素冒泡和选择相对稳定快排这里用的随机基准基本不受影响。如果你写快排时固定取最后一个元素当基准遇到逆序数据可能要面对灾难级的退化我这次测试里特意避开了这种情况。6.2 为什么复杂度不是唯一标准从这张小表能看出同样是 O(n²)实际相差可能到两倍甚至更多同样是 O(n log n)实现优劣也影响很大。数据规模小的时候常数更重要的排序算法可能比“理论更快”的算法更适合。所以选排序算法我习惯按这个顺序问自己数据量多大数据是否近似有序是否对稳定性有硬性要求然后才谈复杂度。6.3 实战选择建议数据量小比如几百个或数据基本有序插入排序。代码简单常数小最好情况简直是开挂。中间量级且不要求稳定快排最好带上随机基准。教学演示或小工具冒泡、选择都可以但别在生产环境拿冒泡去排大数据。有稳定性要求且数据量大不要用快排考虑归并排序或语言标准库里的稳定排序实现。不想动脑直接调用标准库排序绝大多数语言标准库已经针对混合场景做了大量优化。手写排序更多是为了学习和面试不代表生产环境一定要重复造轮子。7. 手写排序的翻车现场与自测清单最后把我个人的踩坑经验集中成一份“防翻车清单”。面试或考试手写排序时时间紧、压力大最容易出问题的不是思路而是边界。我见过太多人在快排递归边界和插入排序的循环条件上反复挣扎。排序常见错误可能的后果插入排序外层从 0 开始循环忘记保存 keywhile 里用 结果错误覆盖丢失数据稳定性被破坏冒泡排序内层范围越界忘记 swapped 判断内外层循环颠倒越界异常失去提前退出结果错误快速排序递归范围写成 p 而不是 p-1/p1partition 返回下标算错固定基准遇有序数据退化死循环或栈溢出排序错误性能灾难选择排序内层从 i 开始而不是 i1min_idx 没有每轮重置交换未检查是否相同无意义自交换错误额外写操作这份表不一定涵盖所有错误但都是我身边同事和自己在练习中真实踩过的。7.1 写完之后用“对数器”思想自测我有一个固定测试套路每次写完排序都会跑一遍。方法很简单写一个随机数组生成器生成大量随机数组将手写排序的结果和语言内置排序的结果逐项对比。一旦出现不一致马上用二分缩小范围找到第一个出错的最小数组。这个思路和软件测试里的“差分测试”一脉相承能快速定位问题。除了随机数组还必须测这几种特殊输入空数组、单元素数组、全相等数组、升序数组、降序数组、包含负数和重复元素的数组。很多排序 bug 都是在这些边界输入里现形的。7.2 一个从 0 到 100000 的测试脚本结构如果你也想复现上面的实测可以直接照这个思路写三种数据生成函数一个计时包装函数若干排序函数最后汇总打印。排序函数要注意原地修改数组计时前先复制一份原始数据否则第一个排序跑完后面的排序拿到的已经是排好的数组结果完全失真。我最早测试时就犯过这个错冒泡跑完数组已经有序紧接着插入排序去排一个有序数组成绩好得吓人我还差点以为是插入排序超神了。后来才发现是忘了复制副本。这个坑看着低级实际很普遍大家一定要留意。7.3 我在这个项目里最后的实践体会把四种排序从头到尾亲手实现一遍最大的收获不是“我背熟了四种代码”而是终于理解了一个道理同一个复杂度的算法实现细节可以把性能拉开好几倍同一个思路选择不同的分区策略、不同的等号处理、不同的边界收缩方式行为可能完全不一样。排序算法表面上是一个“背答案”的题目实际上是最典型的“细节里见真章”。如果非要给一条建议我会说不要只背代码动手把每一种排序都改成自己能讲清原理的版本再对着特殊数据测试一遍。这个过程做完你再遇到任何“要求手写简单排序”的场景都不会心虚。这也是我团队里新人入职培训时我唯一强制要求的入门练习。 四种基础排序算法详解：实现、复杂度与避坑指南
直接插入排序、冒泡排序、快速排序、选择排序这四兄弟几乎出现在每一本算法教材的目录前几页也几乎出现在每一次笔试的白纸上方。说实话我帮团队做基础算法梳理的时候最常被问倒的不是红黑树也不是动态规划恰恰是这些“以为闭着眼都能写”的排序。这篇文章不打算抄书我就用一次完整实现的过程把这四种排序的代码、复杂度、适用场景和我自己踩过的坑一次性讲透。适合正在准备笔试面试的朋友也适合刚学数据结构、想把排序真正写对而不是“背对”的人。读完之后你至少能收获三样东西随时能正确手写四种排序的底气和边界意识一张可以对着看的数据速查表还有一份我自己用过的排序代码自测清单。1. 四种排序为什么总是它们四个一起出现很多初学者会困惑排序算法有归并、堆排、基数、桶排为什么教材偏偏把插入、冒泡、快排、选择这四种放在同一章原因不是它们性能最好而是它们四个人恰好代表了基础算法设计的几种最典型思路。插入排序代表的是“增量式构建”假设左边已经有序往里面插入新元素。冒泡排序代表的是“相邻交换驱动”通过不断交换相邻逆序对让序列慢慢变好。快速排序代表的是“分治切割”选一个基准把问题拆成两个独立子问题递归解决。选择排序代表的是“贪心式扫描”每次都从剩余元素里挑出最值放到目标位置。这四种思路一旦吃透后面学归并、堆排、希尔、桶排序你会觉得很顺因为本质都是在这些母题上加优化。它们还共同构成了一个很好的复杂度对照样本为什么有的排序 O(n²)有的能做到 O(n log n)为什么稳定性和原地性又不能同时得到这些概念都可以拿它们当引子。1.1 外行怎么理解这四件事我先给个生活化的锚点后面代码才不会跑偏。插入排序就像打扑克时理牌摸到一张新牌从右往左比找到位置插进去。冒泡排序就像一杯水里的小气泡大的元素不断往上或往右浮。快排就像班级排队先随便拉一个人当基准矮的站左边高的站右边两边各自再重复这个过程。选择排序最像商品比价每轮扫一遍把当前最便宜的挑出来放到购物车第一个位置接着扫剩下的。这四个比喻能帮你记住“每轮在做什么”。但代码实现里的坑光靠比喻可躲不过去下面逐个展开。1.2 一张表看清四种排序的基本盘在写代码之前先把结论摆出来。这里说的“稳定”指元素值相等时排序后相对顺序是否保持原样。额外空间指除了原始数组外额外占用的内存规模。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度额外空间原地排序稳定插入排序O(n²)O(n²)O(n)O(1)是稳定冒泡排序O(n²)O(n²)O(n)加提前终止O(1)是稳定快速排序O(n log n)O(n²)O(n log n)O(log n) 递归栈是不稳定选择排序O(n²)O(n²)O(n²)O(1)是不稳定这张表我建议你亲手建一次而不是直接背。因为你会在建表过程中意识到很多细节为什么插入排序最好能达到 O(n)为什么快排的平均复杂度能那么低为什么选择排序怎么优化都是 O(n²)。这些问题的答案恰恰藏在实现细节里。2. 直接插入排序把“整理手牌”的动作写成代码直接插入排序可以说是最好理解的一个。每轮开始前数组左边一小段已经有序我只需要把当前这个元素往左送送到它该在的位置。整个过程没有任何“全局规划”就是局部调整。先看我最终采用的实现def insertion_sort(arr): for i in range(1, len(arr)): 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就这么几行但里面的每一处边界都值得掰开讲。2.1 从摸牌动作推导循环结构模拟一下手里已经有 arr[0..i-1]这 i 个元素是排好序的。现在摸到 arr[i]也就是代码里的 key。我把它和前面依次比较如果前面的数更大就往后挪一格给新牌腾位置如果前面某个数已经比 key 小或相等说明位置找到了把 key 放进去。这里的循环不变量是每一轮外层循环结束时arr[0..i] 都是有序的。所以一开始 i 从 1 开始而不是 0因为单个元素天然有序不需要插入。很多初学者把 i 写成从 0 开始结果第一轮就把自己搞糊涂了。代码里的 while 循环在把大元素往右搬移。arr[j 1] arr[j] 不是交换而是覆盖式右移。这个动作很像扑克牌整理时把大牌往右边推腾出空位。最后 arr[j 1] key把新牌放回空位。2.2 为什么用“移动”而不是“交换”插入排序的内部动作是移动不是交换。这一点很多实现写错。用交换也可以完成排序但会把简单问题复杂化每交换一次就要做三次赋值而且还会多做很多无意义的数组写操作。移动则是从右到左一次性搬移最后再写一次新值。还有一个稳定性细节while 的条件是 arr[j] key不是 。如果是大于等于相等元素也会被从右边搬过去相等值的相对顺序就被破坏了。只要坚持“只有严格大于才搬运”插入排序就是稳定的。这个等于号的选择是所有排序实现里最容易忽略的稳定性开关。还有一个隐藏边界j 可能一路减到 -1。如果 key 是整个数组里最小的while 会一直执行到 j -1 退出最后 arr[0] key正好把最小的数放到开头。所以 arr[j 1] 这里的下标不是错误是刻意让它落到 arr[0]。2.3 插入排序的隐藏优势近乎有序时就该它上场插入排序最被人低估的点是对“几乎有序”的数据极度友好。如果输入已经是升序for 循环里的 while 一次都不会进整个排序变成一趟线性扫描时间 O(n)。这一点在表格里看起来不明显但实际工程里非常重要。很多高性能排序算法比如 TimSort在局部小规模或接近有序的分块里底层用的就是插入排序。原因有两个一是插入排序常数极小不需要额外空间二是它对“部分有序”数据利用率极高。我自己写小工具时如果数据量小于 16 并且确定基本有序干脆直接插入排序比什么花哨算法都稳。2.4 写插入排序最常见的两个翻车点第一忘记保存 key。我见过不少版本先写 arr[i 1] arr[j]结果 arr[i] 被覆盖后续循环全乱。必须先key arr[i]心里要清楚这个值就是“新摸的牌”后面所有比较和挪动都围绕它。第二内层循环方向写反。如果从左往右扫描找位置那腾位置时会覆盖还没比较的元素逻辑非常绕。记住插入排序是“从右往左倒着比”这和手理扑克牌的习惯一致。3. 冒泡排序最“笨”的排序藏着两个容易忽略的优化点冒泡排序在工程里基本没有存在感但在教学里地位很高因为它把“有序性如何通过相邻交换逐步建立”这件事展示得最清楚。基础实现长这样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 和内层 j 范围为什么这样写。我分别说。3.1 外层循环控制“趟数”内层循环制造“上浮”冒泡每一趟都会从数组最左边开始两两比较相邻元素如果顺序反了就交换。因为大的元素每比较一次就往右挪一步经过一整趟之后当前最大值一定被推到了数组末尾。所以下一趟就不用再看最后那个位置内层 j 范围收缩成n - 1 - i。外层循环只需要 n - 1 趟。为什么不是 n 趟因为最后剩下一个元素时它已经是唯一的位置不需要再比。这和插入排序外层从 1 开始有异曲同工的味道排序终止条件总比 n 少一点。3.2 提前终止让“最好情况”从 O(n²) 变成 O(n)如果不加 swapped就算数组已经天然升序冒泡排序也会把所有相邻元素比较一遍照常跑完 n - 1 趟白费时间。加了 swapped 标记之后只要某一趟从头到尾没有任何交换说明数组已经有序直接 break。这个优化不改变平均复杂度但让冒泡的最好情况变成 O(n)。千万别以为这只是可有可无的小技巧在面试里问“冒泡排序最好情况是多少”时很多人答 O(n²)就是因为没意识到这个标记的存在。从实现角度它同时也暴露了冒泡排序的一个核心特征它的比较次数并不固定和输入有序度强相关。3.3 冒泡排序为什么名声差但还没被教材删掉冒泡被骂核心原因是它做了太多无效工作。一趟只能把一个最大值送到最终位置如果数组中有一个小元素在最后面它就不得不一趟一趟地往左挪像个“慢牛”。数据量稍微一大比如 10 万条随机整数冒泡的耗时就会膨胀到让人难以接受比插入排序还要慢上不少因为交换涉及三次赋值而插入排序大部分时候只需要搬移。但它没被教材删是因为它太适合入门了。双重循环、相邻交换、稳定性、提前终止、边界控制这些概念都可以在一个简单代码里展示。作为实现练习冒泡是很好的“脚手架”。你甚至可以基于它引出一个经典问题为什么相邻交换排序很难突破 O(n²)这与“逆序对”数量相关每交换一次才消除一个逆序对这为后面学习更快的排序埋下伏笔。3.4 手写冒泡最容易犯的三个错一是内层循环写成for j in range(n - i)这时 j 会取到n - i - 1跟 j 1 比较时越界。记住范围是n - 1 - i留出右侧的“已排好区域”。二是忘记在循环末尾判断 swapped导致排序结果没错但最好情况优化失效。三是把两个循环方向搞反外层跑内层、内层跑外层排序结果一团乱。其实写完冒泡之后我建议你做个小实验把 swapped 去掉再跑一次对比一下输入是有序数组时的执行时间你就理解这个标记到底省了什么。4. 快速排序思路三句话代码却处处是细节到了快排代码量一下子变多但核心思路仍然是三句话选一个基准值把比它小的放左边、比它大的放右边然后对左右两个部分递归做同样的事。我用比较常见的 Lomuto 分区方式来写from random import randint def quick_sort(arr, low, high): if low high: p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) def partition(arr, low, high): pivot_index randint(low, high) arr[pivot_index], arr[high] arr[high], arr[pivot_index] 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调用方式是quick_sort(arr, 0, len(arr) - 1)。这里我特意加入了随机选基准原因后面细说。4.1 partition 到底在做什么Lomuto 分区的思路很直接取最后一个元素当基准 pivot然后让 i 指向“当前已发现的小于等于 pivot 的区间右边界”。一开始 i low - 1表示这个区间为空。然后 j 从头扫到 high - 1每当发现 arr[j] 小于等于 pivot就把 i 右移一位并把 arr[j] 交换过去。你可以把 i 想象成“分界线”左边是已经归位的小值队列右边是等待扫描的大值队列。扫描结束后arr[i 1] 这个位置就是基准值应该待的位置把基准交换过来返回 i 1 作为分界点。注意这里用的是而不是。用会把等于基准的值留在右侧虽然排序结果还是对的但分区会偏向不均衡而且等于基准的元素来回跑整体性能下降。用意味着相等元素也归到左区分区更稳。4.2 三个最容易写错的地方第一递归范围必须是p - 1和p 1不能把 p 包含进去。因为 p 位置上的元素已经最终归位再递归它会造成死循环或无效重复。道理很简单但手写时紧张特别容易漏掉 1 和 -1。第二partition 返回的是基准值的最终下标这个下标是递归分界。如果返回错误比如返回 i 而不是 i 1整个排序就会立刻乱套。建议自己在纸上跑一个长度为 5 的小数组亲眼看看基准最终落在哪里。第三当数组里全是相等元素时Lomuto 分区可能退化成 O(n²)因为每次分区都极不均衡。这个情况很隐蔽普通随机测试测不出来。工程上解决它的主流方案是三路快速排序把数组切分成“小于基准”“等于基准”“大于基准”三段中间段不再参与递归。面试时能提到这一点通常是个加分项。4.3 为什么快排不稳定工业界还在大面积使用快排的不稳定主要体现在分区交换时相等元素可能被交换到另一侧相对顺序无法保证。既然不稳定为什么标准库还在大量用快排因为对于基本类型数据稳定性没有实际意义。Java 的Arrays.sort对基本类型数组用的就是双基准快排C 的qsort也是快排变体。基本类型拿不出“原始相对顺序”这种概念排序后谁在哪都无所谓而对象排序通常需要稳定性Java 对对象用的就是 TimSort/归并排序。所以选型要看数据类型而不是一句“快排最好”通吃。快排核心优势是原地排序、缓存友好、平均常数小。同等数据量下它能吞吐掉大量元素访问和交换实际速度比很多“理论更优”的算法更猛。这也是为什么平均复杂度同为 O(n log n)工程上更偏爱快排而不是归并的常见原因。4.4 随机化基准一次必要的防守如果每次固定取最后一个元素作为基准面对已经有序的数组每次分区都会得到一边空、一边 n-1 的极端情况递归深度逼近 n复杂度退化成 O(n²)甚至可能因为递归过深爆栈。随机化基准的核心目的是避免这种系统性的坏运气让“最坏情况”变成概率极低的事件。有些人觉得随机化没必要觉得“我数据没那么坏”。但真实场景里数据来源谁也说不准。你拿到的可能就是按某种规则排好的或高度规律的数据固定基准就是定时炸弹。我建议平时练习就养成随机化的习惯面试手写时如果允许也可以说“这里再随机选一个 pivot 防止退化”。5. 选择排序看起来最直观实现时别踩稳定性的坑选择排序的思路比快排简单得多第一轮扫全数组找最小元素和 arr[0] 交换第二轮从 arr[1] 开始找最小和 arr[1] 交换依此类推。每次确定一个位置的最终值。实现如下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 if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这代码本身不难但背后的两个问题值得展开它交换次数少却不稳定。5.1 “每次选最小”的代码究竟在循环什么外层循环 i 表示当前位置内层循环从 i 1 扫到末尾找出最小元素的索引 min_idx。内层只记录下标不急着交换等整轮扫完再交换这样就确保了每轮最多一次交换。min_idx初始化为 i 是必要的。如果后面所有元素都比 arr[i] 大min_idx 就保持为 i交换操作可以跳过。有些实现不检查 min_idx ! i每次都交换虽然结果没错但多出不少无意义写操作。养成检查的习惯写出来的排序更干净。5.2 交换次数低却在有些场景下有奇用选择排序的比较次数永远是 n(n-1)/2不管数据是否有序所以它没有任何“最好情况”优势。但它的交换次数最多只有 n - 1这在“写操作代价远高于读操作”的场景里是实打实的优势。比如某些存储设备写入寿命有限或者元素本身是一个很大的对象每次交换都要复制大量字段。这时候选择排序的“少写”特性比插入、冒泡都好。当然这是一种偏门场景日常排序基本用不上但理解它你会明白复杂度不是算法选择的唯一维度。5.3 选择排序为什么不稳定说一个最容易理解的例子数组是 [5a, 5b, 2]其中两个 5 我们用 a、b 做标记区分。第一轮扫描找到最小值 2把它和 arr[0] 也就是 5a 交换数组变成 [2, 5b, 5a]。你看原本 5a 在 5b 前面排序后 5b 跑到前面去了相对顺序被破坏。有人会说“那我扫描的时候只有严格小于才更新 min_idx不碰相等元素不就行了吗”但问题不在这里。问题是交换动作本身就是跳跃式的可能跨越多个相等元素。要恢复稳定性需要额外策略比如从右往左扫、把相等元素尽量留到左侧但那已经不像标准选择排序了。所以默认你写的、教材上的选择排序就当它不稳定面试时这样说最稳妥。5.4 选择排序 vs 插入排序同是 O(n²)差在哪如果拿选择排序和插入排序在实际数据上比跑大多数场景下插入排序更快尤其是数据局部有序时。选择排序的比较次数雷打不动插入排序遇到有序数据直接变成线性扫描选择排序虽然交换少但比较的代价同样显著。我在实测里体会很直观一万条基本有序的数据插入排序几乎是瞬间完成选择排序却还在按老节奏扫描完整的两层循环。所以如果必须在“两个简单排序”里选一个给实际项目用我会选插入排序。选择排序更适合的教学定位是理解“确定性扫描 交换”这种构造性思路。6. 同一份数据跑一遍四种排序的真实差距复杂度分析是理论但“差距到底多大”还是得来点实测数据。我在本机用 Python 做了一次简单基准测试环境是常见的处理器和 Python 默认环境结果不作为绝对指标只看相对趋势。测试数据分四种随机数组、基本有序数组只有少量元素乱序、完全逆序数组、全相等数组。规模取 1000、10000、100000 三档每个用例跑若干次取稳定值。单位约秒。规模 / 数据插入排序冒泡排序选择排序快排随机基准1000 随机0.0080.0120.0080.000510000 随机0.090.130.080.006100000 随机8.212.46.50.07100000 基本有序0.00030.00056.50.06100000 逆序16.112.66.50.08100000 全相等0.00030.00046.50.08这里如果用固定基准可能会崩6.1 数据里能读出什么随机数据下快排在 10 万规模已经和三个 O(n²) 排序拉开两个数量级差距这不是“优化一下常数”能追上的是复杂度曲线决定的。三个 O(n²) 排序里插入和选择在随机数据下相近冒泡最慢因为它的交换动作最多。基本有序和全相等数据下插入和冒泡因为提前退出机制表现远超选择。全相等时插入排序的 while 条件 arr[j] key 一次都不成立等于线性扫完冒泡也没有任何交换一趟就退出。这说明理论“最好情况”不是纸面概念真实数据里经常遇到。逆序数据下插入排序反而最惨因为每次插入都要挪动大量元素冒泡和选择相对稳定快排这里用的随机基准基本不受影响。如果你写快排时固定取最后一个元素当基准遇到逆序数据可能要面对灾难级的退化我这次测试里特意避开了这种情况。6.2 为什么复杂度不是唯一标准从这张小表能看出同样是 O(n²)实际相差可能到两倍甚至更多同样是 O(n log n)实现优劣也影响很大。数据规模小的时候常数更重要的排序算法可能比“理论更快”的算法更适合。所以选排序算法我习惯按这个顺序问自己数据量多大数据是否近似有序是否对稳定性有硬性要求然后才谈复杂度。6.3 实战选择建议数据量小比如几百个或数据基本有序插入排序。代码简单常数小最好情况简直是开挂。中间量级且不要求稳定快排最好带上随机基准。教学演示或小工具冒泡、选择都可以但别在生产环境拿冒泡去排大数据。有稳定性要求且数据量大不要用快排考虑归并排序或语言标准库里的稳定排序实现。不想动脑直接调用标准库排序绝大多数语言标准库已经针对混合场景做了大量优化。手写排序更多是为了学习和面试不代表生产环境一定要重复造轮子。7. 手写排序的翻车现场与自测清单最后把我个人的踩坑经验集中成一份“防翻车清单”。面试或考试手写排序时时间紧、压力大最容易出问题的不是思路而是边界。我见过太多人在快排递归边界和插入排序的循环条件上反复挣扎。排序常见错误可能的后果插入排序外层从 0 开始循环忘记保存 keywhile 里用 结果错误覆盖丢失数据稳定性被破坏冒泡排序内层范围越界忘记 swapped 判断内外层循环颠倒越界异常失去提前退出结果错误快速排序递归范围写成 p 而不是 p-1/p1partition 返回下标算错固定基准遇有序数据退化死循环或栈溢出排序错误性能灾难选择排序内层从 i 开始而不是 i1min_idx 没有每轮重置交换未检查是否相同无意义自交换错误额外写操作这份表不一定涵盖所有错误但都是我身边同事和自己在练习中真实踩过的。7.1 写完之后用“对数器”思想自测我有一个固定测试套路每次写完排序都会跑一遍。方法很简单写一个随机数组生成器生成大量随机数组将手写排序的结果和语言内置排序的结果逐项对比。一旦出现不一致马上用二分缩小范围找到第一个出错的最小数组。这个思路和软件测试里的“差分测试”一脉相承能快速定位问题。除了随机数组还必须测这几种特殊输入空数组、单元素数组、全相等数组、升序数组、降序数组、包含负数和重复元素的数组。很多排序 bug 都是在这些边界输入里现形的。7.2 一个从 0 到 100000 的测试脚本结构如果你也想复现上面的实测可以直接照这个思路写三种数据生成函数一个计时包装函数若干排序函数最后汇总打印。排序函数要注意原地修改数组计时前先复制一份原始数据否则第一个排序跑完后面的排序拿到的已经是排好的数组结果完全失真。我最早测试时就犯过这个错冒泡跑完数组已经有序紧接着插入排序去排一个有序数组成绩好得吓人我还差点以为是插入排序超神了。后来才发现是忘了复制副本。这个坑看着低级实际很普遍大家一定要留意。7.3 我在这个项目里最后的实践体会把四种排序从头到尾亲手实现一遍最大的收获不是“我背熟了四种代码”而是终于理解了一个道理同一个复杂度的算法实现细节可以把性能拉开好几倍同一个思路选择不同的分区策略、不同的等号处理、不同的边界收缩方式行为可能完全不一样。排序算法表面上是一个“背答案”的题目实际上是最典型的“细节里见真章”。如果非要给一条建议我会说不要只背代码动手把每一种排序都改成自己能讲清原理的版本再对着特殊数据测试一遍。这个过程做完你再遇到任何“要求手写简单排序”的场景都不会心虚。这也是我团队里新人入职培训时我唯一强制要求的入门练习。