很多人学排序算法是从冒泡、选择、插入这几个O(n²)的“入门三件套”开始的等到了归并排序和堆排序才算真正接触到主流工业界会用的排序方法。这两个算法放在“递归与分治策略”这个题目下其实非常有讲究归并排序是分治策略最标准的模板把问题一拆为二、分别解决、再合并结果而堆排序表面上看和分治没有直接关系但它的核心操作——堆化heapify——本质上就是一个递归定义的调整过程。如果你能把递归和分治的思维真正理清楚这两个算法可以同时拿下而且你会发现看其他递归算法二叉树遍历、DFS回溯、线段树都会通顺很多。这篇博文会把两件事讲透一是递归与分治到底是怎么协同工作的二是归并排序和堆排序每一步为什么那样写、有哪些常见坑、实战中怎么选。适合正在学算法的初学者也适合准备面试、想把手写排序写出工程感的开发者。我会按自己实际调试和面试遇到的场景来写代码以 Python 为主思路同样适用于 Java、C 和 Go关键部分我会标注清楚。1. 递归与分治先想清楚问题再写代码1.1 递归的三要素我一直和身边的同学说递归不是一种“语法技巧”而是一种描述自相似问题的方式。一个递归函数本质上是在回答一个问题如果我拿到了一个规模更小的子问题的答案我怎么用它拼出当前问题的答案拿最基础的例子说求一个数组的最大值。你当然可以写个for循环扫一遍但递归的写法是这样的def find_max(arr, l, r): # 基线条件区间里只剩一个元素 if l r: return arr[l] mid (l r) // 2 left_max find_max(arr, l, mid) right_max find_max(arr, mid 1, r) # 合并当前问题的答案由两个子问题答案拼出来 return max(left_max, right_max)递归有三个关键要素基线条件、递归调用、合并结果。基线条件决定了递归什么时候停下来必须是“不需要再分解就能直接得到答案”的情况递归调用负责把问题规模缩小合并结果则是把子问题的答案组装成当前问题的答案。这三者缺一不可。很多人写递归翻车要么是基线条件写错导致无限递归要么是合并逻辑写错导致答案偏差而这两个问题在归并排序里都会再次出现。递归在执行的时候系统会为每次调用压入一个栈帧保存局部变量和返回地址。递归深度越大栈空间占用越高。所以看到一个递归函数第一反应应该是它的递归深度是多少会不会在极端输入下爆栈这个问题在归并排序和堆排序里其实都不严重因为两种算法的递归深度都是O(log n)级别但如果你是写递归去处理链表、树这类深度可能很大的结构就要格外小心了。1.2 分治不是递归的专属分治Divide and Conquer是一种问题分解策略把原问题拆成若干个规模更小、结构相似的子问题分别求解后再合并。归并排序是典型的分治一分为二各自排序再合并有序数组。快速排序也是分治甚至二分查找也可以理解为分治的特例。但分治并不强制要求用递归实现。理论上任何递归都可以改写成迭代用显式栈模拟而分治策略也完全可以用循环配合队列去做只是代码会复杂很多不划算。反过来递归也不一定都是分治比如树的DFS遍历它是“沿着一条路径走到底再回来”并没有把问题拆分成独立子问题再合并的过程更多是递推关系。所以看归并排序和堆排序时要把两件事分开分治是一种宏观策略递归是一种代码结构。归并排序同时用到了两者堆排序虽然不按“分解-合并”的思路走但他的堆化操作如果写成递归版本一样有清晰的基线条件和递归调用关系。理解了这层关系你就不会在面试时说出“堆排序是分治算法”这种容易被追问到尴尬的话了。1.3 复杂度视角递归式与递归树谈到递归和分治绕不开的是复杂度分析。归并排序的时间复杂度可以用递归式表示T(n) 2T(n/2) O(n)翻译成人话就是排序n个元素的开销等于排序两个n/2元素的开销所以是2T(n/2)再加上合并两个有序数组的开销O(n)。把这个递归式展开成一个递归树每一层总工作量是O(n)总共分解log₂n层所以总复杂度是O(n log n)。这个推导比死记“归并排序是O(n log n)”要有用得多因为同样的方法可以分析快速排序、二叉树相关算法等。其实对于常见的分治算法可以用一个简化版的主定理快速判断如果 T(n) aT(n/b) O(nᵈ)那么当 log_b a d 时T(n) O(nᵈ)当 log_b a d 时T(n) O(nᵈ log n)当 log_b a d 时T(n) O(n^(log_b a))归并排序这里a2、b2、d1所以log₂21d结果就是O(n log n)。面试时你如果能顺手说出这个推导逻辑面试官对你的印象会好很多因为这证明你不是背答案而是真的理解复杂度是怎么来的。2. 归并排序分治框架的标准模板2.1 从“把两个有序数组合并”开始归并排序的核心子操作是把两个已经有序的数组合并成一个有序数组。这个合并操作本身就值得单独练熟它也是很多其他算法比如合并两个链表、求逆序对的基础。合并的思想非常简单用两个指针分别指向两个数组的开头每次都把较小的元素放入结果数组然后移动对应指针当一个数组被取完了直接把另一个数组的剩余部分复制过去。def merge(arr, l, mid, r): # 先复制出两个临时片段 left_part arr[l:mid1] right_part arr[mid1:r1] i j 0 k l while i len(left_part) and j len(right_part): if left_part[i] right_part[j]: arr[k] left_part[i] i 1 else: arr[k] right_part[j] j 1 k 1 # 把剩余部分接上 while i len(left_part): arr[k] left_part[i] i 1 k 1 while j len(right_part): arr[k] right_part[j] j 1 k 1这里有一个非常容易被忽略的关键点为什么代码里用的是而不是因为归并排序的稳定性就体现在这里。当左半部分的元素和右半部分的元素相等时我们优先取左半部分这样相同值的相对顺序在排序后不会被破坏。“稳定排序”这个词在日常开发中经常被提到比如你先按时间排序再按用户ID排序如果第二次排序是稳定的那么同一个用户ID下的多条记录会保持第一次排序的时间顺序。归并排序是稳定排序这是它工程价值的重要来源之一。另外要注意上面的实现为了简单每次都临时切片复制left_part和right_part这在教学上没问题但实际写高性能版本时更常见的做法是复用同一个临时数组避免频繁分配内存。我后面讲优化时会专门说。2.2 递归实现的区间不变量有了merge函数后归并排序的递归骨架就非常简单了def merge_sort(arr, l, r): # 基线条件区间为空或只剩一个元素 if l r: return mid (l r) // 2 # 分解递归排序左半和右半 merge_sort(arr, l, mid) merge_sort(arr, mid 1, r) # 合并两个有序子数组变成整体有序 merge(arr, l, mid, r)写这一段的时候我建议所有初学者锚定一个“区间不变量”你使用的区间是闭区间[l, r]还是左闭右开[l, r)必须从第一个函数到最后一个函数完全统一。我在上面的代码里统一用了闭区间所以递归边界是l r表示空区间或单元素区间mid的划分是[l, mid]和[mid1, r]。如果中途混用了左闭右开merge里的下标计算就会乱套轻则漏掉元素重则数组越界。判断递归是否正确只需要看三点基线条件下能不能直接返回递归调用是否让区间严格缩小合并后是否覆盖了当前区间所有位置。这三点都满足递归就是正确的。这也是我教别人调试递归算法的固定套路不看细节先核对这三个问题。2.3 复杂度、稳定性与空间优化归并排序的时间复杂度在最好、最坏、平均情况下都是O(n log n)。这一点比快速排序“平均O(n log n)、最坏O(n²)”显然更稳所以很多对性能稳定性要求高的场合会选择归并排序或基于归并的变体。空间复杂度是它最大的短板。合并过程需要一个长度最多为n的临时数组所以空间复杂度是O(n)再加上递归调用栈的O(log n)总体是O(n)量级。这意味你排序1亿个int如果每个int占4字节光临时数组就需要约400MB内存这在内存受限的场景下是不小的开销。但空间是可以优化的。最常用的两个手段第一全局复用同一个临时数组不要在递归的每一层都new一个新数组否则会有大量内存分配开销第二当区间长度小于某个阈值比如16或32时改用插入排序。这是很多工业级排序的重要优化点因为递归分解到很小规模后函数调用和合并操作的常数开销反而比插入排序大。Python里虽然没有内置这层优化但Java的Arrays.sort对基本类型的实现思路里也有类似的混合排序设计。此外还有一个很实用的优化如果左半部分的最大值已经小于等于右半部分的最小值说明两个子数组拼起来恰好天然有序可以直接跳过merge。在数据已经基本有序的场景下这个优化能把归并排序的实际运行时间明显拉低。工程实现里这种小细节很多都是同一个目的降低常数因子。2.4 三个工程优化细节结合我自己写代码的经验归并排序的三个工程优化细节值得单独拿出来说。第一个是复用临时数组。用Python写的时候可以这样先创建tmp [0] * n然后让递归函数接收tmp作为参数。merge时从tmp的指定位置写数据而不是每次切片。这样内存分配次数从O(log n)次降到1次对性能提升是显著的。第二个是小数组转插入排序。在递归入口处判断如果r - l 32就直接用插入排序处理当前区间。这样既减少了递归深度又利用了小数组插入排序的高效率。需要注意这个阈值不是越大越好一般16到64之间是比较合理的范围具体可以实测调优。第三个是上面提到的“天然有序早退”。在merge之前先检查arr[mid] arr[mid1]如果成立说明左半部分所有元素都不大于右半部分所有元素整体已经有序直接return就好。这个检查是O(1)的但可能省下O(n)的合并开销在近乎有序的数据上效果极好。我在实际项目里用归并排序最多的地方是链表排序。因为链表不支持随机访问快排和堆排序在链表上的实现都很别扭而归并排序只需要能顺序遍历和拼接节点天然适配链表。对链表做归并排序时空间复杂度甚至可以做到O(1)严格说是O(log n)递归栈因为不需要额外数组只需要调整指针。这也是很多面试官喜欢拿链表归并排序来考察候选人对递归和指针操作掌握程度的原因。3. 堆排序理解递归堆化的钥匙3.1 堆的结构与数组表示堆排序为什么不叫“分治排序”因为它没有“把问题拆分成独立子问题再合并”的过程。那为什么放在这篇文章里因为堆排序的核心操作——heapify堆化——是一个递归定义的调整过程。理解了这个递归你才算真正理解堆。先明确二叉堆的结构堆是一棵完全二叉树并且满足堆性质。大顶堆里每个父节点都要大于等于它的子节点小顶堆则相反。完全二叉树意味着除了最后一层可能不满之外其他层都是满的最后一层从左到右紧密排列。这个结构用数组来存储非常自然某个节点的下标为i那么它的左孩子下标是2i1右孩子下标是2i2父节点下标是( i - 1 ) // 2。用数组存堆不需要任何指针就能在节点之间自由移动这是堆作为优先级队列底层结构的重要原因。堆化的递归逻辑是这样的假设当前节点i的左右子树都已经是合法的堆但节点i本身可能不满足堆性质。那么我们把节点i和较大对大顶堆来说的那个子节点交换然后递归地对被交换下去的那个子树重新做堆化。递归的基线条件是节点i没有子节点或者节点i已经满足堆性质。这里同样包含“基线条件、递归调用、合并”的递归三要素只是它的“合并”只是重新建立局部有序关系并不像归并那样显式地拼接结果。可以先看递归版本的sift_downdef sift_down(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] # 递归继续处理被交换下去的位置 sift_down(arr, n, largest)这段代码我在面试中看过无数人写错最常见的错误是找到最大值后交换了但没有继续递归处理子树。只要少这一句当前子树可能就不是合法的堆了。记住一个原则交换之后可能破坏的是交换过去的那个子树必须继续向下修正。3.2 自底向上建堆为什么是 O(n)很多人以为建堆的时间复杂度是O(n log n)对n个元素每个都做一次O(log n)的堆化但实际上是O(n)。这一点经常被面试官拿来追问值得从原理上搞明白。建堆的过程是从最后一个非叶子节点开始往前逐个调用sift_down。最后一个非叶子节点的下标是n//2 - 1。为什么从它开始因为所有下标大于n//2 - 1的节点都是叶子节点叶子节点本身就是合法的堆不需要处理。证明建堆是O(n)关键看每个节点需要下沉的高度。一个高度为h的节点sift_down最多下沉h次。而高度为h的节点数量大约是n / 2^(h1)个。所以总操作次数大约为Σ h * n / 2^(h1)对h从0到log₂n求和。这个求和的结果收敛到O(n)因为越高的层节点数量越少而每增加一层节点数量减半抵消了下沉次数的增长。所以建堆是线性的。如果你用递归树的角度理解会更直观接近底层的节点数量多但下沉距离短接近顶层的节点数量少但下沉距离长整体权重加起来是常数级的。简单建堆代码def build_heap(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i)这里的方向不要搞反了。必须从后往前处理以“下面的子树已经是堆”为前提来修正当前节点。如果从前往后处理你根本无法保证需要堆化的子树满足前提条件。3.3 排序阶段堆顶与末尾的交换建堆完成之后堆顶是整个数组最大的元素。堆排序的排序阶段就一个思路把堆顶和当前堆的最后一个元素交换然后把堆的规模缩小1再对新堆顶做sift_down。每轮结束后最大的元素就被放到了数组末尾的最终位置上。重复这个过程数组后面就会逐渐累积出有序序列。def heap_sort(arr): n len(arr) build_heap(arr) # O(n) 建堆 for end in range(n - 1, 0, -1): # 把堆顶最大值放到末尾 arr[0], arr[end] arr[end], arr[0] # 新堆顶下沉堆的有效范围是 [0, end-1] sift_down(arr, end, 0)这里非常容易踩坑的是交换完之后sift_down的堆大小参数要变成end而不是原来的n否则刚换到末尾的最大元素又会被当作堆的一部分导致排序失败。我在帮别人改代码时见过不少次这种错误症状是排序结果基本有序但前面某几个位置乱序原因就是堆的边界没更新到位。堆排序的时间复杂度每一轮sift_down是O(log n)总共要执行n-1轮所以排序阶段是O(n log n)加上建堆的O(n)总体是O(n log n)。而且堆排序是原地排序空间复杂度O(1)这是它相对归并排序的最大优势。但它的缺点是不稳定。举一个简单的例子数组[5a, 5b, 3]建大顶堆后5a和5b的相对顺序就可能发生变化因为堆化过程中不同子树之间的元素会跨区间交换这种交换没有任何机制来保持相等元素的原有顺序。3.4 递归与迭代的实现切换heapify写递归版本教学上很清楚但工程实现里我通常更推荐迭代版本。原因很简单虽然堆的高度是O(log n)递归深度不大不会爆栈但非递归版本避免了函数调用开销性能略高而且对初学者来说递归版的“交换后继续递归”容易漏写迭代版换成while循环反而更能绷住思路。def sift_down_iter(arr, n, i): while True: largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest递归转迭代的一般方法就是把递归调用替换成循环里的状态更新。这里递归调用发生在交换之后对应迭代版本就是更新i为largest然后继续下一轮循环直到i和largest相等等价于递归基线条件“已经满足堆性质”。如果你能用这个视角把递归和迭代互相转换一次你对递归的理解就真的到位了。这比单纯背代码有价值得多因为很多递归算法面试题考的都是这种转换能力。4. 实战选择归并 vs 堆排序4.1 关键指标对比先把两种算法最核心的差异放在一张表里然后我再详细解释每个选择场景。维度归并排序堆排序时间复杂度所有情况O(n log n)O(n log n)额外空间复杂度O(n)O(1)稳定性稳定不稳定原地排序否需要辅助数组是是否适合链表非常适合不适合递归深度O(log n)O(log n)常数因子合并操作较多常数偏高堆调整次数较多常数偏高单从比较次数来看归并排序通常需要更多的比较和复制堆排序虽然比较次数更少但数据交换的随机性更强实际运行时堆排序往往比归并排序慢一些。这也是为什么大多数语言的内置排序没有直接使用堆排序堆排序的地位更多体现在“堆”这个数据结构本身而不是“排序”这个用途上。4.2 归并排序的高频应用场景归并排序第一个典型的应用场景是链表排序。链表的节点只能通过next指针移动没有随机访问能力所以快排需要的前后指针移动在链表上非常别扭堆排序也无法高效地在链表上建堆。而归并排序只需要把链表拆成两半、递归排好、再按顺序合并拼接整个过程都可以用指针完成空间接近O(1)而且稳定。Java的Collections.sort对引用类型的排序底层用的就是TimSort本质上是一种改进的归并排序目的之一就是保证稳定性。第二个场景是外部排序。当数据量大到无法全部放入内存时比如对几个TB的日志文件排序你可以把大文件切分成多个可以放入内存的块每个块内部排序后写回磁盘然后通过多路归并的方式把这些有序块合并成一个大有序文件。这个“多路归并”的思路本质是把归并排序的两路合并扩展成多路合并。这个场景里归并排序的基础地位是无价的。第三个场景是求逆序对数量。经典的算法就是利用归并排序合并过程中的左右指针在左边元素大于右边元素时一次性累加逆序对数量。因为你如果不用归并思路暴力两两比较是O(n²)的而用归并可以在O(n log n)时间内完成。这个考点既考察merge的理解深度也考察分治思维的灵活运用。4.3 堆排序的高频应用场景堆排序本身的排序用途确实不多但它的思想渗透在大量工程场景里。最常见的是TopK问题从一亿个数据里找出最大的K个。你不需要把所有数据都排好序只需要维护一个大小为K的小顶堆遍历数据时如果当前元素大于堆顶就替换堆顶并下沉调整。这样时间复杂度和空间复杂度分别是O(n log K)和O(K)比“全部排序后取前K个”要省太多。我在某个数据分析任务里处理过几千万条记录用堆筛选Top100实测比全量排序快了一个数量级内存占用也几乎可以忽略。第二个场景是优先级队列和定时器。操作系统的任务调度、网络框架的定时器、Java的PriorityQueue、Go的container/heap底层都是堆。它们的共同需求是随时插入一个任务随时取出当前优先级最高或者最快到期的任务。这种动态场景下堆的插入和取出都是O(log n)比维护有序数组要灵活得多也比无序数组找最值要快得多。第三个场景是实时数据流的中位数问题。用一个大顶堆维护较小的一半数据用一个小顶堆维护较大的一半数据新数据进来时先选择插入哪个堆再平衡两个堆的大小那么堆顶就是中位数或中位数的候选值。每次插入和平衡都是O(log n)可以高效应对源源不断的流式数据。4.4 面试中被问到的取舍点面试里最常被问到的问题是既然归并和堆排序都是O(n log n)为什么实际系统里排序很少手写它们这个问题的正经回答思路是绝大多数业务场景直接调用语言标准库的排序函数就够了那些库函数经过了大量调优比如混合快速排序、插入排序、归并排序并且在检测到某些特殊情况时会自动更换策略。只有在特定数据结构链表、特定内存限制嵌入式环境、特定需求稳定性、特定子问题TopK、中位数、优先级队列下才会手动使用归并或堆。另一个高频追问是如果数组很大内存又比较紧而且不需要稳定性你会怎么选这时候堆排序是合理的选择因为它原地排序空间O(1)。但也要注意堆排序的常数因子不低而且存在Cache命中率较差的问题——它访问数组元素的模式是跳跃式的而归并排序的访问模式更接近顺序读写CPU缓存友好度更好。所以在现代计算机上归并排序实际跑起来经常比堆排序快即便它需要额外空间。这也是一个反直觉但很现实的工程结论。5. 常见问题与排查实录5.1 区间与下标最容易翻车的细节我在指导别人写这两种排序时发现90%的bug都出在区间和下标的统一上。归并排序用闭区间[l, r]递归的左右子区间分别是[l, mid]和[mid1, r]如果换成左闭右开[l, r)子区间就变成[l, mid)和[mid, r)。两种方式都能写对但写混了就一定错。建议你自己选定一种之后所有递归、所有merge都按同一个规范来。堆排序里下标问题集中在子节点计算上。数组下标从0开始左孩子是2i1、右孩子是2i2、父节点是(i-1)//2。很多人习惯从1开始的下标体系左孩子2i、右孩子2i1一旦混用堆的结构就完全错乱了。写代码之前先用一个小数组比如[9, 5, 8, 2, 3]手动画一遍堆的树形结构再对着代码检查每个下标对应的节点是否和手画的一致。这样能省下大量调试时间。我刚入行时有一次在面试现场手写归并排序merge函数里把剩余元素接上那两步漏写了导致排序结果每次缺几个元素。面试官提示我“检查区间覆盖”我才意识到两个while兜底复制不是可有可无的因为两个子数组很难刚好交错取完一定有一个数组会先耗尽剩下的元素必须原样拼接。从那以后我给自己定了一个规矩写完排序后必须用规模很小的测试用例比如长度3、4的数组在纸上完整跑一遍逐行核对尤其是边界分支。5.2 典型 Bug 速查表症状可能原因解决方向归并排序结果缺失元素区间越界或merge中剩余元素未复制完整检查闭/开区间一致性、检查两个兜底while归并排序申请内存过多每次递归都创建临时数组改为全局复用temp数组堆排序结果大体有序但局部错乱排序循环中堆的有效边界end没有及时缩小确认每轮交换后sift_down的n参数是end建堆后堆顶不是最大值建堆循环方向写反或漏了部分节点确认从n//2-1倒序到0sift_down后子树仍然非法交换后没有继续递归/循环下沉补上递归调用或更新i继续while递归深度过深导致栈溢出使用递归处理了深度很大的结构如单链表归并排序对数组深度为log n安全链表快排用递归可能爆栈最好改迭代排查的时候我的建议是少用断点多用打印。打印每一层递归的区间范围、merge前后的数组状态或者打印堆化过程中每次交换的数值和下标的对应关系很容易定位出错的位置。与其盯着代码空想不如让程序把过程说出来。5.3 调试技巧与练习路径我自己练算法时有一个非常笨但非常有效的办法用长度为5到8的随机数组配合一个检验函数每次排序后都验证数组是否满足升序条件。对于归并排序再额外打印每一层的merge结果对于堆排序建堆完成后验证堆顶是不是最大值并且每一步交换后堆的有效范围内是否还满足堆性质。这样能及时发现哪一步开始出错而不是等最终结果不对了再去倒推。练习路径上我建议按这个顺序来先用递归求数组最大值理解“拆半-递归-合并”的框架手写merge函数用两个有序数组合并的用例多测几遍写完整的递归归并排序重点练闭区间或左闭右开的统一使用写sift_down递归版再改成迭代版两种版本都要能一次跑对写建堆和堆排序完整流程重点练堆的有效边界维护做两道延伸题比如求逆序对、数组中的第K大元素、合并K个有序链表。每一步都跑通之后再往下一题走不要急于把代码背下来就觉得自己会了。排序算法是递归与分治策略最好的练习题因为你立刻能用一个简单的验证函数判断自己的理解是否正确这个即时反馈对学习特别重要。我个人在实际操作中的体会是归并排序和堆排序放在一起学最大的收获不是会写两个算法而是把“递归三要素”“区间不变量”“复杂度递归式”“稳定性和空间换时间”这些思维习惯一并建立起来。之后再遇到二叉树递归、动态规划、甚至系统设计里的数据流处理很多套路都是相通的。最后再分享一个小技巧面试手写归并排序前先跟面试官确认区间是闭区间还是左闭右开把规则定死再动手这个细节本身就能让你少踩一半的坑。