【算法图解】计数排序：不比较也能排序

你学过的冒泡/快排/归并都属于“比较排序”：

通过比较两个元素大小来决定顺序

比较排序有一个理论下界：

最好也得 $\Omega(n\log n)$（比较模型下）

计数排序很特别：它不走比较模型。

它的思路是：

既然值域有限，我就把每个值出现了多少次数出来。

这样就能在条件满足时做到线性级别的时间。

1. 计数排序的适用条件

计数排序不是万能。

它适合：

数据是整数
值域范围不大（例如 0~100000）
或者可以接受开一个大小为 $k$ 的计数数组

其中：

$n$ 是元素数量
$k$ 是值域大小

复杂度通常是：

时间：$O(n + k)$
空间：$O(k)$

如果 $k \gg n$，计数排序就不划算。

2. 最简单版本：只排序不求稳定

function countingSort(arr, maxValue) {
  const count = new Array(maxValue + 1).fill(0)
  for (const x of arr) count[x]++

  const result = []
  for (let v = 0; v <= maxValue; v++) {
    for (let i = 0; i < count[v]; i++) result.push(v)
  }

  return result
}

这个版本能排序，但不保证稳定性（如果元素带“附加信息”，相等值的相对顺序无法保证）。

3. 稳定计数排序：前缀和 + 逆序回填

稳定计数排序的经典写法是：

统计 count
做前缀和，让 count[v] 表示“<= v 的元素数量”
从右到左扫描原数组，把元素放到正确位置

function countingSortStable(arr, maxValue) {
  const count = new Array(maxValue + 1).fill(0)
  for (const x of arr) count[x]++

  for (let v = 1; v <= maxValue; v++) {
    count[v] += count[v - 1]
  }

  const out = new Array(arr.length)
  for (let i = arr.length - 1; i >= 0; i--) {
    const x = arr[i]
    count[x]--
    out[count[x]] = x
  }

  return out
}