手写算法并记住它：计数排序的核心实践

计数排序（Counting Sort）是一种非比较型整数排序算法，其核心思想是通过统计每个元素出现的次数，将排序问题转化为对计数数组的遍历和重构。相比基于比较的排序算法（如快速排序、归并排序），计数排序的时间复杂度可降至O(n+k)，其中k为数据范围。本文将从原理剖析、代码实现、优化技巧三个维度展开，帮助开发者通过手写算法加深理解并形成长期记忆。

一、计数排序的原理与适用场景

1.1 算法核心思想

计数排序通过三个步骤完成排序：

1. 统计频率：创建一个计数数组count，索引对应待排序数组的值，存储该值出现的次数。
2. 计算前缀和：将count数组转换为前缀和形式，表示每个元素在排序后数组中的最终位置。
3. 反向填充：从后向前遍历待排序数组，根据count数组确定元素位置，避免相同元素的相对顺序错乱（稳定性）。

示例：对数组[4, 2, 2, 8, 3, 3, 1]排序：

• 统计频率：count = [0, 1, 2, 2, 1, 0, 0, 0, 1]（索引0-8）
• 计算前缀和：count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
• 反向填充：结果为[1, 2, 2, 3, 3, 4, 8]

1.2 适用场景分析

计数排序的效率高度依赖数据特征：

• 整数限制：仅适用于整数或可映射为整数的数据（如字符的ASCII码）。
• 数据范围：当数据范围k远大于元素数量n时（如k=1e6，n=100），空间复杂度O(k)会成为瓶颈。
• 稳定性需求：需保持相同元素的原始顺序时，反向填充步骤至关重要。

典型应用：

• 年龄排序（范围0-150）
• 考试分数分组（范围0-100）
• 离散化后的数据排序

二、手写计数排序的完整实现

2.1 Python基础实现

def counting_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    count = [0] * (max_val + 1)
    # 统计频率
    for num in arr:
        count[num] += 1
    # 计算前缀和（确定位置）
    for i in range(1, len(count)):
        count[i] += count[i-1]
    # 反向填充（保持稳定性）
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    return output

2.2 关键步骤解析

1. 初始化计数数组：大小需覆盖数据最大值，避免索引越界。
2. 频率统计优化：可并行统计以提升大规模数据性能。
3. 前缀和计算：count[i]表示≤i的元素总数，即i在排序数组中的右边界。
4. 反向填充逻辑：从后向前处理保证相同元素的原始顺序。

2.3 边界条件处理

• 空数组：直接返回空列表。
• 负数处理：需通过偏移量转换（如将[-5, 3]映射为[0, 8]）。
• 大范围数据：当k>1e6时，建议改用基于比较的排序。

三、计数排序的优化与变体

3.1 空间优化技巧

• 动态范围检测：通过min(arr)和max(arr)确定实际数据范围，减少计数数组大小。

  def optimized_counting_sort(arr):
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    output = []
    for i in range(len(count)):
        output.extend([i + min_val] * count[i])
    return output  # 非稳定版本，适用于无稳定性需求场景

3.2 稳定性增强方案

• 双计数数组法：使用两个计数数组分别统计频率和位置，避免反向填充。
• 索引映射表：对非连续整数（如学号）建立哈希映射，转换为连续索引。

3.3 混合排序策略

当数据范围较大但存在局部密集区间时，可结合计数排序与快速排序：

1. 对数据分桶（如按十位数分组）。
2. 对每个桶内数据使用计数排序。
3. 合并桶结果。

四、记忆方法与学习建议

4.1 算法记忆技巧

1. 可视化流程：用纸笔模拟小规模数据（如[2,1,3,2]）的排序过程。
2. 代码模板化：将计数排序分为统计、前缀和、填充三段，形成固定代码结构。
3. 对比记忆：与桶排序、基数排序对比，明确计数排序的独特性（依赖数据范围）。

4.2 实践建议

1. LeetCode题目：完成第164题（最大间距）、第75题（颜色分类）等变体题。
2. 性能测试：对比计数排序与内置sorted()函数在整数列表上的性能差异。
3. 工程应用：在用户年龄统计、日志级别分类等场景中实践。

五、常见误区与纠正

5.1 误区一：忽略数据范围

错误示例：对范围0-1e6的100个元素直接使用计数排序，导致内存溢出。
纠正：先检测数据范围，若k/n>100则改用其他算法。

5.2 误区二：稳定性破坏

错误示例：正向填充导致相同元素顺序颠倒。
纠正：必须反向填充或使用双计数数组保证稳定性。

5.3 误区三：负数处理缺失

错误示例：直接对含负数的数组统计频率，引发索引错误。
纠正：通过num - min_val偏移量转换。

六、总结与扩展

计数排序通过线性时间复杂度和稳定性优势，在特定场景下优于比较排序。开发者需掌握：

1. 核心三步：统计、前缀和、反向填充。
2. 适用条件：整数、小范围、稳定性需求。
3. 优化方向：动态范围检测、混合排序策略。

进一步学习可探索：

• 基数排序（多关键字排序）
• 桶排序（分布均匀数据）
• 外部排序（大数据量场景）

通过手写代码、可视化模拟和工程实践，计数排序可成为开发者算法工具箱中的高效利器。