排序算法系列 09：计数排序——不比较，直接数

前面所有排序算法有一个共同点：都要比较两个元素谁大谁小。比较排序的理论下界是 O(n log n)——你没法再快了。

但如果数据满足特定条件，完全可以绕开比较，直接做到线性时间 O(n)。计数排序就是这条路上的第一个代表。

核心思想

统计每个值出现了几次，然后按值从小到大把它们"还原"出来。

就像老师统计考试成绩：准备 0 到 100 分的格子，每看到一个分数就在对应格子里画个"正"字。最后从 0 分格子开始往后读，成绩就自动排好了。

text

原始数组：5, 2, 2, 7, 1

统计：
  1 → 1次
  2 → 2次
  5 → 1次
  7 → 1次

还原：1, 2, 2, 5, 7

全程没有任何"谁比谁大"的比较操作。

前提条件

计数排序不是万能的，它有明确的适用限制：

数据必须是整数（或者能映射成整数）
数据范围不能太大

如果数据是 [1, 2, 3, 100000000]，你需要开一个一亿大小的计数数组，纯属浪费。

适合的场景是：值的种类有限、范围可控。比如年龄（0~~120）、考试分数（0~~100）、等级（1~5）。

代码实现（简单版）

javascript

function countingSort(arr) {
  if (arr.length <= 1) return [...arr];

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const count = new Array(max - min + 1).fill(0);

  // 计数
  for (const num of arr) {
    count[num - min]++;
  }

  // 还原
  const result = [];
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      result.push(i + min);
      count[i]--;
    }
  }

  return result;
}

console.log(countingSort([5, 2, 2, 7, 1]));
// [1, 2, 2, 5, 7]

用 num - min 做下标偏移，这样即使有负数也能正确映射。比如最小值是 -3，那 -3 对应下标 0，-2 对应下标 1，依此类推。

稳定版本（排序对象时用）

上面的简单版只能排纯数字。如果你要排序对象——比如按分数排序学生，相同分数的学生要保持原始顺序——就需要稳定版本。

javascript

function countingSortStable(items, getKey) {
  if (items.length <= 1) return [...items];

  const keys = items.map(getKey);
  const min = Math.min(...keys);
  const max = Math.max(...keys);
  const count = new Array(max - min + 1).fill(0);

  // 计数
  for (const key of keys) {
    count[key - min]++;
  }

  // 前缀和：count[i] 变成"值 ≤ i+min 的元素总数"
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // 从后往前遍历原数组，放到正确位置
  const result = new Array(items.length);
  for (let i = items.length - 1; i >= 0; i--) {
    const key = getKey(items[i]);
    const index = key - min;
    count[index]--;
    result[count[index]] = items[i];
  }

  return result;
}

const students = [
  { name: "A", score: 90 },
  { name: "B", score: 80 },
  { name: "C", score: 90 }
];

console.log(countingSortStable(students, s => s.score));
// B(80), A(90), C(90) —— A 和 C 相对顺序不变

稳定版的关键是"前缀和 + 从后往前放"。前缀和告诉你每个值应该放到结果数组的哪个范围，从后往前遍历保证了相同值的元素保持原有顺序。

这个技巧在后面基数排序里还会用到。

复杂度

设 n 是元素数量，k 是值域范围（max - min + 1）：

指标	复杂度
时间	O(n + k)
空间	O(k)（简单版）或 O(n + k)（稳定版）

当 k 不大的时候，这基本就是线性时间。比冒泡的 O(n²) 快多少？数据量 10000，k = 100：计数排序大约 10100 次操作，冒泡大约 1 亿次。

什么时候用计数排序？

判断标准很简单：值域范围 k 和数据量 n 是不是一个量级？

k ≈ n 或 k < n：很适合，用就对了
k >> n：不适合，空间浪费太大，换别的

典型适用场景：

考试分数排序（0~100）
年龄排序（0~120）
评分排序（1~5）
基数排序的子过程（每一位只有 0~9）

下一篇来看桶排序——和计数排序思路相似，但适用范围更广，可以处理小数和非整数数据。

系列导航

上一篇：排序算法系列 08：堆排序——用数据结构的力量排序

下一篇：排序算法系列 10：桶排序——先分堆再各自整理