计数排序如何处理负数和很大的值域？

简化版

计数排序适合值域较小的整数排序。

如果有负数，可以用偏移量把值映射到非负下标，例如 index = value - minValue。如果值域很大，即使元素数量不多，计数数组也会很大，这时计数排序就不合适，可以考虑哈希计数、坐标压缩或改用比较排序。

计数排序快的前提是值域可控。

详细版

计数排序的空间复杂度和取值范围有关。

如果最小值是 minVal，最大值是 maxVal，计数数组长度是：

range = maxVal - minVal + 1

负数处理：

count[x - minVal]++

情况	处理方式
有负数但范围小	用偏移量
值域很大但不同值少	哈希计数或坐标压缩
值域大且分布散	比较排序更稳

不要只看 n，还要看值域 range。

完整版教学

1. 计数排序依赖什么前提

计数排序不是通用排序。

它依赖元素是可计数的离散值，通常是整数，并且值域不能太大。

核心思路是：

统计每个值出现几次
再按值从小到大输出

所以它利用了数值本身，而不是只靠比较。

2. 为什么负数不能直接当下标

数组下标通常从 0 开始。

如果元素是 -3，不能直接访问：

count[-3]

解决办法是整体平移。

假设最小值是 -5，那么：

index = value - (-5)

这样 -5 映射到 0，-4 映射到 1。

负数不是问题，真正的问题是值域跨度是否可控。

3. 偏移量怎么实现

先扫描数组找到最小值和最大值：

minVal = min(nums)
maxVal = max(nums)
range = maxVal - minVal + 1

计数时：

count[num - minVal]++

输出时：

value = index + minVal

这样就能处理负数、零和正数。

4. 值域很大会发生什么

如果数组只有 1000 个元素，但最小值是 -1,000,000,000，最大值是 1,000,000,000，计数数组长度约 2,000,000,001。

这显然不划算。

指标	影响
元素数量 `n`	输入规模
值域 `range`	计数数组空间
时间	`O(n + range)`
空间	`O(range)`

所以计数排序不是只看 O(n)，完整复杂度是 O(n + range)。

5. 坐标压缩能解决什么

如果不同值数量很少，但值域跨度很大，可以做坐标压缩。

例如：

[-1000000, 5, 9999999]

不同值只有 3 个，可以映射成：

-1000000 -> 0
5        -> 1
9999999  -> 2

但坐标压缩本身需要先排序不同值，所以不一定保持线性时间。

6. 哈希计数适合什么

哈希计数只记录出现过的值：

map[value] = count

它能避免巨大空数组，但如果要按值从小到大输出，还需要对 key 排序。

方案	优点	代价
数组计数	线性扫描输出	值域大时浪费
哈希计数	只存出现值	输出有序要排序 key
坐标压缩	空间紧凑	预处理复杂

7. 稳定计数排序怎么做

如果排序对象有附加信息，并且要求稳定，需要前缀和。

步骤：

统计 count；
把 count 转成前缀位置；
从右向左扫描原数组，把元素放到结果数组。

pos = prefix[value]
output[pos - 1] = item
prefix[value]--

从右向左是为了保持相等元素的相对顺序。

8. 常见误区与追问

误区：计数排序不能处理负数。 可以通过 value - minVal 做偏移映射。
误区：计数排序永远是 O(n)。 更准确是 O(n + range)。
误区：值域很大也适合计数排序。 值域太大时空间和扫描成本都会失控。
追问：如何保持稳定？ 使用前缀和定位，并从右向左放入输出数组。
追问：不同值很少但值域很大怎么办？ 可以考虑哈希计数或坐标压缩。

简化版

详细版