🧮 计数排序 (Counting Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 非比较排序 (Non-comparison Sort)
时间复杂度 / Time Complexity: O(n + k)
空间复杂度 / Space Complexity: O(k)

📖 算法简介 / Introduction

计数排序是一种非比较排序算法，通过统计每个元素出现的次数来排序。不是比较元素大小，而是用计数数组记录每个值出现的频率。

Counting sort is a non-comparison sorting algorithm that sorts by counting the occurrences of each value. Instead of comparing elements, it uses a count array to record the frequency of each value.

💡 算法原理 / Principle

1. 找到最大值：遍历数组，确定最大值 k
2. 创建计数数组：创建一个长度为 k+1 的计数数组，初始化为 0
3. 统计频率：遍历原数组，每遇到元素 val，就将 count[val] 加 1
4. 累加计数：将计数数组转换为前缀和（累加每个位置之前的总数）
5. 回填输出：根据累加后的计数，将元素放到正确位置

核心思想：用下标本身表示值，用计数表示频率

📝 代码实现 / Implementation

def counting_sort(arr):
    # 1. 找到最大值
    max_val = max(arr)
    
    # 2. 创建计数数组并统计频率
    count = [0] * (max_val + 1)
    for val in arr:
        count[val] += 1
    
    # 3. 累加计数（计算位置）
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 4. 回填输出数组
    output = [0] * len(arr)
    for val in arr:
        count[val] -= 1
        output[count[val]] = val
    
    return output

✨ 示例 / Example

输入数组：[4, 2, 2, 8, 3, 3, 1]

Step 1: 计数数组 (max_val=8)
count = [1, 0, 2, 2, 1, 0, 0, 0, 1]

Step 2: 累加计数
count = [1, 1, 3, 5, 6, 6, 6, 6, 7]

Step 3: 回填
元素 4 → 位置 6 → output[6] = 4
元素 2 → 位置 2 → output[2] = 2
...

最终输出：[1, 2, 2, 3, 3, 4, 8]

🎯 适用场景 / Scenarios

• 数据范围不大 — 适用于最大值 k 不太大的情况
• 整数排序 — 特别适合整数数组（年龄、成绩、排名等）
• 稳定排序 — 相等元素保持原有顺序
• 计数统计 — 可同时完成排序和频率统计

Integer sorting with bounded range, Scoring systems, Age/rank sorting, Frequency counting and sorting.

⚠️ 优缺点 / Pros & Cons

🔄 与其他排序对比 / Comparison