直接插入排序、冒泡排序、快速排序、选择排序，这四兄弟几乎出现在每一本算法教材的目录前几页，也几乎出现在每一次笔试的白纸上方。说实话，我帮团队做基础算法梳理的时候，最常被问倒的不是红黑树，也不是动态规划，恰恰是这些“以为闭着眼都能写”的排序。

这篇文章不打算抄书，我就用一次完整实现的过程，把这四种排序的代码、复杂度、适用场景和我自己踩过的坑一次性讲透。适合正在准备笔试面试的朋友，也适合刚学数据结构、想把排序真正写对而不是“背对”的人。读完之后你至少能收获三样东西：随时能正确手写四种排序的底气和边界意识，一张可以对着看的数据速查表，还有一份我自己用过的排序代码自测清单。

1. 四种排序，为什么总是它们四个一起出现

很多初学者会困惑：排序算法有归并、堆排、基数、桶排，为什么教材偏偏把插入、冒泡、快排、选择这四种放在同一章？原因不是它们性能最好，而是它们四个人恰好代表了基础算法设计的几种最典型思路。

插入排序代表的是“增量式构建”：假设左边已经有序，往里面插入新元素。冒泡排序代表的是“相邻交换驱动”：通过不断交换相邻逆序对，让序列慢慢变好。快速排序代表的是“分治切割”：选一个基准，把问题拆成两个独立子问题递归解决。选择排序代表的是“贪心式扫描”：每次都从剩余元素里挑出最值，放到目标位置。

这四种思路一旦吃透，后面学归并、堆排、希尔、桶排序，你会觉得很顺，因为本质都是在这些母题上加优化。它们还共同构成了一个很好的复杂度对照样本：为什么有的排序 O(n²)，有的能做到 O(n log n)，为什么稳定性和原地性又不能同时得到，这些概念都可以拿它们当引子。

1.1 外行怎么理解这四件事

我先给个生活化的锚点，后面代码才不会跑偏。插入排序就像打扑克时理牌，摸到一张新牌，从右往左比，找到位置插进去。冒泡排序就像一杯水里的小气泡，大的元素不断往上（或往右）浮。快排就像班级排队，先随便拉一个人当基准，矮的站左边，高的站右边，两边各自再重复这个过程。选择排序最像商品比价：每轮扫一遍，把当前最便宜的挑出来，放到购物车第一个位置，接着扫剩下的。

这四个比喻能帮你记住“每轮在做什么”。但代码实现里的坑，光靠比喻可躲不过去，下面逐个展开。

1.2 一张表看清四种排序的基本盘

在写代码之前，先把结论摆出来。这里说的“稳定”，指元素值相等时，排序后相对顺序是否保持原样。额外空间指除了原始数组外，额外占用的内存规模。

这张表我建议你亲手建一次，而不是直接背。因为你会在建表过程中意识到很多细节：为什么插入排序最好能达到 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 三档，每个用例跑若干次取稳定值。单位约秒。

6.1 数据里能读出什么

随机数据下，快排在 10 万规模已经和三个 O(n²) 排序拉开两个数量级差距，这不是“优化一下常数”能追上的，是复杂度曲线决定的。三个 O(n²) 排序里，插入和选择在随机数据下相近，冒泡最慢，因为它的交换动作最多。

基本有序和全相等数据下，插入和冒泡因为提前退出机制，表现远超选择。全相等时，插入排序的 while 条件 arr[j] > key 一次都不成立，等于线性扫完；冒泡也没有任何交换，一趟就退出。这说明理论“最好情况”不是纸面概念，真实数据里经常遇到。

逆序数据下，插入排序反而最惨，因为每次插入都要挪动大量元素；冒泡和选择相对稳定；快排这里用的随机基准，基本不受影响。如果你写快排时固定取最后一个元素当基准，遇到逆序数据可能要面对灾难级的退化，我这次测试里特意避开了这种情况。

6.2 为什么复杂度不是唯一标准

从这张小表能看出，同样是 O(n²)，实际相差可能到两倍甚至更多；同样是 O(n log n)，实现优劣也影响很大。数据规模小的时候，常数更重要的排序算法可能比“理论更快”的算法更适合。所以选排序算法，我习惯按这个顺序问自己：数据量多大？数据是否近似有序？是否对稳定性有硬性要求？然后才谈复杂度。

6.3 实战选择建议

• 数据量小（比如几百个）或数据基本有序：插入排序。代码简单，常数小，最好情况简直是开挂。
• 中间量级且不要求稳定：快排，最好带上随机基准。
• 教学演示或小工具：冒泡、选择都可以，但别在生产环境拿冒泡去排大数据。
• 有稳定性要求且数据量大：不要用快排，考虑归并排序或语言标准库里的稳定排序实现。
• 不想动脑：直接调用标准库排序，绝大多数语言标准库已经针对混合场景做了大量优化。手写排序更多是为了学习和面试，不代表生产环境一定要重复造轮子。

7. 手写排序的翻车现场与自测清单

最后把我个人的踩坑经验集中成一份“防翻车清单”。面试或考试手写排序时，时间紧、压力大，最容易出问题的不是思路，而是边界。我见过太多人在快排递归边界和插入排序的循环条件上反复挣扎。

这份表不一定涵盖所有错误，但都是我身边同事和自己在练习中真实踩过的。

7.1 写完之后，用“对数器”思想自测

我有一个固定测试套路，每次写完排序都会跑一遍。方法很简单：写一个随机数组生成器，生成大量随机数组，将手写排序的结果和语言内置排序的结果逐项对比。一旦出现不一致，马上用二分缩小范围，找到第一个出错的最小数组。这个思路和软件测试里的“差分测试”一脉相承，能快速定位问题。

除了随机数组，还必须测这几种特殊输入：空数组、单元素数组、全相等数组、升序数组、降序数组、包含负数和重复元素的数组。很多排序 bug 都是在这些边界输入里现形的。

7.2 一个从 0 到 100000 的测试脚本结构

如果你也想复现上面的实测，可以直接照这个思路写：三种数据生成函数，一个计时包装函数，若干排序函数，最后汇总打印。排序函数要注意原地修改数组，计时前先复制一份原始数据，否则第一个排序跑完，后面的排序拿到的已经是排好的数组，结果完全失真。

我最早测试时就犯过这个错：冒泡跑完，数组已经有序，紧接着插入排序去排一个有序数组，成绩好得吓人，我还差点以为是插入排序超神了。后来才发现是忘了复制副本。这个坑看着低级，实际很普遍，大家一定要留意。

7.3 我在这个项目里最后的实践体会

把四种排序从头到尾亲手实现一遍，最大的收获不是“我背熟了四种代码”，而是终于理解了一个道理：同一个复杂度的算法，实现细节可以把性能拉开好几倍；同一个思路，选择不同的分区策略、不同的等号处理、不同的边界收缩方式，行为可能完全不一样。排序算法表面上是一个“背答案”的题目，实际上是最典型的“细节里见真章”。

如果非要给一条建议，我会说：不要只背代码，动手把每一种排序都改成自己能讲清原理的版本，再对着特殊数据测试一遍。这个过程做完，你再遇到任何“要求手写简单排序”的场景，都不会心虚。这也是我团队里新人入职培训时，我唯一强制要求的入门练习。