# 认识“分治”思想

30 秒速记

  • 分治三步:拆成同类小问题 → 分别解决 → 合并结果
  • 递归要有基线(比如长度 ≤ 1 直接返回),每次拆分规模必须严格变小
  • 合并是关键,只拆不合等于没做
  • 归并排序:拆分简单、合并费力;快速排序:拆分(分区)费力、合并不用做
  • 递归太深可以改成自底向上迭代,分治思想不变

分治就是把大问题拆成几个同样结构的小问题,各自解决,再把结果合起来。 好比一个班的试卷让一个人改太慢,拆给四个组各改一摞,最后汇总分数。排序里的两个经典例子:归并排序拆分很简单,从中间切开就行,力气花在合并上;快速排序正好反过来,力气花在分区上,分完左右各自排好就天然有序,不用合并。写递归时我会先确认两件事:基线是什么,每次拆分规模是不是一定变小。

本节我们要学习的两个排序算法都是对“分治”思想的应用。 “分治”,分而治之。其思想就是将一个大问题分解为若干个子问题,针对子问题分别求解后,再将子问题的解整合为大问题的解。

利用分治思想解决问题,我们一般分三步走:

  • 分解子问题
  • 求解每个子问题
  • 合并子问题的解,得出大问题的解

下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。

面试官追问

追问 1数组切两半,各自排好后直接拼起来,算分治吗?
参考回答

不算完整的分治,少了合并。[3, 4] 和 [1, 2] 各自有序,直接拼是 [3, 4, 1, 2],还是乱的,得用双指针合并。

追问 2写一个分治排序的递归函数,入参、返回值和终止条件怎么定?
参考回答

入参是数组或 [lo, hi) 区间,返回有序结果,长度 ≤ 1 直接返回。区间开闭全程统一用左闭右开,切分点 mid = (lo + hi) >> 1,不会漏也不会重叠。

追问 3数据太大,递归太深栈溢出,要放弃分治吗?
参考回答

不用,换实现方式就行。归并可以写成自底向上:先两两合并长度 1 的段,再合并长度 2 的,以此类推。其实归并递归深度只有 log n,100 万条才 20 层,真栈溢出多半是切分写错导致不收敛。

追问 4线上排序结果偶尔少元素,叶子节点都没问题,先查哪?
参考回答

查合并。最常见的是一侧耗尽后忘了把另一侧剩余部分接上。加个断言:合并结果长度等于左右长度之和。

追问 5快排和归并都是分治,区别在哪?
参考回答

归并先拆后合,排序发生在合并阶段,稳定、时间稳定 O(n log n),但要 O(n) 辅助空间。快排先分区再递归,原地排,平均 O(n log n),最坏 O(n²),不稳定。

# 归并排序

30 秒速记

  • 一直对半切到单个元素,再两两用双指针合并成有序段
  • 递归只负责拆,真正的排序发生在合并
  • 每层合并处理 n 个元素,共 log n 层 → 稳定 O(n log n),不分好坏情况
  • 数组版要 O(n) 辅助空间;相等时先取左边才稳定(<= 而不是 <)
  • 适合链表排序、外部排序、要求稳定的场景

归并排序就是先把数组一直对半切到只剩一个元素,再两两合并,合并时用双指针保证每次合出来都是有序的。 单个元素天然有序,所以整件事就变成了反复合并两个有序数组,这一步是线性的。一共 log n 层,每层合并所有 n 个元素,所以不管输入什么样都是 O(n log n),这是它比快排稳的地方。代价是数组版要 O(n) 的额外空间。合并时两边相等要先取左边,写成 <=,不然就不稳定了。

回答参考:“归并的核心是两个有序段线性合并。递归只负责划分,真正的排序发生在合并阶段。”

面试官追问

追问 1有人说递归返回时数组自然就有序了,错在哪?
参考回答

递归只是把数组拆小再拿回两个有序段,真正让整体有序的是合并那一步。去掉合并直接拼接,跨段的元素还是乱的。

追问 2合并两个有序数组,代码怎么写才好检查?
参考回答

两个指针各指一边,每次取较小的放进结果,谁被取了谁的指针往后走。一边耗尽后把另一边剩下的 concat 上去。最后断言结果长度等于两边之和。

追问 3换成链表排序,归并有什么不一样?
参考回答

合并直接改 next 指针,不需要额外数组,空间降到 O(log n)(递归栈)。找中点用快慢指针,切开时记得把前半段尾节点的 next 置 null,不然会成环。

追问 4文件太大内存装不下,怎么用归并排?
参考回答

外部排序:先切成能装进内存的块,每块内部排好写回磁盘,再同时打开这些有序块做多路归并,每路只读当前最小值。多路归并时用一个小顶堆挑最小值。

追问 5为什么 V8 的 sort 用 TimSort 而不是快排?
参考回答

TimSort 是归并加插入的混合,稳定,而且对部分有序的数据很快,真实业务数据大多是这样。V8 从 7.0 起换成它,ES2019 也把 sort 稳定写进了规范,之前的快排版本对长数组是不稳定的。

# 思路分析

30 秒速记

  • 分解:从中间切两半,一直切到每段只有一个元素
  • 求解 + 合并:单元素天然有序,两两合并成更大的有序段
  • 合并时结果前缀一直有序,装的是两边已消费的最小元素
  • 一侧耗尽后另一侧剩余直接接上,它本身有序
  • 切分必须让规模严格变小,mid = Math.floor(len / 2) 对 len ≥ 2 两边都非空

归并排序把分治三步填得很具体:从中间切两半一直切到单元素,然后从最小的段开始两两合并,合到原长度就排完了。 单元素不用排,所以排序问题就变成了「合并两个有序数组」,这个用双指针一遍就能搞定。合并过程中,结果数组里放进去的部分一直是有序的,因为每次都取两边当前最小的。最后一定要把没取完的那一侧接上,这是最常见的漏写点。

function merge(a, b) {
  const res = []
  let i = 0, j = 0
  while (i < a.length && j < b.length) {
    res.push(a[i] <= b[j] ? a[i++] : b[j++]) // <= 保证稳定
  }
  return res.concat(a.slice(i), b.slice(j)) // 剩余部分直接接上
}
merge([3, 7], [1, 5, 9]) // [1, 3, 5, 7, 9]
@前端进阶之旅: 代码已经复制到剪贴板

归并排序是对分治思想的典型应用,它按照如下的思路对分治思想“三步走”的框架进行了填充:

  • 分解子问题:将需要被排序的数组从中间分割为两半,然后再将分割出来的每个子数组各分割为两半,重复以上操作,直到单个子数组只有一个元素为止。
  • 求解每个子问题:从粒度最小的子数组开始,两两合并、确保每次合并出来的数组都是有序的。(这里的“子问题”指的就是对每个子数组进行排序)。 合并子问题的解,得出大问题的解:当数组被合并至原有的规模时,就得到了一个完全排序的数组

面试官追问

追问 1基线改成切到空数组才停,会出什么事?
参考回答

长度为 1 时 mid = 0,切出来左边空、右边还是长度 1,右边永远切不小,无限递归直到栈溢出。基线要写 len <= 1。

追问 2怎么证明合并没漏元素?
参考回答

循环结束时至少有一边耗尽,另一边剩下的必须全部接上。再加断言 res.length === a.length + b.length,漏了马上能发现。

追问 3要求相等记录保持原顺序,合并时怎么比?
参考回答

相等时取左边,用 a[i] <= b[j]。左段的元素在原数组里本来就靠前,每一层都这么取,整体就稳定。教程里的代码用的是 <,相等时先取右边,结果数值对但不稳定。

追问 4长度正常但局部逆序,单元素和两元素用例都过了,怎么查?
参考回答

每层打印左右输入和合并输出。输入就无序,问题在更深一层;输入有序、输出乱了,就查比较方向和指针推进。

追问 5左右排好后,比一下 left 最后一个和 right 第一个,能省掉合并吗?
参考回答

能,left[left.length - 1] <= right[0] 时直接拼接就行,这是个常见优化,对有序输入能明显提速。但一般情况还是得合并,它只是个快速通道。

# 真实排序过程演示

30 秒速记

  • [8,7,6,5,4,3,2,1] 切三次到单元素:8 → 4 → 2 → 1
  • 合并三次:[7,8 | 5,6 | 3,4 | 1,2] → [5,6,7,8 | 1,2,3,4] → [1..8]
  • mergeSort 递归拆分:len <= 1 返回,slice(0, mid) 和 slice(mid) 各自递归
  • mergeArr 双指针合并,一侧耗尽后 concat 另一侧剩余
  • 比较写 arr1[i] < arr2[j] 相等时先取右边,不稳定,要稳定写 <=;每层 slice 会产生新数组,总空间 O(n)

这个例子把归并的过程摊得很清楚:8 个元素切三次到单元素,再合并三次回到 8 个,正好对应 log 8 = 3 层。 代码分两块,mergeSort 负责拆,到长度 ≤ 1 就返回;mergeArr 负责合并两个有序数组,用双指针一边取较小的,一边耗尽就把另一边剩下的接上。有个细节:比较写成 arr1[i] < arr2[j] 的话,相等时会先取右边,数值没问题但不稳定,要保稳定就写 <=。

下面我们基于归并排序的思路,尝试对以下数组进行排序:

[8, 7, 6, 5, 4, 3, 2, 1]
@前端进阶之旅: 代码已经复制到剪贴板
  • 首先重复地分割数组,整个分割过程如下:
  • 首次分割,将数组整个对半分:
[8, 7, 6, 5,| 4, 3, 2, 1]
@前端进阶之旅: 代码已经复制到剪贴板

二次分割,将分割出的左右两个子数组各自对半分:

[8, 7,| 6, 5,| 4, 3,| 2, 1]
@前端进阶之旅: 代码已经复制到剪贴板