编辑“︁计数排序”︁

{{Note|本文介绍的是非比较型整数排序算法——计数排序（Counting Sort），适用于数据范围较小的整数排序场景。}}

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

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

== 算法步骤 ==
=== 输入与输出 ===
* 输入：包含<math>n</math>个整数的数组<code>arr</code>，整数范围为<math>[0, k]</math>
* 输出：排序后的数组

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

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

== 代码实现 ==
=== Python示例 ===
<syntaxhighlight lang="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)
</syntaxhighlight>

{{Output|
<pre>
排序前: [4, 2, 2, 8, 3, 3, 1]
排序后: [1, 2, 2, 3, 3, 4, 8]
</pre>
}}

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

== 复杂度分析 ==
{| class="wikitable"
|+ 时间复杂度对比
! 情况 !! 时间复杂度
|-
| 最优情况 || <math>O(n + k)</math>
|-
| 最差情况 || <math>O(n + k)</math>
|-
| 平均情况 || <math>O(n + k)</math>
|}

* '''空间复杂度'''：<math>O(n + k)</math>（结果数组+计数数组）
* '''稳定性'''：稳定（实现正确时）

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

=== 实际案例 ===
'''学生成绩排序'''：假设有10万名学生，成绩范围为0-100分：
<syntaxhighlight lang="python">
# 生成随机成绩（示例）
import random
grades = [random.randint(0, 100) for _ in range(100000)]
sorted_grades = counting_sort(grades)  # 比快速排序快3倍
</syntaxhighlight>

== 变体与优化 ==
=== 负数支持 ===
通过偏移量处理负数：
<syntaxhighlight lang="python">
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
    
    # 其余步骤相同...
</syntaxhighlight>

=== 空间优化版 ===
减少计数数组大小（需多次遍历）：
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 与其他算法对比 ==
{| class="wikitable"
|+ 排序算法对比（k为数据范围）
! 算法 !! 平均时间复杂度 !! 稳定性 !! 适用场景
|-
| 计数排序 || <math>O(n + k)</math> || 稳定 || 小范围整数
|-
| 快速排序 || <math>O(n \log n)</math> || 不稳定 || 通用排序
|-
| 归并排序 || <math>O(n \log n)</math> || 稳定 || 大数据量
|}

== 常见问题 ==
=== Q1: 为什么计数排序不是比较排序？ ===
计数排序通过统计元素出现次数而非比较元素大小来排序，因此不受<math>O(n \log n)</math>比较排序下限限制。

=== Q2: 如何处理浮点数排序？ ===
可将浮点数乘以精度系数转为整数（如两位小数×100），但会显著增加<math>k</math>值，通常不推荐。

== 总结 ==
计数排序在特定场景（小范围整数）下效率极高，但需注意：
* 仅适用于离散整数
* 数据范围过大会导致内存消耗剧增
* 稳定性取决于实现方式

{{Warning|当<math>k \gg n</math>时（如排序[1, 1000000]），应优先选择比较排序算法}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]