小探险家学算法

Appearance

18. 数票机（计数排序） ​

知识点：计数排序 —— 不比较，只数数（O(n + k)）

项目：投票统计 + 成绩分段

故事开场：不用比较的排序？ ​

老师要评选"最受欢迎课间活动"，全班 50 人投票，每人投 1~10 星：

ts
const votes = [7, 3, 8, 3, 10, 7, 3, 8, 5, 7, 10, 3, 7, 5, 8, ...]

"问题来了，"老师说，"把 50 张票从低到高排好，我要看分布。 快排和归并都能排——可它们都是比较出来的：两个数比大小， 比来比去。可你看这些票：只有 1~10 十种可能！"

"票数只有 10 种……"你念叨着，"能不能不比较呢？"

老师提醒你："还记得第 8 章的统计字数吗？一句话里每个字出现几次， 用 Map 一数就出来了。票也一样——数一数 1 星有几张、2 星有几张……

数完票，排序结果不就出来了吗？"

笨办法先行：数票，然后呢？ ​

你写了个数票程序（用第 8 章的思路）：

ts
const votes = [7, 3, 8, 3, 10, 7, 3, 8, 5, 7]

// 数票：counts[星数] = 张数
const counts: number[] = []
for (let i = 0; i <= 10; i++) {
  counts.push(0)              // 先准备 11 个格子（0~10 星）
}
for (let i = 0; i < votes.length; i++) {
  counts[votes[i]]++
}
console.log(counts)

输出：

[0, 0, 0, 3, 0, 1, 0, 3, 2, 0, 1]

你数出来了：3 星有 3 张、5 星 1 张、7 星 3 张、8 星 2 张、10 星 1 张。

可是然后呢？"数完票，怎么变成排好序的数组？"你卡住了。

你想了想："嗯……从 1 星开始，有 3 张就把 1 输出 3 次， 有 0 张就跳过……"

等等，这不就是排序吗！ 你差点没认出来——

引出知识点：计数排序——按顺序"放票" ​

对，这就是排序！思路是：

  1. 数票：数出每个分数出现几次（用数组当"票箱"，下标就是分数）
  2. 放票：从最小分数开始，一张一张把票"放回"队伍里—— 分数是几，就输出几，连放它出现的次数
ts
// 计数排序：把 list 从小到大排好（list 里的数都是 0~max 之间的整数）
function countingSort(list: number[]): number[] {
  // 第 1 步：找出最大的数（决定票箱要多少个格子）
  let max = list[0]
  for (let i = 1; i < list.length; i++) {
    if (list[i] > max) {
      max = list[i]
    }
  }

  // 第 2 步：准备票箱，数票
  const counts: number[] = []
  for (let i = 0; i <= max; i++) {
    counts.push(0)
  }
  for (let i = 0; i < list.length; i++) {
    counts[list[i]]++
  }

  // 第 3 步：从 0 到 max，按顺序"放票"
  const result: number[] = []
  for (let score = 0; score <= max; score++) {
    for (let k = 0; k < counts[score]; k++) {
      result.push(score)      // 有几张票，就放几个
    }
  }

  return result
}

const votes = [7, 3, 8, 3, 10, 7, 3, 8, 5, 7]
console.log(countingSort(votes))

输出：

[3, 3, 3, 5, 7, 7, 7, 8, 8, 10]

排好了！注意看：整个过程没有一个"比较"（没有 a < b 这种比较）—— 有的只是"数数"和"放票"。

跑起来：数票机有多快？ ​

和快排比一比！造 2 万个 0~100 的成绩：

ts
const bigList: number[] = []
for (let i = 0; i < 20000; i++) {
  bigList.push(Math.floor(Math.random() * 101))   // 0~100 的成绩
}

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

console.time("计数排序")
countingSort(bigList.slice())
console.timeEnd("计数排序")

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

快速排序: 约 35ms
计数排序: 约 3ms

10 倍差距！ 为什么计数排序这么快？

  • 快排：要比较 n log n 次（2 万个数要比较约 30 万次）
  • 计数排序：数一遍 n 个数 + 放一遍 max+1 个格子—— 总共 n + max 次！2 万个数、100 个格子，才 2 万零 100 次

它的复杂度是 O(n + k)（k 是数值范围，比如成绩 0~100，k=100）。 当 k 很小时，它比所有"比较排序"都快——几乎是 O(n)！

数票机的"门票"：数值必须是整数，而且范围不能太大。 排序 0~100 的成绩，票箱只要 101 个格子；排序 0~100 亿的数字， 票箱要 100 亿个格子——内存直接爆炸。 所以计数排序适合"数值范围小"的场合（投票、成绩、星级……）。

小挑战 ​

  1. 从大到小：把计数排序改成从大到小排（提示：第 3 步 从 max 往 0 放票）。
  2. 负数票？：投票改成 -5 到 +5 星（负数！数组下标不能是负数）。 怎么处理？（提示：给所有分数加 5，变成 0~10；放票时再减回来。 这就是"偏移"技巧，大数据排序里很常见。）
  3. 成绩分段：用计数排序统计全班成绩分布（0~100）， 再输出"90 分以上几个人、80~89 几个人……"（提示：排完序后 数一数各段有多少个——或者直接看票箱！）。

课后练习 ​

第 1 题（动手题）：给投票排排队 ​

投票结果 [4, 2, 2, 5, 4, 4, 2, 5, 3]（1~5 星），用 countingSort 排序，输出结果，并手动验证。

参考答案（点开查看）
ts
const votes = [4, 2, 2, 5, 4, 4, 2, 5, 3]
console.log(countingSort(votes))
// [2, 2, 2, 3, 4, 4, 4, 5, 5]

票箱：2 星 3 张、3 星 1 张、4 星 3 张、5 星 2 张。 按顺序放票：2×3、3×1、4×3、5×2 → [2,2,2,3,4,4,4,5,5] ✅

第 2 题（思考题）：什么时候不能用数票机？ ​

下面的数据，哪些适合计数排序，哪些不适合？为什么？

① 全班 50 人的身高（cm，取整） ② 全国人的身份证号 ③ 1~10 的星级评分 ④ 0~100 亿的随机整数

参考答案（点开查看）

① 适合：身高 120~200 左右，范围小，票箱几百个格子就够。 ② 不适合：身份证号范围巨大（10 的 18 次方），票箱要开 10^18 个格子——内存直接爆炸。 ③ 适合：10 个格子就够。 ④ 不适合：范围 100 亿，票箱 100 亿个格子（约 800GB 内存）。

判断标准一句话：数值范围（最大值−最小值）小，才用数票机。

第 3 题（思考题）：数票 vs 比较 ​

计数排序快，那为什么我们还需要快排、归并这些"比较排序"？ （提示：想想"数票机"的门票是什么。）

参考答案（点开查看）

因为数票机有三个限制：

  1. 只能排整数：小数、字符串（名字）没法当下标
  2. 范围必须小：范围一大，票箱就把内存吃光了
  3. 要知道最大值（或准备足够大的票箱）

比较排序（快排、归并）没有这些限制：小数、字符串、任何能比较 大小的东西都能排。所以现实程序里，比较排序是"万能"的， 计数排序是"特快专线"——只服务"整数 + 范围小"的乘客。

没有最好的排序，只有最合适的排序。 以后你还会见到桶排序、 基数排序……每种排序都有自己的"门票"和"绝活"。

下一课预告：家谱！爷爷有两个孩子，孩子又有孩子……老师让 你用程序表示家族关系。用数组？关系全丢了。用链表？一个钩子 只能连一个。家谱可是一爹两娃啊——该用什么结构？