手写算法并记住它：计数排序

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

计数排序（Counting Sort）是一种非比较型整数排序算法，其核心思想通过统计每个元素出现的次数，将原始数据映射到计数数组中，最终按计数结果重建有序序列。与基于比较的排序算法（如快速排序、归并排序）不同，计数排序的时间复杂度为O(n+k)，其中n为元素数量，k为数据范围跨度。当k=O(n)时，计数排序可达到线性时间复杂度，显著优于O(nlogn)的比较型算法。

适用场景：

1. 数据范围较小且分布密集（如0-1000的整数）
2. 需要稳定排序（相同元素的相对顺序保持不变）
3. 对时间复杂度敏感的嵌入式系统或高频交易场景

典型应用案例包括DNA序列排序（碱基仅4种类型）、考试分数分段统计、图像像素值处理等。值得注意的是，计数排序不适用于浮点数或数据范围过大的场景，此时可考虑桶排序或基数排序。

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

1. 算法设计阶段

输入：待排序数组arr[0..n-1]，元素值范围[min, max]
输出：升序排列的新数组

关键步骤：

1. 初始化计数数组count[max-min+1]，所有元素置0
2. 遍历原始数组，统计每个元素的出现次数
3. 计算前缀和数组，确定每个元素的最终位置
4. 反向填充结果数组，保证稳定性

2. 代码实现（Python示例）

def counting_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1
    # 初始化计数数组
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1
    # 计算前缀和（确定位置）
    for i in range(1, range_size):
        count[i] += count[i-1]
    # 反向填充结果数组
    result = [0] * len(arr)
    for num in reversed(arr):
        pos = count[num - min_val] - 1
        result[pos] = num
        count[num - min_val] -= 1
    return result

3. 关键代码解析

• 范围计算：通过max_val - min_val + 1确定计数数组大小，避免空间浪费
• 前缀和处理：将计数数组转换为位置索引数组，例如原始计数[2,3,1]转换为[2,5,6]
• 反向遍历：从后向前处理原始数组，确保相同元素的原始顺序得以保留

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

1. 空间优化方案

当数据范围极大但实际有效值稀疏时，可采用哈希表替代固定大小的计数数组：

from collections import defaultdict
def sparse_counting_sort(arr):
    count = defaultdict(int)
    for num in arr:
        count[num] += 1
    sorted_keys = sorted(count.keys())
    result = []
    for key in sorted_keys:
        result.extend([key] * count[key])
    return result

2. 降序排序实现

修改前缀和计算方向即可实现降序：

def counting_sort_desc(arr):
    max_val, min_val = max(arr), min(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[max_val - num] += 1  # 反向计数
    result = []
    for i in range(len(count)-1, -1, -1):
        result.extend([max_val - i] * count[i])
    return result

3. 多关键字排序扩展

结合基数排序思想，可实现多字段排序。例如先按个位数排序，再按十位数排序：

def radix_counting_sort(arr, digit_pos):
    # digit_pos表示当前处理的位数（0=个位，1=十位...）
    mod = 10
    div = 10 ** digit_pos
    count = [0] * mod
    output = [0] * len(arr)
    for num in arr:
        digit = (num // div) % mod
        count[digit] += 1
    for i in range(1, mod):
        count[i] += count[i-1]
    for num in reversed(arr):
        digit = (num // div) % mod
        output[count[digit]-1] = num
        count[digit] -= 1
    return output

四、性能分析与边界条件处理

1. 时间复杂度详解

• 最佳情况：O(n+k)（当k≈n时）
• 最差情况：O(n+k)（数据均匀分布时）
• 空间复杂度：O(n+k)（需要额外存储计数数组和结果数组）

2. 稳定性保证机制

计数排序的稳定性取决于填充顺序：

• 正向遍历会破坏稳定性（后出现的相同元素会覆盖前面的位置）
• 反向遍历可确保稳定性（先处理后面的元素，将其放在高索引位置）

3. 常见错误处理

• 负数处理：需通过num - min_val将负数映射到正索引
• 空数组检查：应在算法开始时验证输入有效性
• 大数范围检测：当max_val-min_val超过内存限制时，应切换至外部排序

五、实际应用建议与学习路径

1. 练习建议：

   • 从固定范围数据（如0-99）开始练习
   • 逐步增加数据复杂度，包含负数、重复值
   • 对比计数排序与快速排序在不同数据分布下的性能

2. 工程应用：

   • 在数据库系统中用于索引字段排序
   • 结合哈希表实现高频词统计
   • 作为基数排序的子过程处理特定位数

3. 记忆技巧：

   • 联想”计数=统计次数”的核心操作
   • 记住”前缀和确定位置”的关键步骤
   • 通过”反向填充”保证稳定性的特性

计数排序作为线性时间复杂度的排序算法，在特定场景下具有不可替代的优势。通过手写实现并深入理解其原理，开发者不仅能掌握一种高效排序工具，更能培养对算法空间时间复杂度的分析能力。建议结合LeetCode相关题目（如164.最大间距、75.颜色分类）进行实战演练，巩固学习效果。