递归与分治：归并排序与堆排序的深度解析-北京尧图网络

聊排序算法绕不开递归与分治而递归与分治策略里最值得反复琢磨的两个代表就是归并排序和堆排序。我在日常开发里很少会为了“排序而排序”但一旦需要手写底层组件、处理几十万条日志、或者在面试现场写一段稳定的排序代码这两类排序总会第一个出现在脑子里。这篇文章不止讲算法步骤还会把复杂度的直觉推导、边界条件的坑、稳定性带来的业务影响以及我实际调试时踩过的细节一起写出来。想彻底搞懂递归、想弄明白为什么归并排序稳定而堆排序不稳定、想写出一次跑通的排序代码的人都可以按这条线过一遍。1. 递归与分治先把“拆”和“合”想清楚1.1 分治三步曲拆、解、合分治策略的核心思想其实就六个字拆、解、合。把一个规模较大的问题拆成若干个规模较小的子问题子问题继续拆直到小到可以直接解决然后从最小的问题开始逐层把答案合并回完整答案。这里的“递归”不是玄学而是一种“我假设子问题已经有人帮我解决了我只负责把当前问题处理好”的思维方式。拿整理一叠乱序试卷举例。你不会一张一张地从头调整到最后而是先把试卷分成两半让两个人各自整理如果每一半还是太多就继续分下去直到每个人手里只有一两张随手就能排好。最后再把两摞已经有序的试卷按顺序合并成一摞。这个场景里“拆”就是分段“解”就是在小段上排序“合”就是把有序段合并。归并排序完全复刻了这个过程只不过把“排试卷”变成了对数组排序。之所以要这样设计是因为排序的最基本操作是“比较两个元素的大小”。如果直接在原始数组上做逐位调整一次比较往往只能消除一个逆序对而分治把数组拆成两半分别排好后再合并一次合并就能同时处理一大片逆序关系整体效率自然上去了。1.2 递归必须想清楚的终止条件写递归最怕的不是递归本身而是“不知道什么时候该停”。归并排序的递归终止条件非常干脆当待排序区间里没有元素或者只剩一个元素时直接返回。我见过不少初学者写递归排序时把边界写成left right才递归然后又写了mid (left right) // 2结果在数组长度为 2 时左半区是空区间右半区是原区间递归永远不会到终止条件最终栈溢出。真正稳定的写法是左闭右闭区间[left, right]当left right时说明区间为空或只有一个元素不需要再处理。递归的深度也需要心里有数。归并排序每次把区间一分为二深度是 O(log n)即使处理一百万条数据递归栈深度也只有二十层左右完全不用担心栈溢出。但堆排序中的heapify如果用递归实现它的深度取决于堆的高度同样是 O(log n)也不会有栈压力。真正需要警惕的是那些每层只减少一个元素的递归场景比如朴素快排在最坏情况下会递归 n 层那种情况下栈溢出才是真实风险。1.3 从递归树直观理解 O(n log n)很多人把 O(n log n) 当作需要背下来的结论其实从递归树上一眼就能看出来。归并排序每一层递归做的事情是把所有子区间两两合并合并一个长度为 m 的区间大约需要比较和复制 m 次。整个数组长度是 n同层所有子区间长度加起来就是 n所以每一层的合并总耗时是 O(n)。递归树的深度是 log n 层因为每次规模减半从 n 到 1 需要 log n 次。每层 O(n)总耗时就是 O(n log n)。这个推导方式比硬记公式实用得多因为它能解释“为什么归并排序无论输入好坏都是 O(n log n)”——因为拆分总是对半分的合并总是完整跑一遍不存在快速排序那种“每次选到最差 pivot”导致递归树退化成一条直线的情况。分治策略到这里埋下了一个关键伏笔递归树每层的工作量是否均衡直接决定算法能否保持 O(n log n)。归并排序的合并每层工作量都是 n所以稳定后面要讲的堆排序依靠的则是完全二叉树的层高本质上也是 O(log n) 层每层调整代价有界整体也就不会退化。2. 归并排序最值得逐行手写的排序2.1 整体流程拆到不能再拆再两两合并归并排序的实现思路可以拆成两个阶段。第一个阶段是“递归分解”把数组从中间一分为二再分别对左右两半做同样的操作第二个阶段是“合并”把两个已经排好序的子数组合并成一个有序数组。用数组[38, 27, 43, 3, 9, 82, 10]看一遍过程。第一次分解中点在第 3 个元素附近分成[38, 27, 43, 3]和[9, 82, 10]。继续分解直到得到单个元素的区间例如[38]、[27]、[43]、[3]等。合并时先从[38]和[27]开始得到[27, 38][43]和[3]合并成[3, 43]接着把[27, 38]和[3, 43]合并成[3, 27, 38, 43]。右侧同理最后合并整个数组。这里有个容易忽略的细节合并两个有序数组时每次比较两个子数组的头部元素把较小的那个放入结果。因为左右两个子数组都已经有序所以头部的其中一个一定是全局最小值。每次放入一个元素指针向后移动直到某个子数组被取完再把另一个子数组剩余部分直接接上。2.2 核心代码用一份临时数组完成合并归并排序的“合”是整个算法的核心代码层面最大的难点不是递归而是合并时临时数组的管理。最直观的写法是每次合并都新建一个数组但这样会产生大量对象分配在数据量大时性能很难看。我习惯在递归入口创建一份与原始数组等长的临时数组合并时直接往临时数组对应位置写值再拷贝回原数组。def merge_sort(arr, left, right, tmp): if left right: return mid (left right) // 2 merge_sort(arr, left, mid, tmp) merge_sort(arr, mid 1, right, tmp) merge(arr, left, mid, right, tmp) def merge(arr, left, mid, right, tmp): i left j mid 1 k left while i mid and j right: if arr[i] arr[j]: tmp[k] arr[i] i 1 else: tmp[k] arr[j] j 1 k 1 while i mid: tmp[k] arr[i] i 1 k 1 while j right: tmp[k] arr[j] j 1 k 1 for p in range(left, right 1): arr[p] tmp[p]这里有三个边界点值得反复检查。第一mid的归属。左区是[left, mid]右区是[mid 1, right]两区没有重叠也没有遗漏。如果写成mid - 1或mid偏移就会漏元素或重复合并。第二两个while循环里和的差别。上面这段代码用的是也就是说左侧元素和右侧元素相等时先取左侧这样才能保证归并排序的稳定性。第三写回原数组时tmp的下标不是从 0 开始而是从left开始。很多人习惯临时数组下标从 0 开始拷回去时才发现位置错位。最好的做法就是让tmp的下标与被合并区间的下标保持一致省去换算的麻烦。2.3 稳定性为什么重要等于号写在哪一行排序算法的“稳定”是指两个相等的元素排序后相对顺序与原始顺序保持一致。归并排序天然可以做到稳定因为合并相等的两个元素时只要确保先取左侧子数组的元素即可。也就是说比较的时候用而不是。如果某天你把if arr[i] arr[j]不小心改成了那么当左右两边元素相等时会先取右侧元素这样相对顺序就反了。看似无关紧要但在业务上可能引发连锁反应。举个例子。订单列表先按下单时间升序排列然后要求按用户编号升序排列。如果第二趟排序是稳定的那么相同用户编号的订单仍然保持下单时间顺序如果第二趟排序不稳定相同用户编号的订单时间顺序就可能被打乱。这就是为什么很多数据库排序、多关键字排序都偏爱稳定排序。稳定性的代价也很清楚归并排序需要额外 O(n) 的空间存临时数组而且合并时要频繁读写临时数组和原数组内存开销和拷贝耗时比原地排序高。换句话说它是用空间换稳定和确定性。2.4 归并排序的优化思路工程上不会直接写一个朴素归并排序通常会在几个点上做优化。第一个优化是小数组改插入排序。当递归拆分到区间长度小于某个阈值时比如 16 或者 32直接使用插入排序而不继续拆分。原因是递归调用本身有开销小数组上的插入排序常数极低实测往往比继续递归合并更快。这个阈值不要拍脑袋最好在自己的数据规模上测一下不同语言、不同编译器下的最优阈值会差不少。第二个优化是复用临时数组。前面代码已经在递归入口创建了一份临时数组避免每次合并都分配新数组。如果递归函数里写tmp []然后tmp.append在大数组上会有大量内存分配和垃圾回收压力。第三个优化是判断是否需要合并。如果左子数组的最大值已经小于右子数组的最小值说明两个子数组连接起来就已经有序不需要执行合并。这个提前退出对“基本有序”的输入特别有效能直接把部分递归树剪掉。3. 堆排序用数组模拟一棵完全二叉树3.1 父子节点下标关系是堆的地基堆排序的思路和归并排序完全不同。归并排序是靠“拆分后合并”逐渐排好序堆排序则是先把数组调整成一个堆利用堆顶最大或最小的性质一次次把极值放到最终位置。这里的“堆”是一棵完全二叉树但它不是靠指针连起来的而是直接存在数组里。数组下标天然映射了树的位置根节点在位置 0对于任意位置i它的左孩子在2 * i 1右孩子在2 * i 2父节点在(i - 1) // 2。这个关系是整个堆排序的地基任何一个下标算错后面的操作都会连环出错。我一开始从 C 语言式 1 下标切换到 0 下标时老是把左孩子写成2 * i然后就会访问到错误的位置。建议刚学的时候不要贪快先用小数组把下标关系列一遍确认 0 下标下左孩子是 1、右孩子是 2父节点是 0后再写代码。堆排序通常用大顶堆来做升序。大顶堆的意思是每个节点的值都大于等于它的子节点因此堆顶一定是整个数组的最大值。排序时先把数组建成大顶堆然后把堆顶和数组末尾元素交换最大元素就到了正确位置接着缩小堆的有效范围再调整剩下的堆继续取最大值放到倒数第二个位置。重复下去数组就有序了。3.2 堆化从最后一个非叶子节点开始建堆的过程叫“堆化”或“下沉”。对某个节点需要比较它和它的左右孩子如果孩子比它大就把孩子里更大的那个换上来然后继续向下检查被换下去的那个节点直到它不再比孩子小或者到达叶子节点。关键问题是从哪个节点开始做下沉调整答案是最后一个非叶子节点。在完全二叉树里最后一个非叶子节点的下标是n // 2 - 1。从它开始向前遍历到根节点逐个做下沉调整就能把整个数组建成堆。为什么不用从叶子节点开始因为叶子节点没有孩子不存在“下沉”的必要。从最后一个非叶子节点开始本质上是在后往前一层层建立堆每个节点下沉时它的左右子树已经是大顶堆所以只要处理当前节点这一个“入侵者”。堆化的代码可以递归也可以迭代。递归版本思路直观迭代版本可以避免 Python 默认递归深度限制的担忧。下面是递归版本def heapify(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] heapify(arr, n, largest)这里n是当前堆的有效长度不是原始数组长度。每次递归调用时largest变成了新的父节点但n保持不变因为堆的范围没有变。容易写错的地方是在递归调用里误把n改成了largest 1之类的值会出现数组越界。3.3 排序主体先建堆再不断交换堆顶有了heapify堆排序的完整流程就很清晰了。建堆从n // 2 - 1开始倒序执行heapify(arr, n, i)直到i 0。这一步做完数组已经满足大顶堆性质堆顶也就是arr[0]是最大值。排序从最后的下标i n - 1开始循环到i 1。每轮把arr[i]和arr[0]交换最大值被放到数组尾部然后对当前缩减后的堆执行heapify(arr, i, 0)重新调整堆顶。这里的i既是要交换的下标也是下一轮堆的有效长度含义要盯清楚。def heap_sort(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0)很多人在建堆后的交换阶段写错是因为忽略了heapify的第二个参数。每一轮交换后数组尾部的元素已经是排好序的不应该再参与堆调整所以必须把堆的有效长度缩小。这里的i正好就是新的有效长度不能写成n。3.4 堆排序的空间优势与固有短板堆排序最大优势是原地排序空间复杂度只有 O(1)。它不需要额外的临时数组也不像递归归并那样需要维护递归栈。这一点在嵌入式、内存受限的环境里价值很高。但堆排序也有一个常被忽略的短板虽然时间复杂度和归并排序、快速排序一样是 O(n log n)但实际运行常数通常比快速排序大。原因是堆排序对数组的访问模式是跳着访问的i、2*i1、2*i2这些下标之间的关系让 CPU 缓存命中率远低于快速排序和归并排序的连续访问。再加上堆排序在建堆完成后堆顶被拿出来放到末尾然后又要下沉每次下沉都比较几次总的比较次数比快速排序多不少。所以工程上需要 O(1) 空间且不要求稳定时堆排序可以上如果内存够用且追求实际性能归并排序通常更稳。堆排序更大的舞台其实是优先级队列、Top K 问题和调度器这些问题只是借用“堆”这一数据结构不是每次都要完整排序。4. 实际开发中的选型与排错4.1 归并排序的边界条件自查清单我把归并排序常见的错误整理成一份清单每次手写完后逐条检查基本能一次跑通。第一检查递归终止条件。必须是left right返回不能是left right否则空区间会进入死循环。第二检查mid的赋值。mid (left right) // 2左区右端是mid右区左端是mid 1。如果数组下标写错合并结果会乱。第三检查合并循环里的指针推进。两个主循环分别对应左区和右区循环条件为i mid和j right。合并完一个数组后另一个数组剩余部分必须复制进去漏掉这个步骤会导致元素丢失。第四检查写回。临时数组下标和原数组下标要一致写回要从left到right不能从 0 开始。最稳妥的写法是合并时临时数组的下标也初始化为left复制时直接全区间写回。第五检查稳定性。如果要求稳定左边元素必须用比较而不是。可以在测试数据中加入重复元素验证排序前后相同元素的相对位置。4.2 堆排序的常见错误与调试方法堆排序的坑比归并排序更隐蔽因为肉眼很难从最终结果判断是哪一步出了问题。常见错误有几个。最后一个非叶子节点算错有人记成n // 2有人记成(n - 1) // 2。正确是n // 2 - 1原因是数组最后一个元素下标是n - 1它的父节点是(n - 2) // 2在 Python 整数除法下这个值等于n // 2 - 1。heapify中孩子下标越界判断left n和right n不能省略。堆排序过程中堆的有效长度不断缩小如果直接用原始n会把已经放到末尾的最大元素重新拉进堆里排序结果错乱。交换后忘记继续下沉堆顶被交换上来一个较小元素后必须对新的堆顶做heapify否则不满足大顶堆性质下一轮取值就会拿错。调试堆排序时我通常写一个打印函数把数组按完全二叉树的结构缩进打印。这样能直观看到某个节点和左右孩子的关系定位是哪一步的下沉出了问题。还可以在每次交换后打印数组对照“末尾最值已经就位”和“前面仍然满足堆”两个条件逐步核对。4.3 从排序到真实需求逆序对、Top K、稳定性选型排序算法真正有嚼劲的地方是它们能灵活改造解决比“排个序”更大的问题。归并排序可以在合并阶段顺手统计逆序对。合并两个有序子数组时如果右侧元素比左侧小那么左侧从当前指针到mid的所有元素都比右侧这个元素大这些元素与当前右侧元素都构成逆序对数量直接增加mid - i 1。这个技巧比暴力双重循环高效得多时间复杂度还是 O(n log n)。堆排序思想则可以解决 Top K 问题。比如要从一亿条日志里筛出访问量最大的 100 条不需要把所有日志完整排序只需要维护一个大小为 100 的小根堆每个新元素与堆顶比较比堆顶大就替换并下沉。最终堆里就是最大的 100 条时间复杂度 O(n log k)内存只有 O(k)。稳定性选型同样落到业务上。前面提到多关键字排序场景最好用稳定排序。而如果你只是要取一批数据里的最大值堆排序的稳定性根本不重要堆结构本身就够用。选型不要只盯复杂度表还要看数据规模、内存限制和业务是否关心相同元素的相对顺序。4.4 排序算法对比速查表算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性典型场景归并排序O(n log n)O(n log n)O(n log n)O(n)稳定外部排序、多关键字排序堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地排序、优先级队列、Top K快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定通用高性能排序配合优化插入排序O(n)O(n²)O(n²)O(1)稳定近乎有序的小数组这张表不是用来背的而是用来做决策的。如果业务数据量小且基本有序插入排序反而最快如果数据量巨大且内存充足归并排序的稳定性和稳定复杂度最让人省心如果内存受限且不关注稳定性堆排序是安全选择如果追求通用场景下的平均表现工程库里的快速排序优化版本通常是首选。5. 我写递归算法时的三个习惯5.1 先信子问题再写当前层我在刚接触分治时最大的心理障碍是递归展开时容易陷入细节总想把每一步递归都推演完。后来养成了一个习惯只关注当前这一层并假设递归调用返回的子问题答案一定是正确的。这一步对归并排序尤其管用写merge_sort(arr, left, mid, tmp)时我心里默认左半区已经拍好序不需要再问它是怎么排好的同样右半区也是。这样我就能把全部注意力放在merge的合并逻辑上。这个习惯也可以推广到其他递归代码。先想清楚“这一层我要做什么”再想清楚“我从子问题拿到什么样的输入”最后补上终止条件。顺序不要反否则容易在递归迷宫里出不来。5.2 用最小用例把递归调用栈画出来代码写完后不要立刻跑大数据。我用一个四到六个元素的数组把递归调用过程画在草稿纸上。归并排序就画分解和合并的层级堆排序就画每个节点i下沉前后的堆结构。这种方式能发现很多肉眼看不到的问题比如下标偏移一位、终止条件差一个位置、临时数组写回错位等。画完之后再跑几个极端的测试用例空数组、只有一个元素、两个无序元素、所有元素相同、已经有序的数组。这些边界用例能最大限度暴露边界错误。5.3 把稳定性写进测试用例里最后分享一个检查稳定性的方法。准备一组带有唯一编号的对象比如(编号, 成绩)先用成绩排序再验证相同成绩的编号顺序是否保持。这个测试最能区分归并排序和堆排序在实际业务中的差异。归并排序只要等于号正确测试一定通过堆排序如果要求稳定则根本不满足条件测试注定失败这时你就知道该换方案了。递归与分治策略并不是两个孤立的知识点。归并排序把分治的“拆解合并”做到了极致堆排序则用数组上的树形结构配合递归调整换来了原地排序。弄懂这两个算法你会更清楚“O(n log n)”到底是怎么来的也会在真正面对大规模数据时知道该为稳定性、空间、性能付出什么代价又该在什么环节坚持自己的选择。

递归与分治：归并排序与堆排序的深度解析

相关推荐

基于IPFS与以太坊的去中心化文件存证平台实战

PGD对抗训练实战：从数学原理到鲁棒模型调参避坑指南

贾子理论：拆解AI实验室全员大会的三层信号模型

更多资讯

鸿蒙录音实时转文字：音频流采集与流式语音识别实战

Strassen矩阵乘法：Python实现、分治优化与性能分析

论文格式总错？AI写作工具用“样式驱动”重构目录与参考文献

宝塔面板安装教程：从零搭建LNMP环境与安全配置

QC 2.0 快速充电接口控制器D1531

Activiti运行表ACT_RU_VARIABLE深度解析：变量作用域与存储机制

今日更新

NetSpot 实战：用信道分析与频宽优化解决 Wi-Fi 卡顿

C++ split() 字符串分割的五种实现与性能实测

R语言坐标轴范围设置：从xlim/ylim到coord_cartesian的完整指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？