小探险家学算法

Appearance

14. 扑克牌理牌（插入排序） ​

知识点：插入排序 —— 新牌插到正确位置（O(n²)，但对近排序数据很快）

项目：摸牌理牌

故事开场：摸一张，理一张 ​

周末，你和爷爷打扑克。爷爷理牌的方法和你不一样：

你是把所有牌摸完之后，才一起整理；爷爷是摸一张，理一张——每摸到 一张新牌，就立刻把它插到手里已经排好的牌堆的正确位置。

你好奇地看了看爷爷的手牌：小到大排得整整齐齐。摸到一张"7"， 他扫了一眼手里的牌，把 7 插到了 5 和 8 之间。全程就动了一张牌的位置。

你心想：这个办法，比冒泡和选择都省事啊！

回想前两章：

  • 冒泡排序：一趟一趟冒泡，全部数据比来比去
  • 选择排序：每趟从剩下的全部里挑最小的

而爷爷的办法是：手里已有的牌已经排好了，新牌只需要找到自己的位置， 插进去。已经排好的部分不用再动——只用处理一张新牌！

笨办法先行：每次重新排一遍？ ​

你马上想到了"用程序模拟摸牌"。可你的第一版程序是这样的：

ts
const hand: number[] = []   // 手里的牌，从空开始

// 摸到一张新牌……怎么插进手里已经排好的牌堆？
function drawCard(card: number): void {
  hand.push(card)           // 先放手里
  // ……然后呢？重新把整手牌排一遍？
}

然后你发现，你只会用上一章的 selectionSort，把整手牌重新排一遍：

ts
function drawCard(card: number): void {
  hand.push(card)
  selectionSort(hand)       // 把整手牌重新排一遍！
}

能排对，可你隐隐觉得不对劲：

每次摸一张牌，就把整手牌重新排一遍——摸到第 10 张牌时， 要把 10 张牌全排一遍；摸到第 20 张时，要排 20 张。 爷爷明明只用插一张，你却在反复重排所有牌！

牌少还好，要是手里有 100 张牌，每摸一张都重排 100 张， 摸 100 张牌就排了 100 × 100 = 10000 次工作——又回到 O(n²) 了， 而且做的是无用功：除了新牌，其他牌的位置根本不用动！

引出知识点：插入排序——只需要挪"比新牌大"的 ​

爷爷的办法到底妙在哪？拆开看：

假设手里已经有排好的牌：[2, 5, 8, 10]，现在摸到一张 7。

正确的插入方法是从后往前看：

[2, 5, 8, 10, 7]      ← 7 先放到最后
         ↑ 10 比 7 大 → 10 往后挪一格
[2, 5, 8, -, 10]
          ↑ 8 比 7 大 → 8 往后挪一格
[2, 5, -, 8, 10]
       ↑ 5 比 7 小 → 停！就是这里
[2, 5, 7, 8, 10]      ← 7 放进去

规则只有一条：从后往前，凡是比新牌大的，都往后挪一格； 遇到比新牌小（或相等）的，就停下来，把新牌放进去。

注意：只有比新牌大的牌才挪——比新牌小的（2 和 5）纹丝不动。 这就是"插入"和"重排"的区别：重排动了所有牌，插入只动该动的。

动手实现：插入排序 ​

先写"插一张牌"的动作：

ts
// 把 card 插进 hand（假设 hand 是排好序的）
function insertCard(hand: number[], card: number): void {
  hand.push(card)                 // 新牌先放到最后

  let pos = hand.length - 1       // 从最后一张开始往前看
  while (pos > 0 && hand[pos - 1] > card) {
    hand[pos] = hand[pos - 1]     // 前一张比新牌大？往后挪一格
    pos--                         // 继续往前看
  }

  hand[pos] = card                // 找到位置，放下新牌
}

用 insertCard 模拟摸牌：

ts
const hand: number[] = []
insertCard(hand, 8)
insertCard(hand, 2)
insertCard(hand, 5)
insertCard(hand, 10)
insertCard(hand, 7)
console.log(hand)

输出：

[2, 5, 7, 8, 10]

每摸一张，手里都是排好的！这就是爷爷的理牌法。

现在，把"摸一张插一张"应用到整个数组上——数组的前面部分 就是"手里已排好的牌"，从第 1 张开始，一张张往已排好的部分插：

ts
// 插入排序：前 i 个保持排好序，把第 i 个插进去
function insertionSort(list: number[]): void {
  for (let i = 1; i < list.length; i++) {
    const card = list[i]          // 摸到的新牌
    let pos = i

    // 从新牌的位置往前看，比新牌大的都往后挪一格
    while (pos > 0 && list[pos - 1] > card) {
      list[pos] = list[pos - 1]
      pos--
    }

    list[pos] = card              // 把新牌放到腾出来的位置
  }
}

const numbers = [8, 2, 5, 10, 7]
insertionSort(numbers)
console.log(numbers)

输出：

[2, 5, 7, 8, 10]

跑起来：插入排序的每一步 ​

用慢动作看 [8, 2, 5, 10, 7] 是怎么被排好的：

初始：       [8, 2, 5, 10, 7]
摸到 2：     [2, 8, 5, 10, 7]     2 比 8 小，8 往后挪，2 到最前
摸到 5：     [2, 5, 8, 10, 7]     5 插到 2 和 8 之间
摸到 10：    [2, 5, 8, 10, 7]     10 已经最大，不用动
摸到 7：     [2, 5, 7, 8, 10]     7 插到 5 和 8 之间

每摸一张牌，前面已经排好的部分一个不多动。

自己用代码验证：

ts
const test = [8, 2, 5, 10, 7]
insertionSort(test)
console.log(test)

输出：

[2, 5, 7, 8, 10]

插入排序的"秘密武器"：对快排好的数据特别快 ​

插入排序最有趣的地方是：它有个"隐藏技能"。

想一想：如果数组本来就是排好序的（比如 [1, 2, 3, 4, 5]）， 插入排序会做多少事？

  • 摸到 2：2 > 1？不需要挪，直接放
  • 摸到 3：3 > 2？不需要挪
  • ……每张牌都"直接放"，一次都不挪！

数据本来就有序时，插入排序只做 n 次比较，是 O(n)！

对比一下：

数据状态冒泡选择插入
完全乱序O(n²)O(n²)O(n²)
本来就排好O(n²)（优化版可以 O(n)）O(n²)（不知道省事）O(n)
接近排好一般一般接近 O(n)

所以现实程序里，插入排序常被用来处理"数据基本有序"的情况—— 比如新同学插进已按学号排好的名单、往排好序的成绩单里插入新成绩。

三兄弟总结（O(n²) 三兄弟）： 冒泡——简单直观，但交换多； 选择——交换少，适合"搬数据很贵"的场合； 插入——对"本来就排好/接近排好"的数据有隐藏加速，日常最常用。

小挑战 ​

  1. 从大到小：把插入排序改成从大到小排（提示：改 while 里的 一个符号，让"比新牌小的"往后挪）。
  2. 空手摸牌：用 insertCard 模拟"从一副打乱的牌里摸 10 张"： 造一个打乱的数组，一张张 insertCard 进空手，验证手里始终有序。
  3. 新同学插队：班级名单 ["小丽", "小刚", "小明", "小红", "小雨"] 已经按"字的编号"排好，新同学"小华"要插进来。把 insertCard 改成字符串版（参数类型从 number[] 改成 string[] 即可—— 字符串之间也能用 > 比较，比的就是字的编号）， 把"小华"插到正确位置，打印新名单。

课后练习 ​

第 1 题（动手题）：给成绩单插入新成绩 ​

成绩单 [65, 70, 78, 88, 92] 已经排好序，现在插入一个新成绩 85， 要求插入后依然有序。用 insertCard 实现并验证。

参考答案（点开查看）
ts
const scores = [65, 70, 78, 88, 92]
insertCard(scores, 85)
console.log(scores)
// [65, 70, 78, 85, 88, 92]

insertCard 会从后往前看：92 > 85 挪，88 > 85 挪，78 < 85 停， 85 插到 78 和 88 之间。只有两个数挪了位置——其他四个纹丝不动。 这就是插入排序"只动该动的"。

第 2 题（思考题）：为什么从后往前？ ​

insertCard 为什么从后往前看，而不是从前往后？ （提示：想想"往后挪一格"会覆盖谁。）

参考答案（点开查看）

从前往后看，你会遇到"把新牌放哪"的尴尬：比如 [2, 5, 8, 10] 插 7， 从前往后先看到 2（比 7 小），再看到 5（比 7 小），看到 8（比 7 大）， "应该插在 8 前面"——可这时候你还没把 8 往后挪，直接把 7 放进去 就把 8 覆盖了。

从后往前就不会：先把比新牌大的挪走（腾出空位），再放下新牌。 "先腾地方，再放东西"，顺序对了，一个数据都不会丢。 （这和第 13 章"先想清楚会不会覆盖"是同一个道理！）

第 3 题（思考题）：隐藏加速 ​

数组 [1, 2, 3, 4, 5, 6] 本来就排好了，用插入排序排它， 一共要做多少次"比较"？用 O(几) 表示。

参考答案（点开查看）

每个数插入时只看一眼"前面那个数"：1 < 2？是，直接放。 一共只比较 5 次（n−1 次），是 O(n)。

这就是插入排序的隐藏加速：数据越接近有序，它越快。 最乱的情况才是 O(n²)。如果数据完全逆序（[6, 5, 4, 3, 2, 1]）， 每个数都要挪到底，才是最坏情况 O(n²)。

预告：冒泡、选择、插入——O(n²) 三兄弟都认识了吧！ 下一章来点不一样的：套娃。打开一个套娃，里面还是套娃…… 有一种函数，它打开自己，里面还是自己。它叫递归， 它能一口气解决"汉诺塔"这种循环几乎写不出来的难题。