我一直觉得递归与分治策略这几个字光看定义是看不出威力的。直到我把归并排序和堆排序连着看了好几遍又被问过几次“为什么这两个算法经常放在一起讲”我才慢慢琢磨明白分治解决的是“怎么拆问题”递归解决的是“怎么把拆开的问题做到底”而归并排序和堆排序恰好把这套逻辑用两种完全不同的方式展示出来了。这篇文章我把它们放到一起复盘从实现细节、复杂度分析到工程里的场景取舍一次性写清楚。不管你是准备面试还是想在项目里把排序用明白应该都能找到点想看的东西。1. 两个算法给我的第一个共同印象问题都能“递归地”变小1.1 分治是拆解问题的策略递归是执行策略的手段很多人把“递归”和“分治”当成同一个东西其实不是。分治是一种策略它要求你回答三个问题问题能不能拆成更小的同类问题拆完之后子问题能不能独立解决子问题的解能不能合并回原问题的解归并排序对这三个问题的回答非常工整把一个数组从中间切成两半左半边排序右半边排序再把两个有序段合并成一个有序段。递归在这里扮演的角色只是“分治策略”最自然的翻译方式——每次函数调用都在处理一个规模减半的同类问题。堆排序看起来不太像分治因为它的外层是一个迭代循环并没有显式的“切分-合并”动作。但它的核心操作 maxHeapify 本身就是一个天然递归的过程先判断当前节点是否满足堆性质如果不满足就把它和较大的孩子交换然后递归地继续调整那个被破坏的子堆。每向下递归一层关注的范围就缩小到一棵更小的子树。所以从“同一个处理规则递归地作用在缩小的问题上”这个角度看堆排序和归并排序属于同一族思路只是组织数据的方式完全不同。1.2 排序问题本身就是递归结构最好的样本数组排序很适合用来理解递归因为它的子问题边界非常清楚。对长度为 n 的数组排序可以变成“对左半个数组排序、对右半个数组排序、把结果合并”。对堆来说则是“保证某个子树是堆、递归处理它的子子树”。这不是偶然因为排序天然具有可分解性局部有序可以组合成全局有序局部满足堆性质也可以组合成全局满足堆性质。我在学习阶段的体会是不要只背归并排序和堆排序的代码那样过两周就忘。要刻意问自己一句每一层递归到底在保证什么归并里递归返回值是“这段区间已经有序了”堆排序里递归返回值是“以这个节点为根的子树已经满足堆性质了”。一旦把这条主线抓住后面的边界条件和细节错误基本都能自己排查出来。2. 归并排序的分治全流程从递归树到 merge 实现2.1 分解、解决、合并每一步到底在做什么归并排序的代码结构是所有分治算法里最直白的一个核心就三个动作。分解把区间[left, right]从中间一分为二即mid left (right - left) / 2。解决递归地对[left, mid]和[mid 1, right]分别排序。当区间只剩一个元素时它天然有序递归终止。合并把两个已经各自有序的区间合并成一个大的有序区间。这里最反直觉的地方是真正的比较和移动全部发生在合并阶段而不是分解阶段。分解只改变下标不改变数据。可以类比成整理一手扑克牌你先把牌分成两堆每堆内部排好序然后每次从两堆顶部各取一张最小的牌比较把更小的那张放入结果中。整个过程不断重复直到两堆都为空。我见过不少人把归并排序写成这样先 merge再对左右递归排序。这在顺序上是错的。分治要求我们先让左右两边本身有序然后合并才有意义如果先合并左右两边还是乱序合出来的结果也是乱的。2.2 merge 的边界处理与哨兵写法merge 是归并排序里唯一有技巧的部分它的任务是合并两个有序区间。常规写法是用两个指针i和j分别指向左半段和右半段每次比较当前元素把更小的放入原数组然后移动对应指针。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int L[n1], R[n2]; for (int i 0; i n1; i) { L[i] arr[left i]; } for (int j 0; j n2; j) { R[j] arr[mid 1 j]; } int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } } while (i n1) { arr[k] L[i]; } while (j n2) { arr[k] R[j]; } }上面这段代码k从left开始而不是从 0 开始是因为我们合并的是arr的某个子区间不是整个数组。这个细节看着简单实际写错的人非常多。还有一种经典的哨兵写法在L和R的末尾放一个“无穷大”值这样就不用在循环里判断i n1 j n2了因为当某一边遍历完哨兵值一定大于另一边剩余的元素循环会继续把另一边的元素写回去。void merge_with_sentinel(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int L[n1 1], R[n2 1]; for (int i 0; i n1; i) { L[i] arr[left i]; } for (int j 0; j n2; j) { R[j] arr[mid 1 j]; } L[n1] 2147483647; R[n2] 2147483647; int i 0, j 0; for (int k left; k right; k) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } } }哨兵写法的好处是省掉两个收尾循环代码看起来更紧凑。但它有个潜在前提数据本身不会达到INT_MAX这个值否则哨兵会和真实数据混淆可能导致排序结果不正确。实际工程里我倾向用普通写法正确性更直观也方便调试时看边界条件。哨兵写法更适合个人练习和对性能极致抠细节时使用。2.3 递归树的高度只有 O(log n)每一层总操作量是 n归并排序为什么稳定是 O(n log n)用递归树看非常清楚。假设数组长度是 8第一层有一个规模为 8 的问题第二层有两个规模为 4 的问题第三层有四个规模为 2 的问题第四层有八个规模为 1 的问题。每一层的所有子问题加起来规模总和都是 8。每一层要做多少合并工作合并两个总长度为 m 的有序区间需要处理 m 次比较和拷贝所以这一层的总工作量是 O(n)。递归树高多少从规模 n 降到 1每次除以 2最终高度是 log2(n) 的级别。所以总时间复杂度就是 O(n log n)。第 0 层 8 第 1 层 4 4 第 2 层 2 2 2 2 第 3 层 1 1 1 1 1 1 1 1这个递归树结构还解释了另一个事递归调用栈的深度只有 O(log n)不会像某些递归写法那样发生栈溢出。理论上处理任意大规模数据归并排序的递归深度都很可控。这也是它在外部排序里能被当成基础算法的原因之一——递归深度低合并逻辑又是纯顺序访问对磁盘和文件系统都友好。2.4 自底向上的迭代版归并分治策略不一定非要用递归实现也可以用迭代从底层做起。自底向上的归并排序思路是先把数组看成一个个长度为 1 的有序块然后相邻两块两两合并成长度为 2 的有序块再合并成长度为 4 的有序块直到整个数组有序。void mergeSortBottomUp(int arr[], int n) { for (int width 1; width n; width * 2) { for (int left 0; left n; left 2 * width) { int mid left width - 1; if (mid n - 1) { continue; } int right left 2 * width - 1; if (right n) { right n - 1; } merge(arr, left, mid, right); } } }这段代码里有个容易忽略的点当右半段不存在时也就是mid n - 1这一轮不需要合并。另外最后一个块的right可能超出数组末尾必须取n - 1。迭代版归并最大的优势是省掉了递归调用接近标准库函数的使用习惯它也是理解外部排序里“多路归并”概念的前置知识。实际物理内存中数据无法一次性载入时你做的就是这种分块排序加归并的思路。3. 堆排序藏在数组里的完全二叉树3.1 用数组下标表达完全二叉树的父子关系堆排序不是靠“切分数组”来分治而是靠“堆”这种数据结构。堆本质上是一棵完全二叉树所谓完全二叉树是指除了最后一层之外每一层都是满的最后一层也尽可能左对齐。这种结构有一个巨大的好处可以用数组紧凑存储不需要指针。如果用 0-based 下标存储那么对于一个下标为i的节点父节点下标是(i - 1) / 2左孩子下标是2 * i 1右孩子下标是2 * i 2最大堆的性质是每个节点的值都不小于它的孩子节点。也就是说堆顶元素一定是全局最大值。你不需要维护整个数组完全有序但你要保证这个“局部大于”的性质成立。这个性质维护起来非常便宜调整一次只需要沿着一条路径下沉代价 O(log n)。3.2 建堆为什么从最后一个非叶子节点往上调整建堆是堆排序第一个容易写错的步骤。先给出代码再解释为什么。void buildMaxHeap(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { maxHeapify(arr, n, i); } }关键问题是为什么从n / 2 - 1开始而不是从n - 1开始也不是从 0 开始因为下标从n / 2到n - 1的节点全是叶子节点。叶子节点没有孩子天然满足最大堆性质不需要调整。从它们上面开始倒着往根调整才符合“先保证下面的子树已经是堆再处理父节点”的逻辑。如果从根开始往下调整那么当前节点的左子树和右子树可能还没有满足堆性质你把根下沉到某个孩子位置后并不能保证下沉路径上的所有子树都正确。自底向上的建堆保证maxHeapify被执行时被处理节点的两个孩子都已经各自是堆因此一次下沉就能让以该节点为根的整棵子树变成堆。maxHeapify的实现如下void maxHeapify(int arr[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; maxHeapify(arr, n, largest); } }注意maxHeapify中所有比较都有 n这样的边界限制因为当前的“有效堆大小”并不一定等于原数组长度。这个n是参数很容易被忽略。3.3 排序循环交换堆顶、缩小堆、再下沉建好最大堆之后数组中的最大值已经在arr[0]。堆排序的主体循环做的事情非常机械把arr[0]和当前堆的最后一个元素交换这样最大值被“固定”到数组末尾。把有效堆大小减一因为末尾已经排好不再参与后续调整。对根节点arr[0]调用maxHeapify恢复最大堆性质。每轮循环之后数组末尾就会多一个排好序的最大值随着 i 从 n-1 递减到 1整个数组完成升序排序。void heapSort(int arr[], int n) { buildMaxHeap(arr, n); for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; maxHeapify(arr, i, 0); } }这里面最容易被忽略的是maxHeapify(arr, i, 0)中的i。它表示当前有效堆的大小。如果写成maxHeapify(arr, n, 0)每一轮都会把已经排到末尾的最大值重新拉回堆顶比较排序结果会乱。这类 bug 非常阴险因为小规模数据测试时可能碰巧没错数据稍大就暴露。堆排序的时间复杂度是 O(n log n)。建堆过程看起来要循环 n/2 次每次调 maxHeapify 需要 O(log n)直觉上像是 O(n log n)但通过摊还分析可以证明建堆的真实复杂度是 O(n)因为越靠近底层的节点高度越小需要调整的路径长度很短。真正的 O(n log n) 消耗出现在后面的 n-1 轮交换和下沉中。4. 归并与堆排序的“性格”差异稳定性、空间与常数因子4.1 稳定性归并稳定堆排序不稳定“稳定性”是一个看起来不太起眼、实际非常重要的性质。如果数组里有两个相等的元素5a和5b排序后5a仍然出现在5b前面我们称这个排序是稳定的。归并排序的稳定性来自 merge 阶段的比较规则当L[i] R[j]时我们先取左半段的元素。也就是说两个相等元素相遇时左半段那个会被优先放回原数组所以相对顺序被保留。这一点在工程里很重要比如你先按姓名排序再按部门排序稳定排序能让第二次排序后部门相同的人仍然按姓名有序。堆排序则不稳定。原因在于它会把堆顶元素直接交换到数组末尾这种“跨越”式的交换可能把相同元素的相对顺序打乱。举一个简单的例子数组[5a, 3, 5b, 1]建堆过程中你很难保证两个 5 的相对位置不发生颠倒。所以如果你需要保持相等元素原有顺序堆排序直接出局。4.2 空间归并需要 O(n)堆排序原地完成归并排序的标准实现需要额外一个和原数组等长的辅助数组用来在 merge 阶段暂存数据。这意味着空间复杂度 O(n)。如果对这个额外空间有要求比如在内存受限的嵌入式环境里处理几千万条记录O(n) 辅助空间可能是不可接受的。堆排序的空间复杂度是 O(1)它只需要少量临时变量所有操作都在原数组上完成。这是堆排序最大的现实优势。当然如果考虑递归实现版本maxHeapify的递归调用会有 O(log n) 的栈空间但相比归并的 O(n) 辅助数组已经轻量太多了。不过“原地”并不代表“更快”涉及到 CPU 缓存和内存访问模式时事情会更复杂下面单独说。4.3 常数因子为什么堆排序“赢了复杂度输了实测”理论上归并排序和堆排序都是 O(n log n)但在绝大多数真实数据上归并排序往往跑得比堆排序快快排又往往比归并快。问题出在常数因子和缓存局部性。堆排序的调整过程会频繁访问2*i1和2*i2这两个下标它们之间通常不是连续内存跳跃访问会对 CPU 缓存不友好。而且每次 maxHeapify 至少涉及父节点和两个孩子的比较比较次数相对较多。归并排序则是把元素连续地拷贝到辅助数组、再连续地写回原数组内存访问模式非常线性现代 CPU 的预取机制可以“猜到”下一步访问哪里。所以同样是 O(n log n)实际耗时差距可能很大。我做一个不完全严谨的直观对比在随机生成的 100 万个整数上各跑一次大致是算法平均时间复杂度最坏时间复杂度稳定性辅助空间实际表现归并排序O(n log n)O(n log n)稳定O(n)中等偏快利于缓存堆排序O(n log n)O(n log n)不稳定O(1)偏慢比较次数多快速排序标准库常见O(n log n)O(n²)不稳定O(log n)通常最快这不是说堆排序一无是处。当内存严格受限、或者你并不需要一个通用排序而只是想快速拿到最大几个元素时堆仍然是最好的选择。它不是一个糟糕的排序方案但它的价值更多体现在数据结构本身而不是作为通用排序器。5. 实战中我踩过的坑和调试方案5.1 归并排序的三个经典边界问题第一个坑是递归终止条件写成if (left right)。归并排序把区间拆成[left, mid]和[mid1, right]当 left 等于 right 时区间已经只有一个元素应该返回。如果等号处理不好可能无限递归或者多递归一层导致索引越界。正确写法是if (left right)。第二个坑是合并时指针k的起点。前面提到过k必须从left开始有的人从 0 开始写结果排序完只有一小段正确。这个小 bug 用脑内模拟一遍就能发现但当你疲劳赶工时非常容易写错。第三个坑是求mid时写成(left right) / 2。当 left 和 right 都很大时这个表达式可能整型溢出。虽然现在多数机器上 int 溢出后计算结果未必立刻崩但排序结果会莫名其妙错误。写left (right - left) / 2是一个值得坚持的好习惯。5.2 堆排序里最容易翻车的三处第一处是父子下标换算混用。教材里很常用 1-based 下标父节点是i/2孩子是2i和2i1。一旦你照抄到 0-based 数组里就会写出left 2 * i而不是2 * i 1数组越界或者访问错位几乎是一定的。第二处是maxHeapify里的n没有跟着有效堆大小走。排序主循环每轮都缩小堆如果不把当前堆大小传进去“已经排出”的末尾元素会被再次当作堆内元素参与调整已经排好的部分会被重新打乱。第三处是建堆循环的起点。从n/2 - 1开始是正确的从n/2开始通常会多一次无效调用问题不大从n-1开始会出现一堆无意义的叶子调整性能变差但结果也许没错真正错误的是从 0 开始正序遍历因为子树还没建好堆性质不可能正确建立起来。5.3 让算法“可观测”的调试方法我会给每个排序算法配一个小的“验证器”排序后立刻扫描一遍看是否非降序int isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; }在验证器之外还建议准备四组测试数据完全随机数组、已经升序的数组、已经降序的数组、所有元素都相同的数组。很多排序 bug 只会在某一种数据上暴露。比如归并排序在逆序数据上通常没问题但堆排序如果建堆起点写错逆序数组最容易发现异常。更直观的办法是打印中间状态。归并排序可以打印递归拆分的过程观察每一层的区间范围堆排序可以打印每轮交换堆顶后的数组内容看末尾是否逐次固定最大值。这个做法比较笨但非常有效。我在调试一个排序工具时就是靠打印一轮堆调整后的数组才抓到有效堆大小没传对的问题。6. 工程场景里到底该怎么选以及我的一些经验体会6.1 归并排序的现实用途外部排序与链表排序通用排序大家都默认用标准库里的排序函数因为它是各种优化技巧打磨过的结果比如把快排、插入排序、堆排序混合使用。但归并排序有两个真实场景很难被替代。第一个是外部排序。当数据量大到没法一次性装入内存你需要把大文件切成多个小片段每个片段分别读入内存排好序写回磁盘最后把所有有序片段做多路归并。归并的过程天然适合顺序读写不需要随机访问这对磁盘和网络文件系统都友好。我曾在模拟项目X里处理超过内存容量的日志数据核心思路就是分块排序加归并整个过程稳定可控。第二个是链表排序。链表的节点分散在内存中快排的随机访问和堆排序的下标访问都不好用而归并排序对链表非常自然先把链表切分成两半递归排序再把两个有序链表按指针接起来完全不需要额外数组空间开销可以做到 O(1)。所以很多语言标准库在排序某些特定容器时会选用归并思路。6.2 堆排序的真正价值优先队列、TopK 和时间管理在通用排序里堆排序不是第一选择。但“堆”这个数据结构本身无处不在。你只需要快速拿到当前最大或最小的元素用一个最大堆或最小堆就够了。任务调度器要每次取出优先级最高的任务本质上就是堆的操作找一批数据里最大的 K 个元素维护一个大小为 K 的最小堆每次遇到比堆顶大的元素就替换并调整一趟扫描下来结果就出来了不需要全量排序流式数据的中位数也可以用两个堆来维护。所以我的建议是不要只把堆排序当成一个排序算法去背而是当成二叉堆的入门操作来学。你会真正受益的是建堆、调整、下称这些动作本身而不是那 n 次交换堆顶的排序步骤。6.3 一个不严谨但直观的实测印象我在本地对随机整数数组做过简单测试规模从 10 万到 100 万不等印象最深的是在接近有序的数据上库函数排序往往非常快归并排序得益于合并时对有序子段的利用也不差堆排序则是无论数据是否有序时间都差不多。堆排序的综合表现几乎总是比归并和快排慢一些。这不是说堆排序理论复杂度骗人而是复杂度分析丢掉了常数和局部性。它提醒我在算法选型时不能只看大 O。如果内存充足、要求稳定归并更好如果内存很紧、只需要部分有序信息堆更好如果没有任何特殊约束优先相信标准库的排序函数。6.4 递归与分治给我留下的两点体会第一点体会是递归的难点不在于“调用自己”而在于你要准确描述“规模更小的子问题”和“子问题之间如何组合”。归并排序能写对是因为你只需要相信两句话左半边排好右半边排好然后一合并整个区间就排好了。这种“相信递归”的思维方式在后续处理树、图、区间问题时会反复用到。第二点体会是算法复杂度看总量工程实现看细节。堆排序和归并排序的渐近复杂度相同可实际表现差距很大同样一个归并辅助数组分配方式不同、边界处理不同性能也能差出一大截。多跑测试、多打印状态比空想复杂度更容易发现真正的瓶颈。最后分享一个小技巧如果你在写递归类算法时总觉得哪里不对先在纸上画一棵规模为 8 的递归树手动模拟两层然后把每一层“应该返回什么”写在边上。归并排序返回有序数组段堆调整返回满足堆性质的子树。这比直接单步调试更快也能帮你绕过很多隐蔽的边界问题。
