Go语言中的计数排序：高效处理整数序列的线性时间排序算法（详解计数排序适用场景与Go实现）

计数排序的适用场景

虽然计数排序效率高，但它并非适用于所有情况。以下是其典型适用场景：

• 待排序的数据是非负整数（或可映射为非负整数）；
• 数据的取值范围（k）不能太大，理想情况下 k ≈ n 或 k < n²；
• 需要稳定排序（计数排序天然稳定）；
• 对时间效率要求高，且满足上述条件时，可替代快排、归并等 O(n log n) 算法。

例如：对年龄（0~120）、考试分数（0~100）、小范围ID号等进行排序，就是计数排序的绝佳应用场景。

Go语言实现计数排序

下面是一个完整的、易于理解的 Go 语言计数排序实现：

package mainimport "fmt"// countingSort 实现计数排序// arr: 待排序的非负整数切片// maxVal: 数组中的最大值func countingSort(arr []int, maxVal int) []int {    // 创建计数数组，长度为 maxVal + 1    count := make([]int, maxVal+1)    // 统计每个元素出现的次数    for _, num := range arr {        count[num]++    }    // 重构排序后的数组    result := make([]int, 0, len(arr))    for i := 0; i <= maxVal; i++ {        for count[i] > 0 {            result = append(result, i)            count[i]--        }    }    return result}func main() {    data := []int{4, 2, 2, 8, 3, 3, 1}    fmt.Println("原始数组:", data)    // 找到最大值    maxVal := 0    for _, v := range data {        if v > maxVal {            maxVal = v        }    }    sorted := countingSort(data, maxVal)    fmt.Println("排序后数组:", sorted)}  

这段代码清晰展示了计数排序的三个步骤：

1. 遍历原数组，统计每个数字出现的频次；
2. 创建一个计数数组 count，索引代表数值，值代表出现次数；
3. 按顺序遍历计数数组，将数字按次数“展开”回结果数组。

注意事项与局限性

尽管Go排序算法中的计数排序效率很高，但需注意以下几点：

• 空间开销大：若最大值很大（如 10⁹），则计数数组会占用大量内存；
• 仅适用于整数：无法直接用于浮点数、字符串等类型；
• 负数需特殊处理：可通过整体偏移转为非负数再排序。

总结

计数排序是一种高效的线性时间排序方法，在满足特定条件（小范围非负整数）时，性能远超传统比较排序。通过本文的讲解和 Go 代码示例，相信你已经掌握了Go语言计数排序的基本原理和实现方式。在实际开发中，合理判断数据特征，选择合适的排序算法，是提升程序性能的关键。

关键词回顾：Go语言计数排序、计数排序适用场景、Go排序算法、线性时间排序。