计数排序

计数排序（Counting Sort）是一种非基于比较的排序算法，适用于整数数据的线性时间排序。其核心思想是通过统计每个元素的出现次数，然后根据统计结果直接确定排序后的位置。计数排序的时间复杂度为$O(n+k)$，其中$n$是元素数量，$k$是数据范围大小。

算法原理

计数排序的步骤如下： 1. 统计频率：遍历输入数组，统计每个元素出现的次数，存入一个辅助数组（计数数组）。 2. 计算前缀和：将计数数组转换为前缀和形式，表示每个元素在排序后数组中的最后位置。 3. 反向填充：根据前缀和数组，将元素按顺序放入输出数组，同时更新前缀和以避免重复。

数学表示

对于输入数组$A$，输出数组$B$，计数数组$C$：

• 统计频率：$C[A[i]]=C[A[i]]+1$
• 前缀和：$C[i]=C[i]+C[i-1]$
• 填充输出：$B[C[A[j]]-1]=A[j]$

示例代码

以下是用Python实现的计数排序代码：

  
def counting_sort(arr):  
    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]  
sorted_arr = counting_sort(arr)  
print("排序前:", arr)  
print("排序后:", sorted_arr)

输出结果：

  
排序前: [4, 2, 2, 8, 3, 3, 1]  
排序后: [1, 2, 2, 3, 3, 4, 8]  

复杂度分析

• 时间复杂度：$O(n+k)$，其中$k$是数据范围。若$k=O(n)$，则复杂度为线性。
• 空间复杂度：$O(n+k)$，需要额外的计数数组和输出数组。
• 稳定性：计数排序是稳定的，因为反向填充保证了相同元素的相对顺序。

适用场景与限制

适用场景

1. 数据范围较小（如年龄、成绩等离散值）。 2. 需要稳定排序且数据为整数。 3. 作为基数排序的子过程。

限制

1. 仅适用于整数或可映射为整数的数据。 2. 数据范围过大时空间效率低。

实际案例

场景：某学校需要按学生成绩（0~100分）快速排序。 解决：使用计数排序，统计每个分数的学生人数后直接输出结果。

可视化示例

graph TD A[输入数组: 4, 2, 2, 8, 3, 3, 1] B[计数数组: 0,1,2,2,1,0,0,0,1] C[前缀和: 0,1,3,5,6,6,6,6,7] D[输出数组: 1,2,2,3,3,4,8] A -->|统计频率| B B -->|计算前缀和| C C -->|反向填充| D

与其他排序算法对比

• 对比快速排序：计数排序无需比较，但仅适用于有限范围整数。
• 对比桶排序：计数排序是桶大小为1的特例。

扩展阅读

• 基数排序：利用计数排序作为稳定子过程处理多关键字排序。
• 桶排序：将数据分到有限数量的桶中再分别排序。