第18课：计数排序 - 当比较不再是瓶颈

所属模块：排序算法
难度：intermediate
标签：counting-sort, non-comparison, stable
上一课：堆排序
下一课：基数排序

学习目标

学完本课，你将能够：

理解计数排序通过“统计频率”而非“比较”来排序的核心思想。
实现一个稳定且能处理包含负数的计数排序算法。
分析计数排序的时间复杂度与空间复杂度，并明确其适用场景。
区分计数排序与其他基于比较的排序算法（如快速排序、归并排序）的根本不同。
应用计数排序的思想解决相关问题，如计算元素排名或统计特定范围内的频率。

核心概念

我们先来一个生动的比喻：想象一次选举，有5个候选人（A, B, C, D, E）。我们不需要让所有候选人互相比较，而是准备一个表格，统计每个候选人获得了多少票。最后，根据票数，按顺序（比如从A到E）将候选人名单写出来。这就是计数排序的精髓。

核心思想：计数排序是一种非比较排序。它不直接比较元素的大小，而是利用数组下标来确定元素的正确位置。

工作流程：

统计频率：找出待排序数组arr中的最小值min和最大值max。创建一个长度为(max - min + 1)的计数数组count，初始值全为0。遍历arr，将count[arr[i] - min]的值加1。
计算前缀和：对计数数组count进行累加（前缀和），使得count[i]存储了小于等于i + min的元素总数。这个步骤是稳定排序的关键。
反向填充输出：创建一个与arr等长的输出数组output。反向遍历原数组arr，对于每个元素arr[i]，根据其值找到在count数组中的累计个数，将其放入output的正确位置，然后将count中对应的值减1。反向遍历保证了原数组中相同元素的相对顺序得以保持。

为什么是稳定的？稳定性是指相等的元素在排序后保持原有的相对顺序。通过先统计所有元素，在“反向填充”阶段从后往前遍历原数组，可以确保先出现的相同元素被放置在输出数组更靠前的位置，从而维持稳定性。

适用场景与限制：

最佳场景：待排序元素是整数，且范围(max - min)不是特别大（即k较小）。
时间复杂度：O(n + k)，其中n是元素个数，k是整数的范围。
空间复杂度：O(n + k)，需要额外的计数数组和输出数组。
局限性：当数据范围k远大于元素个数n时，空间和时间开销可能不划算。它通常用于为其他算法（如基数排序）服务。

代码示例

下面是一个完整、可运行且能处理负数的Python实现，并附有详细注释。

def counting_sort(arr):
    """
    实现一个稳定的计数排序算法，能够处理包含负数的数组。
    
    参数:
    arr: 待排序的整数列表。
    
    返回:
    排序后的新列表。
    """
    if not arr: # 边界情况处理：空列表
        return []
    
    # 1. 找到最小值和最大值，确定计数数组的范围
    min_val = min(arr)
    max_val = max(arr)
    
    # 2. 初始化计数数组，长度为值域范围 (max_val - min_val + 1)
    # count[i] 对应的数值是 i + min_val
    count_len = max_val - min_val + 1
    count = [0] * count_len
    
    # 3. 统计每个值出现的频率
    for num in arr:
        count[num - min_val] += 1  # 核心：用 (值 - 最小值) 作为索引
    
    # 4. 计算前缀和（累加），count[i] 表示 <= (i+min_val) 的元素总数
    for i in range(1, count_len):
        count[i] += count[i - 1]
    
    # 5. 创建输出数组，并反向遍历原数组进行填充（保证稳定性）
    output = [0] * len(arr)
    # 从后向前遍历原数组
    for i in range(len(arr) - 1, -1, -1):
        num = arr[i]
        # count[num - min_val] 的值是当前值（及更小值）在输出数组中的“终点”索引（从1开始计数）
        # 因此，元素的正确位置索引是 count[num - min_val] - 1
        pos = count[num - min_val] - 1
        output[pos] = num
        count[num - min_val] -= 1 # 放入一个，计数减一，为下一个相同值准备位置
    
    return output

# 测试代码
if __name__ == "__main__":
    test_array1 = [4, 2, 2, 8, 3, 3, 1]
    print(f"原始数组: {test_array1}")
    sorted_array1 = counting_sort(test_array1)
    print(f"排序结果: {sorted_array1}")  # 输出应为 [1, 2, 2, 3, 3, 4, 8]
    
    test_array2 = [-5, 0, 3, -2, 1, 4, -1, 2]
    print(f"\n原始数组(含负数): {test_array2}")
    sorted_array2 = counting_sort(test_array2)
    print(f"排序结果: {sorted_array2}")  # 输出应为 [-5, -2, -1, 0, 1, 2, 3, 4]

代码关键点解析：

处理负数：通过计算min_val和max_val，并用(num - min_val)作为索引，巧妙地将任意范围的整数映射到计数数组的连续下标[0, count_len-1]中。
前缀和的作用：在填充输出前，count[i]的值代表了小于等于(i + min_val)的元素个数。这个值直接可以作为（在考虑稳定性后）最后一个等于(i+min_val)的元素在输出数组中应放置的下一个位置（即终点）。
反向填充保证稳定：反向遍历确保了对于相同的数值，后出现的元素先被放置到输出数组的“终点”前一个位置，从而使得先出现的元素总是在更靠前的位置。

实践练习

练习 1：修改算法（基础） 修改上述counting_sort函数，使其能够处理元素为字符串的情况。字符串按照其对应的ASCII码值进行排序。（提示：你需要找到字符的最小和最大ASCII值，计数数组的索引直接使用ord(char)即可，无需偏移）。

输入: ['banana', 'apple', 'cherry', 'date']
预期输出: ['apple', 'banana', 'cherry', 'date']

练习 2：应用思想（进阶） 给定一个长度为n的整数数组nums，其中每个元素的值都在[0, n-1]的范围内。请仅使用常量级别的额外空间（即O(1)），找出数组中重复的元素。（提示：能否利用给定的值域和数组下标的关系，巧妙地“标记”元素？）

输入: nums = [2, 3, 1, 0, 2, 5, 3]
预期输出: 2 或 3 (返回任意一个重复元素即可)

练习 3：综合应用（挑战） 你有一个包含学生考试成绩（0-100的整数）的列表。你需要按照成绩从低到高排序，但对于成绩相同的学生，必须保持他们名单中原来的顺序。请你手动实现计数排序来完成此任务，不要直接调用语言内置的稳定排序函数。

输入: scores = [85, 70, 90, 70, 60, 85, 95]
预期输出: [60, 70, 70, 85, 85, 90, 95] (注意两个70和两个85都保持了原顺序)

常见错误

计数数组大小错误：最常见的错误是将计数数组的长度设置为max_val + 1（当数组包含负数时会下标越界）或max_val - min_val（少1个位置）。记住是max_val - min_val + 1。
- 错误示例：count = [0] * (max_val + 1) 对于输入[-1, 2]会失败，因为索引-1无效。
- 正确做法：必须引入min_val进行偏移。
忘记保证稳定性：如果按照正序遍历原数组进行填充，或者省略了计算前缀和的步骤，排序结果将失去稳定性。
- 错误示例：
```
# 错误的正向填充
for num in arr: # 正序遍历
    pos = count[num - min_val] # 使用的是原始频率，不是前缀和后的索引
    output[pos] = num
    count[num - min_val] += 1
```
- 正确做法：必须先计算前缀和，然后反向遍历原数组。
不理解前缀和的意义：初学者可能困惑“为什么需要前缀和这一步？”没有它，count[i]仅代表值i出现的次数，你无法直接知道一个值应该放在输出数组的哪个具体位置。前缀和将“频率”转换成了“位置范围”信息。

小结

计数排序是一种非比较排序算法，通过统计元素出现的频率来确定其最终位置。
关键步骤：统计频率 -> 计算前缀和 -> 反向填充输出数组。
核心优势：时间复杂度为O(n + k)，在数据范围k较小时，效率远超基于比较的O(n log n)算法。它是一种稳定的排序算法。
主要限制：空间复杂度为O(n + k)，当范围k非常大时，空间开销巨大，不切实际。它通常只适用于整数排序。
应用场景：常用于基数排序的子过程，或当问题特征明确符合其优势时（如数据密集、范围不大、需要稳定排序）。
实现关键：通过min_val偏移来处理负数；通过前缀和与反向填充共同保证排序的稳定性和正确性。

掌握了计数排序，你就为理解下一课更强大的基数排序打下了坚实的基础！

练习编辑器

rust