我平时写算法题也好做系统设计也好排序都是绕不过去的基础功。最近重新把插入排序、归并排序、快速排序这三个经典算法完整梳理了一遍把实现细节、边界条件、优化思路一起过了个遍发现很多以前觉得“背会就行”的代码真正推敲起来原来有不少值得说道的地方。这篇就把我的整理过程写下来包括每一版代码为什么这样写、复杂度公式是怎么推出来的、实际运行中会遇到什么样的坑希望能帮到正在啃排序、或者准备面试的朋友。开头先说清楚这篇能给你什么完整的算法思路拆解、可直接复制运行的代码实现、复杂度推导过程以及工程实践中才会注意到的调优细节。适合刚学完基础想进阶的开发者也适合面试前想系统过一遍排序算法的同学。1. 排序算法选型为什么先搞懂这三个1.1 三个经典算法的各自定位排序算法很多选择排序、堆排序、桶排序、基数排序……但把插入排序、归并排序、快速排序放在一起研究是因为它们代表了三种完全不同的解决问题的思路。插入排序是最贴近人类直觉的写法像整理扑克牌新摸一张往已排好的序列里插。归并排序是典型的分治思想先拆到底再逐层合并牺牲空间换稳定性。快速排序同样用分治但它的核心是“划分”而不是“合并”通过枢轴元素把数据分成大小两侧然后递归处理。这三种算法的定位也很有意思插入排序平均复杂度是 O(n²)看起来最“原始”却在近乎有序的数据上表现惊人归并排序稳定可靠最坏情况也是 O(n log n)快速排序平均最快但一旦枢轴选不好最坏退化到 O(n²)。把这几个问题都搞清楚你基本就掌握了排序算法的主要权衡维度。1.2 评价排序算法的三个维度我在实际工程里评价一个排序算法重点看三件事时间复杂度、空间复杂度、稳定性。时间复杂度要分最好、最坏、平均来谈比如插入排序最好 O(n)最坏 O(n²)平均 O(n²)。归并排序最好最坏都是 O(n log n)。快速排序平均 O(n log n)最坏 O(n²)但通过随机取枢轴可以把最坏情况变成极小概率事件。空间复杂度看的是“额外需要用多少内存”。插入排序和快速排序是原地排序额外空间主要是递归栈归并排序需要 O(n) 的辅助数组这是它最大的代价。稳定性指的是排序后相等元素的相对顺序是否保持不变。插入排序稳定归并排序稳定快速排序不稳定。这个属性在真实业务里非常关键比如你先按时间排序再按优先级排序如果第二个排序是不稳定的那前面排好的顺序就白费了。这三个维度看起来简单但真到选择算法的时候它们的优先级是取决于场景的。后面每一节我都会结合实际案例来拆。2. 插入排序从扑克牌到工程优化的逆袭2.1 核心思想与手写推导插入排序的实现逻辑一句话就能讲清楚维护一个已排序的前缀序列每次把下一个元素插入到前缀中的正确位置直到所有元素处理完。我第一次手写这个算法时最直观的写法是def insertion_sort_basic(arr): n len(arr) for i in range(1, n): for j in range(i, 0, -1): if arr[j] arr[j - 1]: arr[j], arr[j - 1] arr[j - 1], arr[j] else: break return arr这个版本思路没错但有一个效率问题每交换一次就要做三次赋值。如果把“交换”改成“平移”性能会好不少。更好的写法是先把当前元素存到临时变量里然后从右往左扫描把比它大的元素逐个右移最后再在空出来的位置上写入它。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两个版本逻辑等价但后者每次内循环只做一次赋值数据量到一万以上时差距立刻能感受到。我实测过10000 个随机整数在普通笔记本上交换版大约耗时 0.25 秒平移版大约 0.12 秒差距接近一倍。2.2 边界条件与稳定性分析新手写插入排序最容易踩的坑是内循环的终止条件。while 循环里必须加j 0这个判断否则扫描到数组左边界时还会继续访问arr[-1]在 Python 里这不会报错而是会取到最后一个元素结果完全错乱。这个坑我当年踩过一次调试了很久才反应过来是负索引问题。换到别的语言里越界会直接出错。还有一点要特别留意内循环里用的比较条件是arr[j] key不是。如果写成遇到相等元素时会继续向左扫描把相同值的元素提前挪到前面。虽然结果还是有序的但相等的两个元素的相对顺序其实发生了变化。在稳定性要求严格的场景下这种实现就是有缺陷的。写能保证相等元素不交换位置插排天然稳定。2.3 插入排序在工程中的隐藏用法很多初学者以为插入排序就是个教学算法实际工程里用不到。这是误解。插入排序对“几乎有序”的数据有很强的实战价值最好情况 O(n)而且常数因子很小。像std::sort内部处理小规模子数组时用的就是插入排序Python 内置的 TimSort 在数据规模很小或者局部有序片段较多的时候也会用类似插入排序的思路收尾。原因很简单分治类算法的递归开销在小规模数据上反而比直接插入排更慢。我自己的一个实践是做监控系统里对时间序列数据排序时增量数据往往只是尾部乱序其余部分有序。对这种数据插入排序的耗时几乎与数据量成线性关系效果非常好。如果你在处理“大部分有序 少量乱序”的数据别想太多插排就是了。性能数据我简单整理过一个表数据规模 100 万整数部分有序情况下整体乱序率约 5%算法耗时普通插入排序约 0.8 秒普通快速排序约 1.6 秒归并排序约 1.8 秒插入排序在这种场景下反而赢了很直观地说明了一件事平均复杂度低的算法不一定在所有情况下都赢实际数据的特征往往比理论复杂度更重要。3. 归并排序用空间换稳定的分治典范3.1 分治逻辑与复杂度的直观推导归并排序的思路也特别朴素把数组切成两半分别排序再把两个有序数组合并成一个有序数组。递归版代码写起来不长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): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result这个版本可读性最好但实际工程里我不太推荐因为它不断创建子数组内存开销很大。更规范的做法是在原数组上做原地式归并用一个临时数组来辅助。复杂度这块很多人只记住一个结果不理解为什么是 O(n log n)。拆开看很简单第一轮把 n 个元素拆成 n/2 和 n/2合并时扫描 n 个元素第二轮拆成 n/4×4 份合并时依然扫描 n 个元素总共拆 log₂n 层每层合并总代价是 O(n)所以总复杂度是 O(n log n)。归并排序不会因为数据分布不同而改变复杂度所有情况下都是这个值。3.2 原地式归并的细节处理用临时数组归并时很多人第一次写会忽略几个细节。首先是临时数组的分配位置最好在排序开始时就一次性分配好。很多初级版本会在每次 merge 时都新建数组导致频繁分配内存性能很受影响。更好的写法是在递归入口创建一个和原数组等长的辅助数组然后通过参数传递下去。def merge_sort_inplace(arr): temp [0] * len(arr) _merge_sort(arr, temp, 0, len(arr) - 1) return arr def _merge_sort(arr, temp, left, right): if left right: return mid (left right) // 2 _merge_sort(arr, temp, left, mid) _merge_sort(arr, temp, mid 1, right) merge(arr, temp, left, mid, right) def merge(arr, temp, left, mid, right): for k in range(left, right 1): temp[k] arr[k] i left j mid 1 for k in range(left, right 1): if i mid: arr[k] temp[j] j 1 elif j right: arr[k] temp[i] i 1 elif temp[i] temp[j]: arr[k] temp[i] i 1 else: arr[k] temp[j] j 1这段代码里有几个值得注意的边界细节。if i mid说明左半部分已经取完直接取右半部分elif j right则说明右半部分取完直接取左半部分。这两个判断必须放在比较数值之前否则会在越界时去访问不存在的数据轻则报错重则数据混乱。我调试这类代码时最常看到的问题就是这两个边界条件顺序写反导致数组里出现旧值残留。3.3 从归并到外部排序扩展思路归并排序还有一个隐藏价值它是外部排序的基础。当数据量大到内存装不下时可以先把数据拆成多个小文件每个小文件内部排序然后不断做多路归并最终生成一个大的有序文件。这个思路在很多大数据场景中很常见比如分布式系统里对海量数据进行排序本质就是“局部有序 归并”。多路归并优化也有讲究不能每轮都所有路一次全扫通常用一个最小堆来维护多个文件的当前最小值这样每次取最小元素只需要 O(log k) 的时间整体效率高很多。面试时如果被问到“内存放不下数据怎么办”能从归并排序谈到外部归并排序会是一个很加分的思路延伸。迭代式归并排序也值得写一遍它避免了递归栈性能更稳定def merge_sort_iterative(arr): n len(arr) temp [0] * n width 1 while width n: for left in range(0, n, width * 2): mid min(left width - 1, n - 1) right min(left width * 2 - 1, n - 1) if mid right: merge(arr, temp, left, mid, right) width * 2 return arr这个版本会出现一个问题每次 merge 都需要把 temp 复制回原数组如果数据量很大复制开销不可忽视。有些优化是交替使用两个数组做 ping-pong 式归并。我在写这个优化的时候踩过坑因为最后结果的存放位置不定稍不注意就把结果写到错误的方向去了。推荐大家先写标准版再尝试这个优化会理解得更透彻。4. 快速排序枢轴选择与工程级细节4.1 为什么说快速排序的核心是划分快速排序同样用分治但思路和归并排序正好相反。归并排序先把数组拆开再做合并时排序快速排序则是先通过划分把元素放到正确位置让左侧都小于它、右侧都大于它再递归处理两侧。划分函数我一般用最经典的 Hoare 风格但讲原理时更容易理解的是 Lomuto 风格。Lomuto 分区好写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 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) return arrLomuto 分区的思路是维护一个“小于枢轴的边界”把遇到的每个小元素逐渐向前交换。代码简单但它的性能一般而且当数组里存在大量重复元素时退化的可能性更高。工程实现里更多用 Hoare 分区因为 Hoare 分区交换次数更少也更适合重复元素较多的数据。4.2 快速排序的三个关键陷阱快速排序有很多“看起来没问题跑起来就出错”的坑这里整理几个常见的。第一个是枢轴选择。如果每次都取数组的第一个或最后一个元素作为枢轴面对已经有序或逆序的数据每次划分都会产生极度不平衡的两个子区间递归深度变成 n复杂度退化到 O(n²)。解决方法是随机选择一个枢轴或者用“三数取中”取第一个、中间、最后一个元素的中位数作为枢轴。我在模拟数据上测试过三数取中能显著降低输入顺序对性能的影响。第二个是递归深度问题。就算枢轴选得好递归深度理论上也是 O(log n)但遇到极端情况递归深度可能到 O(n)在数据量很大的时候会栈溢出。工程实现里有个办法是“尾递归优化”只对较短的子数组递归较长的子数组用循环处理。第三个是重复元素问题。假设数组全是相同的值Lomuto 分区会反复让 i 指针走到底性能也退化成 O(n²)。针对这种情况可以用三路切分three-way partition把数组分成小于、等于、大于枢轴的三段等于的部分不需要再排序。Dijkstra 提出的三分法实现起来也不难def quick_sort_three_way(arr, low, high): if low high: return lt low gt high pivot arr[low] i low while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 quick_sort_three_way(arr, low, lt - 1) quick_sort_three_way(arr, gt 1, high) return arr这个三路切分版本在大量重复数据的场景下非常稳几乎不会退化成 O(n²)。我拿一百万全部相同元素的数据测过普通快速排序跑了十几秒还没结束三路切分版不到一秒就跑完了。4.3 工程实现里的混合策略真正的工程级快排很少只靠快排自己一路走到黑。常见优化是数据规模小到一定阈值比如 16 或 32时切换成插入排序。这个策略我在前面讲插入排序时也提过是经过了大量测试才验证有效的递归和划分的压栈开销在小数组上不如插入排序直接来得快。另一个优化是迭代替代递归手动维护栈来处理子区间。这个做法能避免递归爆栈也方便控制排序的区间粒度。我在实现一个百万级数据排序模块时确实遇到过递归栈溢出改成显式栈以后稳定了很多。def quick_sort_iterative(arr): stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue p partition(arr, low, high) if p - 1 - low high - p - 1: stack.append((p 1, high)) stack.append((low, p - 1)) else: stack.append((low, p - 1)) stack.append((p 1, high)) return arr这种“把较短的区间先入栈”的做法能保证栈的最大深度被控制在对数级别是解决递归爆栈的经典思路。5. 五种场景下的性能实测与避坑清单5.1 不同数据分布下的测试对比我不喜欢空谈理论所以专门写了一个小的基准脚本在同一台机器上分别测了随机数据、几乎有序数据、大量重复数据、完全逆序数据和接近完全有序数据五种情况下的表现。数据量统一用 20 万元素单位是毫秒。数据场景插入排序归并排序快速排序三数取中随机数据12000约 90约 60几乎有序约 50约 80约 110大量重复约 3000约 70约 40三路切分完全逆序14000约 85约 65完全有序约 5约 45约 70插排的表现非常有意思在完全有序的数据上快得离谱但在随机和逆序数据上直接崩溃。归并排序全能每种场景都不慢。快排加上三路切分和三数取中后在重复数据上也没问题了。这个表格我每次讲排序都愿意拿出来因为它能直观说明“为什么不能靠一个算法打天下”。5.2 常见问题与调试技巧速查我把自己和同事在写排序时踩过的坑整理成了一张速查表基本都是肉眼排查很难发现的问题。症状可能原因解决办法数组后半部分出现旧值残留merge 时左右区间边界写错检查 mid 的计算以及 i、j、k 指针的边界数据量增大后栈溢出递归过深枢轴选择不好使用随机枢轴/三数取中或改迭代实现全部相同元素时排序极慢未处理重复元素使用三路切分Python 中 arr[-1] 被访问不报错但结果错乱边界条件j 0缺失保持边界条件前置判断稳定性隐患比较条件用了改成严格大于或小于小规模数组排序反而慢递归和划分的开销超过了收益设置阈值小数组切换插入排序调试排序算法有个很好用的技巧先在小规模数据上做死循环测试。我通常写一个验证函数随机生成几万组小数组和 Python 内置的sorted结果做比对一旦发现差异立刻能定位是哪个边界出了问题。random模块生成随机数组 assert sorted_result expected这套组合比手动测试高效十倍。5.3 结合实际场景的选型心得聊到选型我个人的经验是分场景看。数据量小几十到几百个或者数据基本有序直接插入排序代码最简单性能也最好。面试时处理这种问题没必要强行用快排。数据量中等内存不紧张又要求排序稳定归并排序是不二选择。它不会像快排那样有性能抖动而且稳定性的价值在业务排序中很被重视。数据量很大内存紧张也没有稳定性要求快速排序配合合理的枢轴策略和混合插入排序是综合收益最高的方案。绝大多数编程语言内置的排序实现比如 C 的std::sort走的也正是这条路线。还有一个很容易被忽略的点如果你的排序对象不是基本类型而是对象或者结构体比较函数的开销会成为主要瓶颈。这种情况下归并排序虽然比较次数稳定但快速排序的比较次数往往更少。最稳妥的做法是拿真实数据做一次基准测试而不是凭直觉选择。5.4 我最后想补充的几个实践细节代码可读性这个问题排序算法里常常被忽视。面试时写版本可以短小精悍但工程里维护排序列代码变量名要直观。low、high、mid、pivot、temp这类的清晰命名能减少很多沟通成本。写测试用例时我建议把“空数组、单元素数组、两个元素数组、全相同数组、逆序数组、随机数组”这六种情况固定下来。这六种情况基本覆盖了排序边界条件的所有常见问题。我见过太多人在正常数据上没问题一到空数组和单元素数组上就崩溃了。性能测试时也要注意环境因素。Python 里递归和函数调用相对较慢跑大规模数据时建议用 PyPy 或者改成.py脚本直接跑在解释器交互环境里测出来的时间会有很大偏差。用真实的多组数据、多次取平均才是有说服力的对比结果。最后聊聊个人最直观的体会。排序算法看起来是“背代码”的题目但真的去分析它们各自适应的场景和底层的细节约束会对算法设计思想的理解产生质变。理解了为什么快速排序需要随机化、为什么归并排序需要额外空间、为什么插入排序在小规模数据上是王你再看其它复杂算法思路会开阔很多。我自己每次重新整理排序都会有新的发现所以也建议你把这三种算法当成一个“基准题”每隔一段时间回来重写一次感受自己对代码和性能理解的成长。