计数排序适合非负整数且值域接近数组长度的场景，如成绩、年龄等；不适用于负数、浮点数、大范围或稀疏整数。需通过偏移支持负数，倒序填值保证稳定性，非原地算法，不可替代sort.Ints。
计数排序适合什么场景？
计数排序不是万能的，它只在特定条件下快得离谱：输入全是非负整数，且最大值 max 和数组长度 n 满足 k = max + 1 接近 n（即 k = O(n)）。一旦 max 达到 10⁶ 甚至更高，make([]int, max+1) 就会分配巨量内存，反而比 sort.Ints 慢得多、还可能 OOM。
- ✅ 适合：成绩（0–100）、年龄（0–150）、状态码（0–99）、小范围枚举值
- ❌ 不适合：时间戳、ID、负数、浮点数、稀疏大整数（如
[]int{1, 2, 1000000}） - ⚠️ 注意：标准库
sort.Ints是快排+堆排+插入排序混合实现，对一般整数数组更鲁棒；计数排序是“有前提的加速器”，不是替代品
怎么写一个真正可用的 CountingSort 函数？
别照抄教科书里“假设最小值是 0”的简化版。真实数据常含负数或非零起点，必须支持偏移。核心是两步：统计频次 → 构造前缀和 → 倒序填入结果（保证稳定性）。
func CountingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
min, max := arr[0], arr[0]
for _, v := range arr {
if v < min {
min = v
}
if v > max {
max = v
}
}
offset := -min // 支持负数的关键偏移
size := max - min + 1
count := make([]int, size)
<pre class="brush:php;toolbar:false;">// 统计频次
for _, v := range arr {
count[v+offset]++
}
// 构造前缀和（count[i] 表示 ≤ (i-offset) 的元素个数）
for i := 1; i < size; i++ {
count[i] += count[i-1]
}
// 倒序遍历原数组，保证稳定性
res := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
v := arr[i]
pos := count[v+offset] - 1
res[pos] = v
count[v+offset]--
}
return res}
- 必须用 倒序遍历原数组，否则相同值的相对顺序会反转（破坏稳定性）
-
offset让负数也能映射到非负索引，没有它，arr[i] = -5会直接 panic -
size = max - min + 1是最小必要空间，比固定开1e6更安全
为什么原地排序不可行？
计数排序天然不是原地算法：它依赖一个额外的 count 数组存频次，还要一个 res 数组存结果。试图“复用输入数组”会导致逻辑混乱——你在遍历 arr 填 res 的同时，arr 还在被读取，无法覆盖。
立即学习“go语言免费学习笔记（深入）”；
- 不能加
arr = append(arr[:0], res...)就算“原地”，那只是切片重赋值，底层数组已不同 - 如果内存极度敏感，应先评估是否真需计数排序；否则老实用
res，清晰且无副作用 - Go 的 slice header 很轻，但误以为“没分配新内存”是常见错觉
和 sort.Ints 对比时要注意什么？
sort.Ints 是就地排序、稳定、泛型友好、经过充分测试；而手写 CountingSort 是复制排序、仅限整数、需手动处理边界。二者不构成“替代关系”，而是“条件满足时的性能选项”。
- 测速别只用 10 个数：至少
1e5级别才看出差异；小数组sort.Ints反而更快（cache 局部性好） - 若数据含负数但你硬截断为 0，结果就错了——没有运行时错误，只有逻辑错误
- Go 1.21+ 支持
constraints.Ordered，但计数排序无法泛型化（依赖整数值做数组索引），这点本质受限
负数处理、偏移计算、倒序填值——这三处写错任意一个，排序就悄无声息地错乱，而且很难一眼看出来。
