编辑“︁计数排序”︁

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

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

=== 数学表示 ===  
对于输入数组<math>A</math>，输出数组<math>B</math>，计数数组<math>C</math>：  
* 统计频率：<math>C[A[i]] = C[A[i]] + 1</math>  
* 前缀和：<math>C[i] = C[i] + C[i-1]</math>  
* 填充输出：<math>B[C[A[j]] - 1] = A[j]</math>  

== 示例代码 ==  
以下是用[[Python]]实现的计数排序代码：  
<syntaxhighlight lang="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)  
</syntaxhighlight>  

'''输出结果'''：  
<pre>  
排序前: [4, 2, 2, 8, 3, 3, 1]  
排序后: [1, 2, 2, 3, 3, 4, 8]  
</pre>  

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

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

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

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

== 可视化示例 ==  
<mermaid>  
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  
</mermaid>  

== 与其他排序算法对比 ==  
* '''对比快速排序'''：计数排序无需比较，但仅适用于有限范围整数。  
* '''对比桶排序'''：计数排序是桶大小为1的特例。  

== 扩展阅读 ==  
* [[基数排序]]：利用计数排序作为稳定子过程处理多关键字排序。  
* [[桶排序]]：将数据分到有限数量的桶中再分别排序。  

{{算法导航}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]