计数排序（Counting Sort）是一种非比较排序算法，特别适用于处理范围有限、整数值为主的输入数据。它的关键在于利用统计每个元素出现的频率，从而直接计算出每个元素在有序数组中的位置。这种排序算法效率高，在许多实际应用中得到了广泛使用。
计数排序的原理
计数排序的基本思想是首先对待排序的元素进行计数，然后利用计数信息来将元素放置到正确的位置。这个过程可以分为几个步骤：
步骤一：确定范围
首先，需要找出待排序数组中的最小值和最大值。通过这些值，可以确定计数数组的大小，以便于存储每个元素的出现频率。如果待排序元素的范围很大，计数排序的效率可能会降低，因此该算法最适合于范围较小的整数排序。
步骤二：创建计数数组
接下来，创建一个计数数组，用于存储每个元素的出现次数。计数数组的索引对应待排序数组中的元素值。此数组的大小为最大值与最小值之差加一，以确保能够包含所有可能的值。
步骤三：填充计数数组
然后，遍历待排序数组，将每个元素在计数数组中对应的索引位置上的值加一。这将有效记录每个元素出现的次数。
步骤四：累加计数数组
在填充完计数数组后，需要将计数数组变为累加数组。即，对于计数数组中的每个位置，前面元素的值累加到当前位置上，表示小于等于当前值的元素个数。这一步是为了确定每个元素在输出数组中的位置。
步骤五：生成有序数组
最后，根据累加数组，反向遍历待排序数组，逐一将元素放到正确的位置。这是为了确保在相同元素的排序中保证稳定性，即相同值的元素在原数组中的相对顺序保持不变。
计数排序的时间复杂度
计数排序的时间复杂度为O(n + k)，其中n为待排序的元素个数，k为元素值的范围。相较于其他比较排序算法（如快速排序和归并排序），计数排序在处理大规模的数据上有显著的性能优势，尤其是当k相对于n不是特别大的情况下。但在元素范围过大时，空间复杂度会显著增加，导致效率下降，因此需谨慎使用。
计数排序的实现
以下是计数排序的Go语言实现示例：
package main
import "fmt"
// CountingSort 实现计数排序算法
func CountingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
// 找到最大值和最小值
maxVal, minVal := arr[0], arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
if num < minVal {
minVal = num
}
}
// 创建计数数组
rangeSize := maxVal - minVal + 1
count := make([]int, rangeSize)
// 计数每个元素出现的频率
for _, num := range arr {
count[num-minVal]++
}
// 累加计数数组
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
// 创建输出数组
output := make([]int, len(arr))
for i := len(arr) - 1; i >= 0; i-- {
output[count[arr[i]-minVal]-1] = arr[i]
count[arr[i]-minVal]--
}
return output
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
sortedArr := CountingSort(arr)
fmt.Println("Sorted array:", sortedArr)
}
计数排序的应用场景
计数排序在处理一定范围内的整数时表现出色，适用于以下场景：
1. 笔试成绩排序
在学校或考试中，通常会统计学生的成绩，而成绩通常为定量数据，适合使用计数排序来快速排序。
2. 频率分析
在字符处理或数据分析中，我们可能需要对字符或数字的出现频率进行统计，也可以用计数排序来提高效率。
3. 直方图生成
许多图形处理和统计分析中，直方图的生成也是基于元素计数的，应用计数排序可以帮助更快的生成图形数据。
综上所述，计数排序是一种高效且简单的排序算法，尤其适合较小范围内的整数排序。在合适的场景中使用，能够极大提高性能和效率。