计数排序

概述

计数排序（Counting Sort）是一种稳定的线性时间排序算法，通过统计元素出现次数实现排序。其时间复杂度为$O(n+k)$（$k$为数据范围），空间复杂度为$O(n+k)$，适用于已知数据范围的整数排序。

核心思想

1. 统计频率：统计每个元素出现的次数
2. 计算位置：计算每个元素在输出数组中的最终位置
3. 反向填充：根据统计结果将元素放入正确位置

算法步骤

输入与输出

• 输入：包含$n$个整数的数组arr，整数范围为$[0,k]$
• 输出：排序后的数组

详细步骤

1. 初始化计数数组：创建长度为$k+1$的数组count，初始值为0 2. 统计元素频率：遍历输入数组，记录每个元素出现次数 3. 计算累积频次：将count数组转换为元素最后出现的位置索引 4. 反向填充结果数组：从后向前遍历输入数组，根据count数组确定元素位置

flowchart TD A[输入数组 arr] --> B[创建计数数组 count] B --> C[统计元素频率] C --> D[计算累积频次] D --> E[反向填充结果数组] E --> F[输出排序数组]

代码实现

Python示例

def counting_sort(arr):
    if not arr:
        return []
    
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)
    
    # 统计元素出现次数
    for num in arr:
        count[num] += 1
    
    # 计算累积频次
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 反向填充结果数组（保证稳定性）
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
sorted_arr = counting_sort(arr)
print("排序后:", sorted_arr)

关键点说明

• 稳定性：反向填充保证相同元素的原始顺序不变
• 边界处理：空数组直接返回
• 空间优化：可改为原地排序（但会失去稳定性）

复杂度分析

时间复杂度对比

情况	时间复杂度
最优情况	$O(n+k)$
最差情况	$O(n+k)$
平均情况	$O(n+k)$

• 空间复杂度：$O(n+k)$（结果数组+计数数组）
• 稳定性：稳定（实现正确时）

应用场景

适用情况

1. 数据范围为已知有限整数 2. 需要稳定排序的场景 3. 数据量大但范围小的场景（如年龄排序）

实际案例

学生成绩排序：假设有10万名学生，成绩范围为0-100分：

# 生成随机成绩（示例）
import random
grades = [random.randint(0, 100) for _ in range(100000)]
sorted_grades = counting_sort(grades)  # 比快速排序快3倍

变体与优化

负数支持

通过偏移量处理负数：

def counting_sort_with_negative(arr):
    min_val = min(arr)
    max_val = max(arr)
    offset = -min_val
    count = [0] * (max_val - min_val + 1)
    
    for num in arr:
        count[num + offset] += 1
    
    # 其余步骤相同...

空间优化版

减少计数数组大小（需多次遍历）：

def counting_sort_optimized(arr):
    if not arr:
        return []
    
    min_val = min(arr)
    max_val = max(arr)
    count = [0] * (max_val - min_val + 1)
    
    for num in arr:
        count[num - min_val] += 1
    
    # 直接展开计数数组
    result = []
    for i in range(len(count)):
        result.extend([i + min_val] * count[i])
    
    return result

与其他算法对比

排序算法对比（k为数据范围）

算法	平均时间复杂度	稳定性	适用场景
计数排序	$O(n+k)$	稳定	小范围整数
快速排序	$O(n\log n)$	不稳定	通用排序
归并排序	$O(n\log n)$	稳定	大数据量

常见问题

Q1: 为什么计数排序不是比较排序？

计数排序通过统计元素出现次数而非比较元素大小来排序，因此不受$O(n\log n)$比较排序下限限制。

Q2: 如何处理浮点数排序？

可将浮点数乘以精度系数转为整数（如两位小数×100），但会显著增加$k$值，通常不推荐。

总结

计数排序在特定场景（小范围整数）下效率极高，但需注意：

• 仅适用于离散整数
• 数据范围过大会导致内存消耗剧增
• 稳定性取决于实现方式