Go语言怎么做计数排序_Go语言计数排序算法教程【详解】-Golang-PHP中文网

计数排序适合非负整数且值域接近数组长度的场景，如成绩、年龄等；不适用于负数、浮点数、大范围或稀疏整数。需通过偏移支持负数，倒序填值保证稳定性，非原地算法，不可替代sort.Ints。

go语言怎么做计数排序_go语言计数排序算法教程【详解】

计数排序适合什么场景？

计数排序不是万能的，它只在特定条件下快得离谱：输入全是非负整数，且最大值 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  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 = 0; i-- {
    v := arr[i]
    pos := count[v+offset] - 1
    res[pos] = v
    count[v+offset]--
}
return res

}