什么是计数排序？

计数排序(Counting Sort)是一种非比较型的排序算法，它通过计算每个元素出现的次数来实现排序。与基于比较的排序算法(如快速排序、归并排序)不同，计数排序利用元素的实际值来确定其在输出数组中的位置，因此具有线性时间复杂度。

计数排序的基本思想

计数排序的核心思想是：对于给定的输入序列中的每一个元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的正确位置上了。

计数排序的步骤

1. 找出待排序数组的最大值： 确定数组中的最大值k
2. 创建计数数组： 创建一个长度为k+1的计数数组count，初始化为0
3. 统计元素出现次数： 遍历输入数组，统计每个元素出现的次数，存储在count数组中
4. 计算累积和： 对count数组进行顺序累加，使得count[i]表示小于等于i的元素个数
5. 构建输出数组： 反向遍历输入数组，根据count数组中的位置信息，将元素放入输出数组的正确位置

计数排序的复杂度分析

最佳和最坏情况

• 最佳情况： 当k=O(n)时，时间复杂度为O(n)
• 最坏情况： 当k远大于n时，效率较低

计数排序的优缺点

计数排序的适用场景

• 排序的元素都是整数
• 元素的范围不是很大，最好与元素数量接近
• 需要稳定排序算法的场景
• 作为基数排序的子过程使用
• 数据量大但取值范围有限的场景，如学生成绩排序(0-100分)

计数排序的Python实现

基础实现

def counting_sort(arr):
    # 如果数组为空，直接返回
    if not arr:
        return []
    
    # 找出数组中的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)
    
    # 创建计数数组，初始化为0
    count = [0] * (max_val - min_val + 1)
    
    # 统计每个元素出现的次数
    for num in arr:
        count[num - min_val] += 1
    
    # 计算累积和
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 创建输出数组
    output = [0] * len(arr)
    
    # 反向填充输出数组，保证稳定性
    for num in reversed(arr):
        index = count[num - min_val] - 1
        output[index] = num
        count[num - min_val] -= 1
    
    return output

# 示例使用
arr = [4, 2, 2, 8, 3, 3, 1]
print("原始数组:", arr)
sorted_arr = counting_sort(arr)
print("排序后数组:", sorted_arr)

代码说明

1. 找出数组中的最大值和最小值，以减小计数数组的大小
2. 创建计数数组，统计每个元素出现的次数
3. 将计数数组转换为累积计数数组
4. 反向遍历原数组，根据累积计数数组将元素放入正确位置
5. 反向遍历保证了排序的稳定性（相同元素的相对位置不变）

示例输出

原始数组: [4, 2, 2, 8, 3, 3, 1]
排序后数组: [1, 2, 2, 3, 3, 4, 8]

总结

计数排序是一种高效的非比较型整数排序算法，特别适用于数据范围不大的场景。它的主要优势在于线性时间复杂度和稳定性，但缺点是只能用于整数排序且需要额外的内存空间。

在实际应用中，当排序的元素都是整数且范围较小时，计数排序是一个很好的选择。它常被用作基数排序的子过程，或用于需要稳定排序的特殊场景。

理解计数排序的原理对于学习更复杂的排序算法（如基数排序、桶排序）非常有帮助，也是算法学习中的重要一步。