小探险家学算法

Appearance

12. 泡泡排队（冒泡排序） ​

知识点：冒泡排序 —— 相邻两个比较，大的往后飘（O(n²)）

项目：给乱糟糟的成绩单排队

故事开场：成绩单乱成一锅粥 ​

期中考试结束了。老师抱着一摞成绩单走进教室，皱着眉头：

"我把成绩单按学号排好了，可大家要看的是按分数从高到低！"

你自告奋勇："我来排！"

你盯着成绩单看了半天：78、92、65、88、70…… 要从高到低排， 怎么排？你的第一个念头是：两个人比一比，谁矮谁往后站—— 不对，是谁分低谁往后排。

于是你想到了一个"笨但自然"的办法：从头到尾，把相邻的两个分数比一比， 前面的比后面小，就换一下位置。把 78 和 92 比——78 小，换！

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

// 交换数组里第 a 位和第 b 位的两个数
function swap(list: number[], a: number, b: number): void {
  const temp = list[a]     // 先把 a 位的数"端在手里"
  list[a] = list[b]        // 再把 b 位的数放进 a 位
  list[b] = temp           // 最后把手里的数放进 b 位
}

// 相邻比较：比一遍
for (let i = 0; i < scores.length - 1; i++) {
  if (scores[i] < scores[i + 1]) {
    swap(scores, i, i + 1)
  }
}
console.log(scores)

跑一下，结果：

[92, 78, 88, 70, 65]

咦，还是乱着的！92 跑到最前面了，但 78、88、70、65 还是乱序。

你盯着数组看："我的办法有问题？……不对，好像只排了一半！"

笨办法先行：一趟只冒一个泡 ​

想明白刚才发生了什么，我们把这一趟"相邻比较"走一遍：

[78, 92, 65, 88, 70]
 78 vs 92：78 小，换 → [92, 78, 65, 88, 70]
      78 vs 65：78 大，不换 → [92, 78, 65, 88, 70]
          65 vs 88：65 小，换 → [92, 78, 88, 65, 70]
               65 vs 70：65 小，换 → [92, 78, 88, 70, 65]

发现规律了吗？最小的 65，一路被"冒"到了最后面！ 因为每一次比较，都是"小的往后换"——65 每碰到一个比它大的， 就被换到更后面。一趟下来，最小的那个数，一定沉到了数组的最后。

（就像水里的气泡：重的往下沉，轻的往上冒——所以这个办法叫 冒泡排序。虽然这里是"最轻的沉底"，方向反了，但道理一样： 每一趟，都有一个数"飘"到它该去的位置。）

所以问题清楚了：一趟只保证一个数归位。5 个数，要排好， 需要 4 趟（最后剩一个时它自己就是对的）。

引出知识点：冒泡排序——多来几趟 ​

把刚才那一趟"重复 4 次"，每次少管一个已经归位的：

ts
function bubbleSort(list: number[]): void {
  // 一共要排 n-1 趟（最后一个不用排）
  for (let round = 0; round < list.length - 1; round++) {
    // 每一趟：从第 0 个比到"还没归位"的最后一个
    // 已经归位的是最后 round 个，不用再比
    for (let i = 0; i < list.length - 1 - round; i++) {
      if (list[i] < list[i + 1]) {        // 从高到低排
        swap(list, i, i + 1)              // 前面的小？换！
      }
    }
  }
}

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

输出：

[92, 88, 78, 70, 65]

排好了！从高到低，整整齐齐。

为什么内层循环要 - round？ 因为每一趟结束，末尾就多一个 已经归位的数（第一趟后 65 归位，第二趟后 70 归位……）。 已经归位的不用再比，所以每趟少比一个——内层就减去 round。

为什么外层是 n - 1 趟？ 5 个数，4 趟就够了： 每一趟归位一个，4 趟归位 4 个，最后一个自己待着也是对的。

跑起来：数一数，冒泡有多累？ ​

排序要"做多少次比较"，我们来数一数。给 bubbleSort 装个计数器：

ts
let compareCount = 0

function bubbleSortCount(list: number[]): void {
  for (let round = 0; round < list.length - 1; round++) {
    for (let i = 0; i < list.length - 1 - round; i++) {
      compareCount++                       // 比了一次！
      if (list[i] < list[i + 1]) {
        swap(list, i, i + 1)
      }
    }
  }
}

const test = [78, 92, 65, 88, 70]
bubbleSortCount(test)
console.log("排 5 个数，比较了 " + compareCount + " 次")

输出：

排 5 个数，比较了 10 次

5 个数比较 10 次：4 + 3 + 2 + 1 = 10。n 个数，比较 (n-1) + (n-2) + ... + 1 次，大约等于 n × n ÷ 2 次—— 这就是第 1 章见过的 O(n²)！

O(n²) 的意思：数据翻 10 倍，比较次数翻 100 倍。 排 10 个数约 45 次，排 100 个数约 4950 次，排 1000 个数约 50 万次， 排 10 万个数…… 50 亿次，电脑也得喘口气。

冒泡排序胜在简单直观——它是最容易想出来的排序办法。 但 O(n²) 让它在数据一大时就力不从心。接下来的两章， 我们会看到两个"不那么笨"的排序，它们比冒泡少做不少事。

小挑战 ​

  1. 换个方向：把程序改成从低到高排（最小分在最前面）—— 改一行就行，想想是改哪一行。
  2. 提前下班：如果某一趟一次交换都没发生，说明已经排好了， 可以提前结束（提示：用一个"这趟换没换"的标记变量， 没换就 break）。这就是冒泡排序的"优化版"。
  3. 数交换：给 bubbleSort 再加一个计数器，数一数一共 交换了几次。比较次数和交换次数一样吗？为什么？

课后练习 ​

第 1 题（动手题）：倒着冒泡 ​

按"从低到高"（分数从低到高排）重写 bubbleSort， 用 [78, 92, 65, 88, 70] 验证，输出应该是：

[65, 70, 78, 88, 92]
参考答案（点开查看）

把比较的符号反过来就行：

ts
if (list[i] > list[i + 1]) {   // 前面的比后面大？换！
  swap(list, i, i + 1)
}

这次是"大的往后沉"，最小的一路冒到最前面。 冒泡排序改方向，只需改一个符号。

第 2 题（思考题）：一趟以后，什么保证了？ ​

跑完第一趟后，数组 [78, 92, 65, 88, 70] 变成 [92, 78, 88, 70, 65]。 这时候，哪一个数的位置是"最终"的（以后几趟不会再变）？为什么？

参考答案（点开查看）

65（最后一位）已经归位，后面几趟它不会再动。

因为第一趟里，65 一路被"小的往后换"换到了最后——它已经比 前面所有数都小（或相等）了。以后几趟，比较范围最多到 "最后一个归位数的前一位"，根本碰不到 65。

这就是冒泡排序"每趟归位一个"的保证：第 k 趟结束， 末尾第 k 个数一定是它最终的位置。

第 3 题（思考题）：O(n²) 有多吓人？ ​

一个班 50 人，冒泡排序最坏要比较大约多少次？全校 2000 人呢？ （提示：n × n ÷ 2。）

参考答案（点开查看）
  • 50 人：50 × 50 ÷ 2 ≈ 1225 次
  • 2000 人：2000 × 2000 ÷ 2 ≈ 200 万次

人数从 50 涨到 2000（40 倍），比较次数从 1225 涨到 200 万（约 1600 倍）—— 40 × 40 = 1600，这正是 O(n²) 的"平方"在起作用。 200 万次比较电脑不眨眼，但如果数据是 10 亿级别， O(n²) 就会慢到不可接受——那时候就要请出更快的排序了 （这本书的进阶篇里有！）。

下一课预告：冒泡排序一趟才归位一个，而且换位特别多。 有个更"聪明"的办法：每次直接从剩下的数里挑出最小的， 放到最前面——像老师排队挑人一样。它比冒泡少做多少事呢？