排序算法这种东西很多人觉得已经烂大街了——工程里直接用内置的sorted()就完事面试前背两个模板也能应付。可真到要用的时候你会发现三种算法各自有脾气插入排序看起来最慢却在近乎有序的数组上一骑绝尘归并排序既不快也不省内存却凭一个稳定性成为数据库和外部排序的基石快速排序平均最快但一个有序输入就能让它直接退化到平方级。这篇文章就是要把这三种算法彻底拆开从思想、实现到复杂度推导再到实际跑数据的量级感受最后聊聊工程实现里最容易踩的坑。适合正在学算法、准备面试、或者写代码时想明白内置排序到底在帮我做什么的人。我把实现语言统一用 Python因为它最方便验证想法而且能顺带让你看清递归深度、切片开销这些教科书不讲的细节。1. 自己实现排序到底在学什么1.1 这不是造轮子是理解复杂度的起点很多人觉得排序都有现成的自己写没意义。但如果你真的亲手实现过这几种排序你会发现大 O 记号突然变得具体了O(n^2) 不是一句抽象的话而是插入排序在 10 万元素时让人等到怀疑人生的真实体验O(nlogn) 也不是背出来的结论而是归并排序先切分再合并后呈现出的稳定节律。不亲手写一遍你对时间复杂度的理解始终隔着一层。更实际的价值在于面试和手写算法场景。快速排序的 partition 是双指针思想的典型载体归并排序是递归分治的最佳练习插入排序则是增量维护有序区的经典模型。这三个模型在后面刷二分、链表、树形问题时都会反复出现。1.2 三种算法分别代表了三种设计范式插入排序是增量式Incremental思路一次处理一个元素把它放入已经有序的序列中。归并排序是分治Divide and Conquer中的先分后合派重点在合并两个有序子序列合成一个有序序列。快速排序也是分治但重点在切分一次 partition 就把元素按基准值分成两拨递归只负责处理分出来的部分。理解了这三种模型你后面看 TimSort、三路快排、外部排序都会觉得是在这些基础上加补丁。2. 三种排序的核心思路与性格差异2.1 插入排序像整理手中的扑克牌想象你抓了一手牌从左到右一张张看每张新牌都往前找位置插到合适的地方。开始时左手只有第一张牌它天然就是有序的第二张来了和第一张比一下决定放它左边还是右边第三张来了又和前两张逐个比较找到位置。代码里对应的就是我反复强调的两个循环外层for i in range(1, len(arr))负责新牌内层while j 0 and arr[j] key负责往前挪位置。内层移动时用的是赋值而不是交换因为每张牌只需要向后挪一格最后空出来的位置给新牌这样赋值次数比冒泡排少不少。2.2 归并排序像两队士兵合并成整齐队伍归并排序的思路很朴素把数组从中间劈开左半边排好右半边排好然后把两个有序序列合并成一个有序序列。合并过程就像左右两队士兵排队会师每次都让两队队首比较个子矮的先出列直到某一队为空剩下的一队整体跟上。所以归并排序真正花时间的不是分而是合。这个合过程有一个非常重要的细节当左右两边的元素相等时我们优先取左边那个这正是归并排序稳定性的来源。2.3 快速排序按基准值把队伍分流快速排序也玩分治但它不急着合——它先选一个基准值pivot然后一趟扫描把数组原地分成两拨小于基准值的靠左大于基准值的靠右。基准值自己就落在了最终位置上。之后左右两拨各自再做同样的事。所以快排的精华全在 partition 这一步而且它是原地的不需要额外的大数组这点和归并排序完全不同——也正因如此快排的平均常数因子特别小。2.4 三种算法的一页纸对比算法设计范式原地性稳定性最好平均最坏辅助空间插入排序增量式原地稳定O(n)O(n^2)O(n^2)O(1)归并排序分治-合并非原地稳定O(nlogn)O(nlogn)O(nlogn)O(n)快速排序分治-切分原地不稳定O(nlogn)O(nlogn)O(n^2)O(logn)~O(n)这张表背下来很容易但背后的为什么才是重点。接下来三个章节逐个拆开讲。3. 插入排序被低估的 O(n^2)3.1 基础实现与两层循环的真正职责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 arrkey arr[i]是一个很重要的临时变量它保存了当前要插入的元素。内层循环的边界条件是j 0和arr[j] key同时满足j从头往前扫描有序区每遇到一个比key大的元素就把它往后挪一位直到遇到一个不大于key的元素或者越过数组头这时j 1就是key的最终位置。这个实现有两个容易写错的地方一是外层必须从 1 开始因为第 0 个元素天然有序不需要插入自己二是key要提前存好否则后面挪位会把arr[i]覆盖掉你就会发现一顿操作之后数字丢了。3.2 最好、最坏与平均用逆序对说清楚插入排序的性能非常依赖输入的初始顺序。最好情况数组已经有序。每个key和它前一个元素比一下发现不用挪直接结束内层循环外层一共只做了n-1次比较。复杂度 O(n)。最坏情况数组逆序。每个key都得一路比到数组开头所有元素都往后挪。总比较次数是1 2 ... (n-1) n(n-1)/2总移动次数同样接近这个量级复杂度 O(n^2)。平均情况乱序输入时期望上大约有一半的元素需要移动所以比较和移动次数约为最坏的一半仍然是 O(n^2) 的量级。这里有一条很妙的关联插入排序的移动次数恰好等于这个数组的逆序对数量。逆序对就是前面的数比后面的大的配对个数。逆序越多插入排序越慢。这也解释了为什么近乎有序的数组对插入排序如此友好——逆序对很少几乎不用移动。3.3 优化技巧提前终止、哨兵与二分插入插入排序的第一个优化叫做提前终止如果key比有序区最后一个元素还打直接放回原位内层循环连一次赋值都不做。这在实际的近似有序数据上收益非常明显。第二个经典技巧是哨兵。在数组最前面放一个极小的值比如float(-inf)内层循环就可以去掉j 0的判断。当然实际工程里你不会真往数组里塞哨兵但作为思维训练它很直观地告诉你减少边界判断就是减少常数时间。这个思想在链表、循环缓冲区等场景里都会用到。还有一道常考的变体是二分插入排序因为前面是有序区可以用二分查找找到key的插入位置把比较次数降到 O(logn) 每趟。但移动次数仍然是 O(n) 每次所以整体复杂度还是 O(n^2)。它只优化了比较没优化移动因此工程价值有限面试中却常被用来考察你是否理解两个操作各自的开销。3.4 稳定性的证据与什么时候该用插排插入排序是稳定的。稳定性指值相等的元素排序后相对顺序不变。原因看代码就很清楚——内层条件用的是arr[j] key意味着值相等时不移动直接放到相等元素的后面。假设输入是[5a, 5b, 1]排序后 5a 和 5b 仍然先 5a 后 5b。那什么时候用它一句话数组规模很小比如小于 50或者输入已经接近有序。这时候插入排序不仅不是灾难反而可能是最快的。这个结论不是空谈——Python 内置排序 TimSort 就对小片段启用插入排序正是利用了它的这个特性这一点后面会讲。4. 归并排序稳定背后的空间账4.1 分到不能再分合要合得干净归并排序的核心思路可以用一句话概括把数组从中间砍成两半每一半自己先排好序再把两个有序序列合成一个。这个先砍再合的结构就是一棵递归树。递归的终止条件是len(arr) 1——一个元素不需要排序。然后mid len(arr) // 2切成左右两半分别递归最后 merge。因为每一层都老老实实地把数组劈成两半所以递归深度恰好是logn量级。而合并这一步每一层加起来的代价是 O(n)总代价就是 O(nlogn)。这个复杂度是刚性的——不管输入是顺序、逆序还是随机归并排序永远稳定在 O(nlogn)这一点是它最大的定心丸。4.2 递归实现与 merge 函数的三个分支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): res [] i j 0 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 while i len(left): res.append(left[i]) i 1 while j len(right): res.append(right[j]) j 1 return resmerge 的循环逻辑其实只有三条路左右都还有元素比较各自队首谁小谁出列左边还有剩余整体接上右边还有剩余整体接上。重点在第一条路的判断条件left[i] right[j]用的是小于等于而不是小于。当左右相等时优先取左边的元素这样左边序列里相等的元素永远保持在右边序列之前这就是归并排序稳定性的全部秘密。这个版本在 Python 里还有一个务实的改进res.extend(left[i:])直接拼剩余部分代码更短。但注意left[i:]其实会创建一个新切片列表数据量大时有额外内存和时间开销。追求性能时可以用循环逐元素 append 代替切片这个细节在 LeetCode 的归并题里无所谓但在处理超大数组时差异明显。4.3 自底向上迭代版少一半递归压力递归版写起来直观但递归栈深度是 O(logn)而且切片arr[:mid]、arr[mid:]每层都会复制数组带来额外分配。用自底向上的迭代版可以规避这些问题def merge_sort_iter(arr): n len(arr) src arr[:] dst [0] * n size 1 while size n: for start in range(0, n, 2 * size): mid min(start size, n) end min(start 2 * size, n) i, j, k start, mid, start while i mid and j end: if src[i] src[j]: dst[k] src[i] i 1 else: dst[k] src[j] j 1 k 1 while i mid: dst[k] src[i] i 1 k 1 while j end: dst[k] src[j] j 1 k 1 src, dst dst, src size * 2 return src这个版本的核心是size从 1 开始每次翻倍。size1时把相邻两个元素合并成有序长度为 2 的片段size2时把相邻两个长度 2 的片段合并成长度 4以此类推。它完全模拟了递归版本的合并过程但不依赖递归。有个容易忽略的点src和dst每次循环完要互换。因为下一轮要从刚合并完的数组里再取相邻片段继续两两合并。最后一轮合并完如果交换后返回的是src还是dst要小心——我的实现里最后返回的是src因为它保留了最后一次合并的结果但如果你在循环里调整了交换时机记得实测验证一下返回哪个变量。4.4 归并的经典应用外部排序与链表排序归并排序的价值绝不只是教科书上的稳定排序。外部排序是个典型的实战场景当数据量大到内存装不下时你把数据切成多个块每块在内存里排好序写回磁盘然后再做多路归并把一个个有序块合并成全局有序的大文件。这个过程用的核心操作就是 merge——它是唯一能把多个局部有序序列合并成全局有序序列的通用操作。另一个应用是链表排序。数组排序可以随机访问元素快排的 partition 本质依赖随机访问链表不行你不能轻易交换相隔很远的节点。但归并排序只需要顺序访问天然适配链表。所以你在实际工程中要对链表做稳定的 O(nlogn) 排序归并几乎是唯一选择。5. 快速排序教科书只讲了一半5.1 partition 到底在干嘛快排最核心的操作是 partition它的目标只有一个选一个 pivot一趟扫描后让所有小于等于它或严格小于它的元素聚到左边所有大于它的元素聚到右边然后返回 pivot 最终所在的下标。最经典的实现是 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)这里i的语义很关键i始终指向最后一个小于 pivot 的元素的位置。每当j扫描到一个小于 pivot 的值就把i往前推进一位并把它交换过去。扫描结束后i右边的第一个空位i1就是 pivot 的最终位置。Lomuto 分区实现短好理解但有个代价交换次数很多而且 pivot 选最右端时对逆序或有序输入的退化问题非常严重。5.2 Lomuto 和 Hoare 两种分区方式计算机科学家 Hoare 当年提出的原始版本比 Lomuto 更高效用的是双指针从两端往中间夹def partition_hoare(arr, low, high): pivot arr[(low high) // 2] i low - 1 j high 1 while True: i 1 while arr[i] pivot: i 1 j - 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i] def quick_sort_hoare(arr, low, high): if low high: p partition_hoare(arr, low, high) quick_sort_hoare(arr, low, p) quick_sort_hoare(arr, p 1, high)Hoare 的思想是左指针i找比 pivot 大的右指针j找比 pivot 小的找到就交换直到两指针相遇。它每次交换能同时把两个元素放到正确的一侧所以平均交换次数比 Lomuto 少很多。但需要注意Hoare 分区返回的p并不是 pivot 的最终位置——它只是左右分界的某个点。所以递归调用时区间是[low, p]和[p1, high]而不是 Lomuto 的[low, p-1]和[p1, high]。这个差异非常容易导致写错递归边界然后陷入无限递归这是快排实现里最经典的坑之一。5.3 退化危机有序数组为什么把快排打成 O(n^2)假设我们始终选arr[high]当 pivot。输入是恰好有序的数组会发生什么每一轮 partitionpivot 都是当前区间里最大的元素Lomuto 扫描结束后i停在low - 1pivot交换到low位置右侧区间长度为n-1。于是每次递归只排除掉一个元素递归深度变成n每一层都要完整扫描剩余数据总代价是n (n-1) ... 1 O(n^2)。这个退化恰好和插入排序形成绝妙的反差插入排序在近乎有序的数组上表现超神接近 O(n)快速排序在近乎有序的数组上如果 pivot 选不好直接掉到 O(n^2)比归并慢几个数量级。所以快排平均最快这个结论有个隐含前提你必须想办法避免最坏情况。这也是为什么面试官总爱追问快排优化。5.4 随机化 pivot 与三数取中优化的思路很简单既然输入是有序的坑了我那我就不让你猜到 pivot 的位置。随机选一个下标import random def partition_random(arr, low, high): rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] return partition(arr, low, high)随机化之后输入是顺序的、逆序的、还是随机的都不影响 pivot 的期望位置。从概率上最坏情况发生的概率被压到极低这就是随机化快排能保持期望 O(nlogn) 的原因。工程上更常用的是三数取中取low、mid、high三个位置的值选其中位数作为 pivot。它不但抗有序输入还能避免随机数生成的开销在真实数据上往往比纯随机更稳定。STL 的std::sort在数据量较小时就常用这类策略。5.5 快排为什么不稳定快排的不稳定性经常被问很多人背结论但不理解。稳定性要求相等的元素排序后相对顺序不变而快排的交换是跨越大量中间元素的远程交换这会打乱相等元素的相对位置。举个例子数组为[5a, 5b, 1]选第三个元素 1 作 pivot。Lomuto 扫描j0时 5a 1跳过j1时 5b 1跳过结束后把arr[i1] arr[0]和 pivot 交换数组变成[1, 5b, 5a]——5a 跑到 5b 后面去了。这种远程交换一旦发生相等元素的相对顺序就无法保证所以任何基于这种 partition 的快排都不稳定。顺带说一句想让快排稳定也不是完全不可能你可以用值原始下标联合作为比较键或者额外用一块临时数组做稳定分区但那样就牺牲了快排原地的最大优势得不偿失。6. 同台实测常数因子才能决定真实差距6.1 测试方法与数据准备理论归理论真实体感还得跑数据。我这里用timeit分别测插入排序、归并排序和随机化快排在三种数据分布下的表现随机乱序、近乎有序、完全逆序。规模从 1000 到 100000。import random import timeit def bench(sort_func, data): arr data[:] t timeit.timeit(lambda: sort_func(arr), number1) return t注意几个测试细节每个 sort 前都要拷贝一份数据否则第一次排完序后面测的就是有序输入结果会完全失真用timeit取一次运行时间就够观察量级较慢的插排在 10 万元素时要几十秒没必要重复近有序数据可以用random.shuffle后只扰动少量位置来模拟。6.2 结果解读的思路直接给结论性的量级参考数值随机器浮动但相对关系稳定数据插入排序归并排序快排随机pivot1000 随机约 0.01s约 0.0005s约 0.0003s10000 随机约 0.5s约 0.007s约 0.004s100000 随机约 60s约 0.09s约 0.05s100000 近有序约 0.001s约 0.09s约 0.05s100000 逆序约 60s约 0.09s约 0.05s几个关键信息第一插排在 10 万元素随机输入下已经不可用了——O(n^2) 的增长是真的恐怖。但它在近有序时 0.001s 就把所有对手按在地上摩擦差距达到百倍量级。这个反差是理解排序算法最重要的直觉。第二快排和归并虽然都是 O(nlogn)但快排就是快那么一点。原因是快排完全原地操作cache 命中率高只做交换不做大数组分配而归并每层都要创建临时数组内存分配和拷贝的代价实打实存在。第三近有序时固定 pivot 的快排如果不用随机化会退化成接近插排的灾难。这个我特意没放进表里——你可以在自己机器上试试把 10 万元素排好序再跑一次quick_sort(arr, 0, n - 1)你会看到它慢得超乎想象。6.3 为什么工程库最终选择了混血既然快排平均最快为什么 Python 的sorted()不用快排答案是Python 内置排序用的是 TimSort本质是归并排序 插入排序的混合体——它把数组切成小块小块内部用插入排序因为小块接近有序插入排序玄学快块之间用归并排序合并同时利用数据中已有的有序片段run来减少合并次数。Java 的Collections.sort对对象类型也默认用归并系算法因为对象排序需要稳定性而基础类型如int[]则用双轴快排DualPivotQuickSort因为基础类型不需要稳定快排更省内存。这说明一个重要的工程观点没有银弹选型永远看场景——是否要稳定、内存是否紧张、输入是否可能接近有序每一条都会改变最优选择。7. 工程实现中的四个高频坑7.1 Python 递归深度10 万元素直接把快排栈打爆写快排或归并递归版最常见的翻车现场是RecursionError。Python 默认递归深度限制约 1000而快排在带有随机化 pivot 时递归深度约logn——10 万元素大约是 17 层没问题——但如果 pivot 选得不好或你没用随机化递归深度可能达到 n立刻爆栈。解决方案有三条路一是sys.setrecursionlimit(1_000_000)把上限调大二是对输入先random.shuffle再排序降低退化风险三是直接换成迭代版。我建议你至少了解递归深度这个坑因为在 LeetCode 上写快排时测试用例经常故意造极端数据。7.2 Lomuto 分区的边界条件pivot 与 i1 的错位第一次写 Lomuto 时最容易写错两个地方内层用了arr[j] pivot而不是 pivot。用会把相等元素也交换到左边造成大量无谓交换而且会破坏 partition 后左侧严格小于、右侧大于等于的语义递归边界容易混乱。分完区忘了 pivot 已经就位。partition 最后必须做一次arr[i1], arr[high] arr[high], arr[i1]否则 pivot 还在high位置没归位递归时它会被重复处理。写完之后用一个小数组手动模拟一遍比如[3, 1, 4, 2]看看 partition 返回的下标和数组状态是否符合预期。7.3 Hoare 分区的边界返回 j 对应的递归区间如果你用 Hoare 分区一定要记住它和 Lomuto 的递归写法不同quick_sort_hoare(arr, low, p) # 而不是 low, p - 1 quick_sort_hoare(arr, p 1, high)为什么因为 Hoare 返回的p只是左右边界相遇点它可能在 pivot 的左边或右边pivot 本身并没有被放到最终位置。如果照抄 Lomuto 的[low, p-1]可能丢掉元素如果你不仔细调最典型的结果是无限递归——某次p等于low再套[low, p-1]就变成[low, low-1]这种空区间虽然空区间还好但[low, p]若用 Lomuto 边界反而会把已经排好的元素又递归进去。我的建议是面试和做题首选 Lomuto理解简单、不易错Hoare 留到你真的需要压常数时再用而且必须写单元测试覆盖边界情况。7.4 重复元素也会让快排退化三路分区最后一个容易被忽略的坑是大量重复元素。假设数组全是同一个值[1, 1, 1, ..., 1]Lomuto 分区用 pivot判断内层一次交换都不发生i始终停在low-1最后 pivot 被放到最左边右侧剩下n-1个全等元素。每次递归只排掉一个元素——这又是一个 O(n^2)。解决这个问题的标准方案是三路分区也叫荷兰国旗问题分区把数组分成三块小于 pivot、等于 pivot、大于 pivotdef quick_sort_3way(arr, low, high): if low high: return pivot arr[low] lt, i, gt low, low 1, high 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_3way(arr, low, lt - 1) quick_sort_3way(arr, gt 1, high)三路分区里lt维护小于区的右边界gt维护大于区的左边界i扫描中间未处理区。遇到小于 pivot 的元素把它扔到左边并前进遇到大于 pivot 的把它扔到右边但不前进因为换回来的元素还没检查等于 pivot 的直接跳过。最终[lt, gt]区间全是等于 pivot 的元素它们不需要再递归。这个版本不仅处理了重复元素还顺便把递归范围缩小了在很多实际场景下比普通快排更快。我在实际写代码时对涉及排序的场景都会先问自己三个问题数据量有多大是否可能接近有序排序结果需不需要保持相对顺序把这三个问题想清楚你自然知道该上手哪种算法——而不是每次无脑调用sorted()。最后分享一个我的习惯每次写完排序代码先拿空数组、单元素数组、两个相同元素的数组和全相同元素的数组做一轮边界测试这些用例能暴露绝大多数递归边界和分区逻辑的问题。
