小探险家学算法

Appearance

17. 分而治之（归并排序） ​

知识点：归并排序 —— 分：拆成两半；治：合并两个有序队伍（O(n log n)，稳定）

项目：合并两支合唱队 + 给成绩单"稳排"

故事开场：两支排好的队伍 ​

合唱比赛，一班和二班各排练了一支合唱队。老师宣布：

"今天，两支队伍合并成一支大队伍！要求：从矮到高站好。"

一班队伍已经按身高排好了：[152, 158, 165, 170] 二班队伍也排好了：[150, 156, 168, 175]

老师问："谁有办法最快合成一支有序的队伍？"

你举手说："直接把两队的名单倒在一起，然后重新排一遍！" ——说完你自己也觉得不对劲：两队都已经排好了，重新排一遍， 前面排好的功夫不是白费了吗？

笨办法先行：重新排，浪费了 ​

你试了试"倒在一起重排"：

ts
const teamA = [152, 158, 165, 170]
const teamB = [150, 156, 168, 175]

const all = teamA.concat(teamB)   // 倒在一起
quickSort(all)                    // 重新排一遍
console.log(all)

输出：

[150, 152, 156, 158, 165, 168, 170, 175]

排对了，可是你盯着代码想：这两个队明明都排好了啊！

最小的两个人是谁？"一班队首 152，二班队首 150"——全场最小的， 一定是两个队首之一！（因为两个队各自都是队首最小！）

那么第二小的呢？把最小的 150 拿出来后，二班的队首变成 156， 新的两个队首是 152 和 156——第二小的就是 152……

你眼睛亮了：根本不用重新排！每次只看两个队首，谁小谁出来，一会儿就合成一支有序的队伍了！

引出知识点：归并——"治"的两队合一 ​

"看两个队首，谁小谁先进"这个动作，有个名字，叫归并（merge）：

一班队首：152 → 158 → 165 → 170
二班队首：150 → 156 → 168 → 175

比队首：150 出列（二班）→ 152 出列（一班）→ 156（二班）→ 158（一班）
→ 165（一班）→ 168（二班）→ 170（一班）→ 175（二班）
结果：[150, 152, 156, 158, 165, 168, 170, 175]

每个数只被"看"一次——合并两个长度各 n 的队伍，只要 2n 次比较， 这就是 O(n)。排好的数据合并起来，快得飞起。

那如果数据是乱的，没有"两个排好的队"怎么办？——那就自己造两个！ 把乱数组从中间劈成两半，递归地把每一半排好（劈到只有一个数时， 它天然就是"排好的队"），再归并起来。这就是归并排序：

分（divide）：把数组从中间劈成两半 治（conquer）：递归排好每一半，再归并成有序的整体

"分而治之"——把大问题拆成小问题，小问题解决了，大问题自然解决。

动手实现：归并排序 ​

先写"合并两个有序队伍"：

ts
// 归并：合并两个排好序的数组
function merge(a: number[], b: number[]): number[] {
  const result: number[] = []
  let i = 0                    // a 的队首指针
  let j = 0                    // b 的队首指针

  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) {
      result.push(a[i])        // a 的队首小，出列
      i++
    } else {
      result.push(b[j])        // b 的队首小，出列
      j++
    }
  }

  // 有一队先走完了，剩下的整队接上
  while (i < a.length) {
    result.push(a[i])
    i++
  }
  while (j < b.length) {
    result.push(b[j])
    j++
  }

  return result
}

// 用两队验证
const teamA = [152, 158, 165, 170]
const teamB = [150, 156, 168, 175]
console.log(merge(teamA, teamB))

输出：

[150, 152, 156, 158, 165, 168, 170, 175]

然后，套上"分"的递归：

ts
// 归并排序
function mergeSort(list: number[]): number[] {
  if (list.length <= 1) {
    return list                // 出口：0 个或 1 个数，天然有序
  }

  const mid = Math.floor(list.length / 2)
  const left = mergeSort(list.slice(0, mid))     // 分：左半边（递归排）
  const right = mergeSort(list.slice(mid))       // 分：右半边（递归排）

  return merge(left, right)                      // 治：合并两半
}

const scores = [78, 92, 65, 88, 70]
console.log(mergeSort(scores))

输出：

[65, 70, 78, 88, 92]

（slice(0, mid) 是"切出数组的一段"：slice(从哪开始, 到哪结束)， slice(mid) 是"从 mid 切到结尾"。）

跑起来：快排 vs 归并，谁更稳？ ​

把归并排序加进第 16 章的计时比赛：

ts
// 造 2 万个随机成绩
const bigList: number[] = []
for (let i = 0; i < 20000; i++) {
  bigList.push(Math.floor(Math.random() * 100))
}

console.time("快速排序")
quickSort(bigList.slice())
console.timeEnd("快速排序")

console.time("归并排序")
mergeSort(bigList.slice())
console.timeEnd("归并排序")

在我这台电脑上，输出（数字可能不一样）：

快速排序: 约 40ms
归并排序: 约 6ms

咦，归并排序还快一些！这是因为我们第 16 章的快速排序是简单教学版—— 每次分区都新建两个数组（smaller、bigger），最后还要拼接，比较费功夫。 真正的快排是"原地交换"，会快得多。

但不管怎样，两个都是 O(n log n)——比冒泡（O(n²)）快一个数量级。 这一轮，它们打了个平手。不过归并排序有个快排没有的"稳"：

快速排序归并排序
平均速度O(n log n)O(n log n)
最坏情况O(n²)（坏运气：每次都分不均匀）O(n log n)（永远分均匀！）
内存原地交换（省内存）要造新数组（费内存）
稳定性不稳定（相等的数可能换位）稳定（相等的数保持原顺序）

归并排序不怕坏运气：不管数据原本长什么样，它都是"从中间劈开"， 永远分得均匀。快排赌运气，归并靠实力。

一个小秘密：合并两个排好的队伍这件事（merge），在现实程序里 到处都在用——数据库把两个排好序的表拼起来、Git 合并代码分支…… "谁小谁先进"是一个价值连城的动作。

小挑战 ​

  1. 数一数：给 merge 加一个计数器，数一数合并两支 4 人队伍 比较了几次。最坏情况是多少次？（提示：两队各 n 人， 最坏比较 2n−1 次。）
  2. 反着排：把归并排序改成从大到小（提示：改 merge 里的 一个符号）。
  3. 字符串版：和快排一样，把 mergeSort 改成字符串数组版， 用第 11 章的名单 ["小丽", "小刚", "小明", "小红", "小雨"] 排序， 验证输出顺序。

课后练习 ​

第 1 题（动手题）：手动归并 ​

纸上手动合并 [2, 5, 9] 和 [1, 3, 4, 8]，写出每一步"谁出列"， 最后用程序验证。

参考答案（点开查看）
  • 2 vs 1 → 1 出列（二队）
  • 2 vs 3 → 2 出列（一队）
  • 5 vs 3 → 3 出列
  • 5 vs 4 → 4 出列
  • 5 vs 8 → 5 出列
  • 9 vs 8 → 8 出列
  • 一队剩 9，整队接上

结果：[1, 2, 3, 4, 5, 8, 9]。一共比较了 6 次。

第 2 题（思考题）：为什么归并不怕坏运气？ ​

快排的坏运气是"每次都分不均匀"。归并排序永远从中间劈开—— 从中间劈，最坏能劈出什么比例？这样劈，要劈几层才能劈到底？

参考答案（点开查看）

从中间劈，两半永远差不多一样大（差最多 1 个）——没有"不均匀"这回事。

劈的层数：n → n/2 → n/4 → … → 1，固定 log n 层（和第 1 章 "能被除以 2 多少次"一样）。每层处理 n 个数，总共 n log n， 任何输入都一样，所以最坏情况也是 O(n log n)。

快排靠"运气"（平均 O(n log n)），归并靠"设计"（永远 O(n log n)）。

第 3 题（思考题）：分而治之 ​

"分而治之"——把大问题拆成小问题，解决小问题，再合并成大问题的答案。 除了归并排序，你还见过哪些"分而治之"？提示：想想汉诺塔、 快排、文件夹树、二分查找……

参考答案（点开查看）
  • 汉诺塔：移 n 个盘子 = 移 n−1 个 + 移 1 个 + 移 n−1 个
  • 快排：分成小堆、大堆，各自递归排
  • 文件夹树：打印文件夹 = 打印自己 + 递归打印每个子文件夹
  • 二分查找：每次排除一半（它只"分"不"治"，因为只在一半里找）
  • 爬楼梯：f(n) = f(n−1) + f(n−2)

"分而治之"是计算机科学最常用的思路之一。凡是问题里能看到 "小一号的自己"，都可以想想：能不能拆成两半，分别解决，再合起来？

下一课预告：快排、归并都靠"比较"。可老师突然说："投票统计！ 全班 50 人投票，每人投 1~10 星。谁是最快的排序？" 票数只有 10 种——数一数每种票有几张，不就知道结果了吗？ 不需要比较的排序，登场！