22. 大问题变小问题（分治）

知识点：分治（divide and conquer）—— 快速选择：只拆一边的分治（平均 O(n)）

项目：不排完全队，直接找出"第 3 名"

---

故事开场：老师只要"第 3 名"

期中考试，老师宣布："这次只公布第 3 名！大家猜猜是谁？"

你想用程序算出来。成绩单是乱序的：

const scores = [78, 92, 65, 88, 70]

"第 3 名 = 从高到低排第 3 = 从低到高排第 3。"你自言自语， "那先排个序，再拿第 3 个不就得了？"

const sorted = quickSort(scores)     // 把 5 个成绩全排好
console.log("第 3 名：" + sorted[sorted.length - 3])

输出：

第 3 名：78

算对了！可你盯着 quickSort 想：为了一个第 3 名，把 5 个成绩全排了—— 全班 50 人还好，全校 5000 人呢？为了"第 3 名"，把 5000 个成绩 全排一遍（O(n log n)）……是不是太浪费了？

老师神秘一笑："你忘了快排的'分区'了吗？"

---

笨办法先行：分区完，基准的位置就"定死了"

回忆第 16 章快排的分区：选一个基准，比它小的站左边，比它大的站右边。 分区完之后，基准站的位置，就是它最终的位置——永远不用再动！

[78, 92, 65, 88, 70]   选 70 当基准
         ↓
[65]  70  [78, 92, 88]
 ↑     ↑       ↑
小的   基准    大的

你看，70 已经站在"第 2 小"的位置上了（它左边只有 1 个数）！

那么，"第 3 小"在哪里？——在右边那堆里！ 而且我们根本不用管左边——第 3 小不可能在只有 1 个数的左边。

"我只需要排'右边'那一堆？"你眼睛亮了，"那左边那堆不是白排了吗！"

---

引出知识点：快速选择——只拆一边的分治

这就是快速选择（quick select）：和快排一样分区，但只递归一边。

每次分区后，基准的位置就定死了，分三种情况：

1. 基准正好是第 k 小 → 直接返回它，完事！
2. 第 k 小在左边 → 只去左边继续找
3. 第 k 小在右边 → 只去右边继续找，而且 k 要"缩水"（右边第 1 小 是全局第 smaller.length + 2 小）

快排要把两半都排（分而治之，两边都治），快速选择只治一边 ——这叫"分而治之的懒人版"：拆还是要拆，但只拆有用的那半边。

为什么快？ 快排每层处理 n 个数，一共 log n 层，O(n log n)； 快速选择每层也只处理 n 个数左右，但只走一条路——n + n/2 + n/4 + … ≈ 2n， 平均 O(n)！找一个数，不用排完全队。

---

动手实现：快速选择

// 快速选择：找第 k 小的数（k 从 1 开始数）
function quickSelect(list: number[], k: number): number {
  if (list.length === 1) {
    return list[0]              // 出口：只剩一个，就是它
  }

  const pivot = list[list.length - 1]    // 选基准（最后一个）
  const smaller: number[] = []           // 比基准小的
  const bigger: number[] = []            // 比基准大的

  for (let i = 0; i < list.length - 1; i++) {
    if (list[i] <= pivot) {
      smaller.push(list[i])
    } else {
      bigger.push(list[i])
    }
  }

  if (k === smaller.length + 1) {
    return pivot                // 基准正好是第 k 小！
  }
  if (k <= smaller.length) {
    return quickSelect(smaller, k)       // 第 k 小在左边
  }
  return quickSelect(bigger, k - smaller.length - 1)   // 在右边，k 缩水
}

const scores = [78, 92, 65, 88, 70]
console.log("第 1 小：" + quickSelect(scores, 1))   // 65
console.log("第 2 小：" + quickSelect(scores, 2))   // 70
console.log("第 3 小：" + quickSelect(scores, 3))   // 78

输出：

第 1 小：65
第 2 小：70
第 3 小：78

（"第 3 名"是从高到低排第 3，也就是从低到高排第 3—— 两个方向数，都是第 3 个！所以 quickSelect(scores, 3) 就是第 3 名。）

---

跑起来：只找，不排完

第 3 名 = 从高到低第 3 = 从低到高第 3 小。那"第 500 名"呢？

// 全校 5000 人的成绩（0~100 随机）
const allScores: number[] = []
for (let i = 0; i < 5000; i++) {
  allScores.push(Math.floor(Math.random() * 101))
}

console.time("排序后取第 500 名")
const sortedAll = quickSort(allScores)      // 全排
const rank500 = sortedAll[5000 - 500]       // 从高到低第 500
console.timeEnd("排序后取第 500 名")

console.time("快速选择直接找")
const quick500 = quickSelect(allScores, 4501)   // 第 500 大 = 第 4501 小
console.timeEnd("快速选择直接找")

console.log("排序法：" + rank500 + "，选择法：" + quick500)

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

排序后取第 500 名: 约 8ms
快速选择直接找: 约 1ms

（5000 个数太小，差距不明显。把 5000 改成 50 万再试一次： 排序法要排 50 万个（约 320ms），快速选择只处理大约 2×50 万个中 的一部分（约 20ms）——数据越大，差距越明显：一个要全排， 一个只找一半。）

快速选择 = 快排的"只问一半"版。 这就是分治思想的妙处： 问题拆开之后，不用全部解决，只解决需要的那一半。

---

小挑战

1. 找最大 / 找最小：用 quickSelect 找数组里的最大值和最小值 （提示：最小值是第 1 小，最大值是第 n 小）。
2. 第 k 大：写一个函数 quickSelectBig(list, k) 找第 k 大的数 （提示：第 k 大 = 第 (length − k + 1) 小，或者把分区的 "小/大"方向换过来）。
3. 思考题：大整数乘法——两个 3 位数相乘，竖式要做 3×3=9 次 个位数乘法。如果把每个数拆成"高半 + 低半"，能不能少做几次 乘法？（提示：这就是著名的 Karatsuba 算法，它把 4 次乘法 变成 3 次——网上查一查，很有意思！）

---

课后练习

第 1 题（动手题）：找中位数

"中位数"是排好序后正中间那个数（奇数个数时）。用 quickSelect 找 [42, 17, 88, 56, 33, 71, 25] 的中位数，并用 quickSort 验证。

参考答案（点开查看）

7 个数的中位数是排好序后第 4 个（正中间）：

const nums = [42, 17, 88, 56, 33, 71, 25]
console.log(quickSelect(nums, 4))          // 42
console.log(quickSort(nums)[3])            // 42（验证：排序后第 4 个）

排好序是 [17, 25, 33, 42, 56, 71, 88]，第 4 个（下标 3）是 42。 两个方法答案一致 ✅

找中位数是快速选择最著名的用途——不用全排，直接"挖"出中间那个。

第 2 题（思考题）：快速选择为什么是 O(n)？

快速选择每层处理大约 n 个数，但只递归一边。数一数它一共要处理 多少个数：n + n/2 + n/4 + …… 加起来大约是多少？

参考答案（点开查看）

n + n/2 + n/4 + n/8 + …… 这个"越来越小"的数列，加起来永远不会 超过 2n（想想：1 + 1/2 + 1/4 + 1/8 + … = 2）。

所以快速选择平均大约处理 2n 个数——O(n)！

快排每层都是 n，一共 log n 层（n log n）；快速选择每层也是 n， 但只有 log n 层中的一条路（n + n/2 + n/4 + … ≈ 2n）。 "只走一条路"，就是它快的秘密。

第 3 题（思考题）：三种分治

二分查找、快速选择、归并排序都是"分治"。它们的"分"和"治"有什么不同？ 填一填：

算法	拆成几半	每一半都解决吗？	需要合并吗？
二分查找	2 半	？	？
快速选择	2 半	？	？
归并排序	2 半	？	？

参考答案（点开查看）

算法	拆成几半	每一半都解决吗？	需要合并吗？
二分查找	2 半	只去一半（数据有序）	不需要
快速选择	2 半	只去一半（位置定死）	不需要
归并排序	2 半	两半都解决	需要（合并）

规律：只找"一个答案"的（二分、选择），只去一半，不用合并； 要"全部排好"的（归并），两半都去，还得合并。

分治三兄弟，各怀绝技，但核心思想只有一个：大问题变小问题， 小问题变没有问题。

---

下一课预告：迷宫的入口和出口只隔着一堵墙，可你就是找不到路。 你决定：走一步试试，不行就退回来换一条路——退回来，叫"回溯"。 它能让程序像聪明的探险家一样，把每一条路都试一遍，绝不迷路。