很多学习 C 语言的同学都会有这种感觉冒泡排序和选择排序刚弄明白一看到归并排序就懵了。代码不长但递归一层套一层return 来 return 去脑子完全跟不上程序执行顺序。即使勉强背下了代码过两个星期再写还是不会。这不是你笨而是学习路径出了问题。归并排序真正的难点不在于代码本身而在于两个关键点一是你还没在脑袋里形成“整个数组被不断拆成两半再两两合并回去”的动态画面二是你还没理解递归在这里其实是一种“先递后归”的控制结构而不是数学公式。这篇文章的目标很直接用尽可能通俗的方式把归并排序的分治思想、图解过程、C 语言完整实现、复杂度分析一次讲透。你不需要任何算法基础只要会 C 语言的函数和数组就能跟着写完整个排序代码。代码部分我会给出可直接编译运行的完整版本同时讲解面试中常问的细节和优化点。1. 归并排序到底解决了一个什么问题如果只看结论归并排序是建立在“合并两个有序数组”这个基础操作之上的排序算法。这里先说一个核心判断归并排序的难点不在“排序”而在“合并”。排序本身是靠递归不断把问题变小真正干活的是合并两个已经有序的子数组。你只要把 merge 这个函数吃透了整个归并排序就通关了一大半。想想看如果给你两个已经排好序的数组A [1, 4, 7, 9] B [2, 3, 5, 8]你愿意不愿意把它们合并成一个有序的大数组这太简单了。两个数组从左往右各拿一个数出来比大小谁小谁先进新数组。这就是归并排序最基本的一步。但问题来了原始数组通常是乱序的[38, 27, 43, 3, 9, 82, 10]它根本没有两个现成的有序子数组可以合并。那怎么办归并排序的想法非常直接如果数组长度为 1它天然有序如果数组长度为 2比较一下就能排好如果更长就把它一分为二把左半边排好序把右半边排好序最后再把这两个有序半区合并起来。这里体现的正是分治策略分把一个大数组从中间切成两个子数组。治递归地对每个子数组再切分直到子数组只剩一个元素。合从最小的子数组开始两两合并出有序数组最终合并成完整的有序数组。这种思路相比冒泡排序有一个本质区别冒泡排序每一轮都盯着整个数组做交换而归并排序先把问题拆小再在小规模上解决最后合并答案。从实际编码角度讲归并排序也是一种你必须掌握的“模板型算法”。很多复杂问题比如求逆序对数量、链表排序、外部排序底层都用到了归并思想。学透归并排序不只是会写一个排序函数更是掌握一种解决规模问题的思维框架。2. 归并排序动画级理解从一棵递归树看全过程很多教材直接丢给你一段归并排序代码然后让你背。这样学效率很低。我们先把代码放在一边用图的方式把全过程走一遍。待排序数组下标 0 1 2 3 4 5 6 数值 38 27 43 3 9 82 10第一步拆分。我们把数组从中间一分为二左半区[38, 27, 43, 3] 右半区[9, 82, 10]注意这里并不真的创建新数组在 C 语言里是通过下标范围来划分逻辑区域的。继续拆分[38, 27, 43, 3] 拆成 [38, 27] 和 [43, 3] [9, 82, 10] 拆成 [9] 和 [82, 10]再继续拆[38, 27] 拆成 [38] 和 [27] [43, 3] 拆成 [43] 和 [3] [82, 10] 拆成 [82] 和 [10]到这里每个子数组的长度都是 1。长度为 1 的数组天然有序不用再拆了。第二步合并。现在从最底层开始两两合并。先看 [38] 和 [27]比较大小得到[27, 38]再看 [43] 和 [3]得到[3, 43]此时左半区的第二层变成了[27, 38] 和 [3, 43]继续合并这两个有序数组[3, 27, 38, 43]左半区排好了。再看右半区[9] 保持不变[82] 和 [10] 合并成 [10, 82]然后再合并[9, 10, 82]最后把左半区 [3, 27, 38, 43] 和右半区 [9, 10, 82] 合并得到完整有序数组[3, 9, 10, 27, 38, 43, 82]这就是归并排序的完整过程。拆的时候从大往小合的时候从小往大。拆到不能再拆就开始合并合并的结果总是有序的所以最终整个数组有序。这段过程对应的递归结构可以用下面这棵递归树来表示[38 27 43 3 9 82 10] / \ [38 27 43 3] [9 82 10] / \ / \ [38 27] [43 3] [9] [82 10] / \ / \ / \ [38] [27] [43] [3] [82] [10]你只要记住这棵树归并排序的大局观就有了。平时写递归卡住时就在草稿纸上画这棵树对照代码看当前递归到哪一层。3. 核心操作合并两个有序数组前面提到归并排序最关键的操作是合并两个有序数组。这一部分我们必须写清楚因为整个归并排序代码的核心就是这个 merge 函数。假设我们有数组 arr其中下标 left 到 mid 是有序的下标 mid1 到 right 也是有序的。我们的任务是把这两个区间合并成一个有序区间覆盖回原数组。C 语言实现如下// 文件路径merge_demo.c // 功能将 arr[left..mid] 和 arr[mid1..right] 合并为有序区间 #include stdio.h #include stdlib.h void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 mid - left 1; // 左半区长度 int n2 right - mid; // 右半区长度 // 创建临时数组存放两个半区 int *L (int *)malloc(n1 * sizeof(int)); int *R (int *)malloc(n2 * sizeof(int)); if (L NULL || R NULL) { printf(内存分配失败\n); exit(1); } // 拷贝数据到临时数组 for (i 0; i n1; i) { L[i] arr[left i]; } for (j 0; j n2; j) { R[j] arr[mid 1 j]; } // 合并临时数组回 arr[left..right] i 0; j 0; k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } // 如果左半区还有剩余直接拷贝 while (i n1) { arr[k] L[i]; i; k; } // 如果右半区还有剩余直接拷贝 while (j n2) { arr[k] R[j]; j; k; } free(L); free(R); }这段代码的逻辑非常清晰一共四步算出左右两个半区的长度申请临时数组。把原数组 left 到 mid 的数据拷到 L把 mid1 到 right 的数据拷到 R。用 i 和 j 分别指向 L 和 R 的起始位置比较 L[i] 和 R[j]把较小的放入原数组。当某个半区先遍历完另一个半区剩余元素直接按顺序放到后面。这里有一个容易忽略的细节为什么不直接用一个临时数组而要分成 L 和 R 两个临时数组因为合并的过程中原数组的位置会被覆盖。如果你直接把左边元素和右边元素同时存在原数组里而不借助额外空间前面存进去的值可能把还没比较的值覆盖掉。分成两个临时数组是为了保证比较的两个来源数据在合并过程中不被破坏。面试里也经常会问能不能做到空间复杂度 O(1) 的原址归并排序理论上有原地归并的写法但实现非常复杂而且常数因子很大实际工程中很少使用。标准归并排序的空间复杂度是 O(n)这点我们在后面复杂度分析里详细讲。4. 完整归并排序 C 语言实现有了 merge 函数归并排序本身只需要做两件事递归拆分然后调用 merge 合并。// 文件路径merge_sort.c // 功能完整归并排序实现含测试代码 #include stdio.h #include stdlib.h // 合并函数声明 void merge(int arr[], int left, int mid, int right); // 归并排序递归函数 void mergeSort(int arr[], int left, int right) { if (left right) { return; // 区间内只有一个元素或为空无需排序 } int mid left (right - left) / 2; // 防止整数溢出 // 递归排序左半部分 mergeSort(arr, left, mid); // 递归排序右半部分 mergeSort(arr, mid 1, right); // 合并两个有序部分 merge(arr, left, mid, right); } void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 mid - left 1; int n2 right - mid; int *L (int *)malloc(n1 * sizeof(int)); int *R (int *)malloc(n2 * sizeof(int)); if (L NULL || R NULL) { printf(内存分配失败\n); exit(1); } for (i 0; i n1; i) { L[i] arr[left i]; } for (j 0; j n2; j) { R[j] arr[mid 1 j]; } i 0; j 0; k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } while (i n1) { arr[k] L[i]; i; k; } while (j n2) { arr[k] R[j]; j; k; } free(L); free(R); } // 打印数组 void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } // 主函数测试 int main() { int arr[] {38, 27, 43, 3, 9, 82, 10}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); mergeSort(arr, 0, n - 1); printf(排序后); printArray(arr, n); return 0; }编译运行方式gcc merge_sort.c -o merge_sort ./merge_sort预期输出排序前38 27 43 3 9 82 10 排序后3 9 10 27 38 43 82这段代码有一个容易写错的地方mid 的计算。很多教材写int mid (left right) / 2;这在 left 和 right 都很大时可能溢出。写成int mid left (right - left) / 2;更安全。虽然在普通测试数据里看不出差别但面试官问起来时你能答出这一点会加分不少。还有一个细节递归出口的判断条件是if (left right)。为什么用 而不是 因为当区间为空时可能出现 left right 的情况。虽然正常递归里一般不会传入 left right 的区间但写成 更严谨也能防止意外情况导致死循环。5. 归并排序执行过程可视化用一个演示版代码看清每一步如果你只运行上面的代码看到的是排序前后的对比中间过程还是看不见。为了真正搞懂归并排序建议你在学习阶段加一点打印代码把每次 merge 前后的状态输出出来。// 文件路径merge_sort_debug.c // 功能归并排序过程可视化学习用 #include stdio.h #include stdlib.h void printRange(int arr[], int left, int right) { printf([); for (int i left; i right; i) { printf(%d, arr[i]); if (i right) { printf(, ); } } printf(]); } void merge(int arr[], int left, int mid, int right) { printf(合并区间 [%d..%d] 和 [%d..%d] 前, left, mid, mid 1, right); printf(左半区 ); printRange(arr, left, mid); printf( 右半区 ); printRange(arr, mid 1, right); printf(\n); int i, j, k; int n1 mid - left 1; int n2 right - mid; int *L (int *)malloc(n1 * sizeof(int)); int *R (int *)malloc(n2 * sizeof(int)); for (i 0; i n1; i) L[i] arr[left i]; for (j 0; j n2; j) R[j] arr[mid 1 j]; 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]; free(L); free(R); printf(合并后); printRange(arr, left, right); printf(\n\n); } void mergeSort(int arr[], int left, int right) { if (left right) { printf(区间 [%d..%d] 只有一个元素停止拆分\n, left, right); return; } int mid left (right - left) / 2; printf(拆分区间 [%d..%d]中间位置 mid%d\n, left, right, mid); mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } int main() { int arr[] {38, 27, 43, 3, 9, 82, 10}; int n sizeof(arr) / sizeof(arr[0]); printf(初始数组); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n\n); mergeSort(arr, 0, n - 1); printf(最终排序结果); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); return 0; }运行这个演示版你会看到类似下面的输出初始数组38 27 43 3 9 82 10 拆分区间 [0..6]中间位置 mid3 拆分区间 [0..3]中间位置 mid1 拆分区间 [0..1]中间位置 mid0 区间 [0..0] 只有一个元素停止拆分 区间 [1..1] 只有一个元素停止拆分 合并区间 [0..0] 和 [1..1] 前左半区 [38] 右半区 [27] 合并后[27, 38] 拆分区间 [2..3]中间位置 mid2 区间 [2..2] 只有一个元素停止拆分 区间 [3..3] 只有一个元素停止拆分 合并区间 [2..2] 和 [3..3] 前左半区 [43] 右半区 [3] 合并后[3, 43] 合并区间 [0..1] 和 [2..3] 前左半区 [27, 38] 右半区 [3, 43] 合并后[3, 27, 38, 43] 拆分区间 [4..6]中间位置 mid5 拆分区间 [4..4] 只有一个元素停止拆分 ...建议你自己跑一遍这个程序对照输出画递归树你会明显感觉到归并排序的执行过程在脑子里“活了”。看动画讲解视频也是同样的效果但自己运行代码印象更深。6. 时间复杂度与空间复杂度分析归并排序的时间复杂度非常稳定这是它最大的优点之一。6.1 时间复杂度O(n log n)分析归并排序的时间复杂度核心是看递归树的层数以及每一层合并不需要多少工作。假设数组长度为 n每次一分为二。递归树的层数大约为 log₂n。例如 n7递归深度大概是 3 层n1000深度大约是 10 层。每一层里所有合并操作加起来要处理的总元素数量是 n。虽然拆成了很多小区间但同一层内每个元素恰好参与一次合并。因此每一层的时间复杂度是 O(n)。总时间复杂度 层数 × 每层工作量 O(n log n)。这和冒泡排序、选择排序 O(n²) 相比在数据量较大时有明显优势。这里给个直观对比数据规模 n冒泡排序比较次数约(n²/2)归并排序比较次数约(n log₂n)1005000约 664100050万约 9966100005000万约 13万数据量越大差距越明显。当 n10000 时归并排序的工作量可能只有冒泡排序的三四百分之一。但要注意归并排序的时间复杂度不受初始数据顺序影响。这点和快速排序不同快速排序在数组已经有序时可能退化到 O(n²)而归并排序无论输入什么顺序递归结构完全一样因此时间复杂度始终是 O(n log n)。6.2 空间复杂度O(n)归并排序需要额外的临时数组来存放左右半区。在每一层递归中merge 函数会申请临时空间递归深度是 log n但同一时刻最大占用的临时空间是多少关键点虽然代码看起来在每层递归都会 malloc 空间但递归的执行是深度优先的。左半部分递归调用结束后空间先被释放才会进入右半部分递归。因此某一时刻同时存在的临时空间不是 n × log n而是 n 级别。所以归并排序的空间复杂度是 O(n)不是 O(n log n)。这一点面试中经常被问到很多人答错。如果想减少频繁 malloc/free 带来的开销可以考虑在递归函数外一次性申请一个与原数组等长的临时数组然后通过下标传进 merge 函数复用。这是工程上常用的优化方式。我们下面会给出这种优化写法。7. 归并排序优化版本复用临时数组递归过程中频繁 malloc 和 free 其实是不必要的而且有一定的性能开销。更好的做法是在调用归并排序之前一次性申请一个临时数组在整个排序过程中复用。下面是优化版的完整代码// 文件路径merge_sort_opt.c // 功能归并排序优化版复用临时数组减少内存分配开销 #include stdio.h #include stdlib.h #include string.h // 合并函数使用外部传入的临时数组 void merge(int arr[], int temp[], int left, int mid, int right) { int i left; // 左半区起始 int j mid 1; // 右半区起始 int k left; // 临时数组起始 // 比较并拷贝较小元素 while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } // 拷贝左半区剩余元素 while (i mid) { temp[k] arr[i]; } // 拷贝右半区剩余元素 while (j right) { temp[k] arr[j]; } // 将临时数组中的结果拷贝回原数组 for (i left; i right; i) { arr[i] temp[i]; } } // 归并排序递归函数 void mergeSortHelper(int arr[], int temp[], int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSortHelper(arr, temp, left, mid); mergeSortHelper(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); } // 对外接口只需要传入数组和长度 void mergeSort(int arr[], int n) { if (n 1) { return; } int *temp (int *)malloc(n * sizeof(int)); if (temp NULL) { printf(内存分配失败\n); exit(1); } mergeSortHelper(arr, temp, 0, n - 1); free(temp); } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {5, 2, 9, 1, 5, 6, 3, 8, 7, 4}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前); printArray(arr, n); mergeSort(arr, n); printf(排序后); printArray(arr, n); return 0; }这个版本的改动要点临时数组在 mergeSort 接口函数中申请只分配一次。merge 函数接收 temp 数组作为参数不再自行 malloc。对外只暴露 mergeSort(arr, n)调用者不需要关心 left 和 right 下标降低了使用门槛。这种设计比较贴近真实项目的工程习惯公共接口保持简洁内部细节封装起来同时兼顾性能。8. 归并排序 vs 快速排序到底选哪个排序算法里归并排序和快速排序经常被放在一起比较。很多初学者会问时间复杂度都是 O(n log n)它们有什么区别什么时候用哪个对比维度归并排序快速排序时间复杂度稳定 O(n log n)平均 O(n log n)最坏 O(n²)空间复杂度O(n)O(log n)递归栈理想情况下可做到 O(1) 额外辅助空间稳定性稳定排序不稳定适用场景链表排序、外部排序、数据量大的稳定排序数组排序、对空间敏感的场景归并排序的一个显著优势是稳定。所谓稳定是指如果数组里有两个相等的元素排序后它们的相对顺序不会改变。比如有一个对象数组需要先按姓名排序再按年龄排序稳定的排序算法可以保证第二次排序后年龄相同的人仍然保持姓名的顺序。另一个优势是归并排序对链表的支持极好。数组的归并排序需要 O(n) 额外空间但链表归并排序不需要这种额外空间只需要改变节点的 next 指针。这也是很多链表排序算法选择归并排序而不是快速排序的原因。快速排序的优势在于空间效率更高。快速排序是原址排序不需要额外的数组空间平均情况下表现非常优秀。虽然最坏情况是 O(n²)但通过随机选择基准值或三数取中法实际中几乎不会触发最坏情况。正因为快速排序的常数因子小、缓存友好大多数标准库里的排序实现都使用快速排序思想的变种。从学习角度讲我建议你两个都掌握。它们分别代表了分治策略的两种典型应用方向一个是“先拆后合合并是重点”归并排序一个是“先划分后递归划分是重点”快速排序。理解它们的区别你对分治思想的理解会上一个台阶。9. 归并排序常见问题与排查思路写归并排序的时候初学者容易遇到一些典型的错误。下面整理成表格你可以直接对照排查。问题现象可能原因排查方式解决方案程序运行后数组顺序没变递归调用写成了mergeSort(arr, left, mid - 1)或边界处理错误检查递归出口和 mid 的传递左半区应该是[left, mid]右半区应该是[mid1, right]不要漏掉中间元素排序结果中部分元素丢失或重复拷贝临时数组时循环边界写错检查 merge 里从临时数组拷回原数组的for循环是不是到i right考回时应该是for (i left; i right; i)程序崩溃segmentation fault数组下标越界通常是 mid 计算错误或者递归区间处理不对用 gdb 查看崩溃堆栈或打印 left、mid、right 的值检查递归出口是否用left rightmerge 中临时数组长度是否计算正确输出结果正确但 malloc 次数过多每次 merge 都申请临时数组统计 malloc 调用次数使用优化版在外部一次性申请临时数组并复用排序不稳定相等元素顺序改变merge 中使用了L[i] R[j]而不是检查比较条件希望稳定排序时应该写成L[i] R[j]这样相等时优先取左半区元素数组长度很大时程序变慢malloc 频繁调用导致开销大使用性能分析工具统计耗时改用复用临时数组的版本如果你遇到排序结果不对一个非常实用的调试方法先用一个长度为 5 以内的数组测试手动在纸上模拟一遍对比程序和你的模拟过程。归并排序的递归逻辑在小区间上很容易推演大多数问题都能在这个步骤里暴露出来。10. 归并排序的实际应用不只是面试题有些同学觉得归并排序只是考试和面试用的实际开发用不上。这个观点不够准确。归并排序的思想在几个真实场景中非常重要。第一个场景是外部排序。当数据量大到无法全部载入内存时比如对几十 GB 的文件排序归并排序是核心方案。做法是先把大文件切成多个能载入内存的小块对每个小块排序后写回磁盘然后对这些小块进行多路归并。外排序正是归并排序思想在大数据场景下的延伸。第二个场景是链表排序。Java 的 Collections.sort() 对对象列表的排序就用到了归并排序思想TimSort 是归并排序的优化版本。因为链表不支持随机访问快速排序在链表上实现麻烦而归并排序只需要改变指针就能完成。第三个场景是求逆序对数量。给定一个数组要求计算有多少对 (i, j) 满足 i j 且 arr[i] arr[j]。暴力解法是 O(n²)而利用归并排序的合并过程可以在 O(n log n) 时间内完成。原理是合并两个有序数组时如果左边数组的某个元素大于右边数组的某个元素那么左边数组该元素之后的所有元素也都大于右边这个元素可以一次性统计逆序对数量。// 文件路径inversion_count.c // 功能利用归并排序统计逆序对数量 #include stdio.h #include stdlib.h long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) { int i left; int j mid 1; int k left; long long inv_count 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { // arr[i] arr[j]说明 arr[i..mid] 都大于 arr[j] inv_count (mid - i 1); temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (i left; i right; i) { arr[i] temp[i]; } return inv_count; } long long mergeSortAndCount(int arr[], int temp[], int left, int right) { if (left right) { return 0; } int mid left (right - left) / 2; long long count 0; count mergeSortAndCount(arr, temp, left, mid); count mergeSortAndCount(arr, temp, mid 1, right); count mergeAndCount(arr, temp, left, mid, right); return count; } int main() { int arr[] {1, 20, 6, 4, 5}; int n sizeof(arr) / sizeof(arr[0]); int *temp (int *)malloc(n * sizeof(int)); long long result mergeSortAndCount(arr, temp, 0, n - 1); printf(逆序对数量%lld\n, result); free(temp); return 0; }这个例子很好地说明了理解归并排序的过程不只是会背代码更重要的是能在合并阶段捕捉到额外信息。你能从合并顺序里观察到哪些元素“跨过了”哪些元素从而快速统计出逆序对数量。11. 归并排序的稳定性和那些容易踩坑的细节归并排序是稳定排序这个结论只在实现正确时成立。关键点在于合并两个有序数组时遇到相等元素应该怎么办。正确写法if (L[i] R[j]) { arr[k] L[i]; i; }当 L[i] 和 R[j] 相等时我们优先取左半区的元素。由于左半区在原数组中本来就在右半区前面取出后放进新数组也保持了这个相对顺序所以稳定性成立。如果误写成而不是相等的元素会优先取右半区相对顺序就颠倒了稳定排序的性质被破坏。另外归并排序的递归深度是 log n 级别对于长度为 10 万的数组递归深度大约是 17 层不会导致栈溢出。但如果数组长度达到百万、千万级别递归深度也只是 20 到 30 层仍然可以接受。真正消耗内存的是临时数组的空间这和使用递归还是迭代无关。如果面试官问你归并排序能否改成非递归写法答案是可以的。思路是引入一个 width 变量从 1 开始翻倍每次对相邻的 width 长度子数组进行合并直到整个数组被合并完成。这种方式也叫自底向上的归并排序避免了递归调用代码上需要多处理一下数组长度不是 2 的幂的情况。12. 推荐文章总结与学习路径建议现在我们可以把归并排序的学习路径梳理成一条清晰的路线第一步画递归树。拿一个小数组手动模拟拆分和合并的过程直到你能不看任何参考资料独立画出每一层的状态。第二步先写 merge 函数。单独构造两个有序数组验证你的合并代码能否得到正确结果。这一步能通过归并排序就完成了一半。第三步实现完整的递归调用。注意 mid 的计算方法、递归边界条件、左右区间的划分。第四步运行演示版代码观察程序输出与你自己手动模拟的结果是否一致。第五步再想三个问题为什么复杂度是 O(n log n)为什么空间复杂度是 O(n)为什么相等元素要用而不是把这些步骤做完你对归并排序的理解就能超过大多数背书式学习者。后面学快速排序时你也能更清晰地意识到两种分治实现的差异。归并排序不是那种“看一眼就会”的算法它的价值恰恰在于它训练的是递归思维和分治思维。这两项能力在二叉树、堆排序、线段树、动态规划等很多后续主题里都会被反复使用。建议先收藏这篇文章在电脑上打开代码编辑器把每一段代码亲手敲一遍再对照过程可视化输出加深理解。代码和思路都在这里了剩下的就是动手实践。