Python 计数排序（建议收藏）

什么是 Python 计数排序？

在学习排序算法的过程中，我们常常会遇到冒泡排序、快速排序、归并排序这些“老熟人”。但如果你正在处理的是一个范围有限、数值重复较多的数据集，那么有一个效率极高但使用场景受限的算法，值得你深入了解——Python 计数排序。

计数排序不是基于比较的排序算法，它的核心思想是：“用空间换时间”。当我们要排序的数据范围较小（比如 0 到 100），且数据类型为整数时，它能实现 O(n + k) 的时间复杂度，远超大多数基于比较的排序。

想象一下：你有一堆颜色各异的球，但颜色只有红、黄、蓝三种。你不需要一个一个比较，而是直接数一数每种颜色有几个，然后按顺序排列。这个过程，就是计数排序的直观体现。

Python 计数排序正是利用了这种“计数+重排”的机制，特别适合处理整数数据，尤其是当最大值与最小值之差不大的时候。它的优势在于稳定、高效，但代价是需要额外的内存空间。

Python 计数排序的原理详解

要理解 Python 计数排序，先从它的基本逻辑入手。

假设我们有一个整数数组：[4, 2, 2, 8, 3, 3, 1]，我们要将它从小到大排序。

1. 找出数据范围：最小值是 1，最大值是 8。
2. 创建计数数组：长度为 max - min + 1 = 8，即索引 0 到 7，对应数值 1 到 8。
3. 遍历原数组，统计每个数字出现的次数：比如数字 2 出现了 2 次，就在计数数组的索引 1（即 2 - 1）位置加 1。
4. 累计计数：把计数数组变成“前缀和”形式，这样每个位置的值表示小于等于该数字的元素个数。
5. 构建结果数组：从后往前遍历原数组，根据计数数组的值确定每个元素在结果中的位置，然后更新计数。

这个过程看似复杂，但一旦理解，你会发现它非常直观。尤其适合“数据范围小、重复多”的场景。

实现 Python 计数排序的完整代码

下面是一个完整的 Python 实现，包含详细注释，帮助你逐行理解。

def counting_sort(arr):
    # 如果数组为空或只有一个元素，直接返回
    if not arr or len(arr) <= 1:
        return arr

    # 步骤1：找出数组中的最小值和最大值
    min_val = min(arr)
    max_val = max(arr)

    # 步骤2：创建计数数组，长度为 max - min + 1
    # 例如：min=1, max=8，则计数数组长度为 8，索引 0~7 对应值 1~8
    count = [0] * (max_val - min_val + 1)

    # 步骤3：遍历原数组，统计每个数字的出现次数
    for num in arr:
        count[num - min_val] += 1  # 数字 num 在计数数组中的索引是 num - min_val

    # 步骤4：将计数数组转换为前缀和数组
    # 使得 count[i] 表示小于等于 i + min_val 的元素个数
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 步骤5：创建结果数组，长度与原数组相同
    result = [0] * len(arr)

    # 步骤6：从后往前遍历原数组，确保排序稳定
    # 为什么从后往前？防止相同元素的相对顺序被打乱
    for i in range(len(arr) - 1, -1, -1):
        num = arr[i]
        # 找到该数字在结果数组中的位置
        pos = count[num - min_val] - 1  # 减1是因为 count 是从1开始计数的
        result[pos] = num
        # 更新计数数组，表示这个数值的下一个位置
        count[num - min_val] -= 1

    # 返回排序后的数组
    return result

💡 关键点说明：

• count[num - min_val]：将数值映射到计数数组的索引，是核心技巧。
• 从后往前遍历保证了稳定性（相同元素的相对顺序不变）。
• 时间复杂度：O(n + k)，n 是数组长度，k 是数值范围。
• 空间复杂度：O(k)，需要额外的计数数组。

Python 计数排序的实际案例演示

让我们用一个真实场景来测试这个算法。假设你是一名学校老师，要对 30 名学生的考试成绩进行排序，成绩范围是 0 到 100。

scores = [85, 92, 78, 92, 85, 90, 78, 85, 88, 92, 75, 80, 85, 90, 78, 82, 85, 92, 78, 80]

print("原始分数：", scores)
sorted_scores = counting_sort(scores)
print("排序后分数：", sorted_scores)

输出结果为：

原始分数： [85, 92, 78, 92, 85, 90, 78, 85, 88, 92, 75, 80, 85, 90, 78, 82, 85, 92, 78, 80]
排序后分数： [75, 78, 78, 78, 78, 80, 80, 82, 85, 85, 85, 85, 85, 88, 90, 90, 92, 92, 92, 92]

可以看到，Python 计数排序不仅完成了排序，还保持了相同分数的原始顺序（稳定排序）。这对需要“按分数排序，相同分数按入学时间排列”的场景非常友好。

Python 计数排序的适用场景与局限性

Python 计数排序不是万能的，它有明确的使用边界。我们来分析一下它的适用与不适用场景。

📌 建议：当你处理的是“学生分数、年龄、等级编号”这类整数、范围有限的数据时，Python 计数排序是首选方案。

与其它排序算法的对比分析

为了更清楚地理解 Python 计数排序的优势，我们和常见的排序算法做个对比：

从表格可以看出，Python 计数排序在满足条件时，性能远超其他算法。比如当 n = 1000，k = 100 时，计数排序只需约 1100 次操作，而快速排序通常需要 10000 次以上。

但代价是：如果 k 是 1000000，那计数数组就要 100 万个位置，内存消耗巨大。

如何优化 Python 计数排序的性能？

虽然 Python 计数排序本身已经很高效，但仍有优化空间。以下是一些实用建议：

1. 使用 array 模块替代列表
   对于大数组，list 的内存开销较大。可以改用 array.array('i')，更节省空间。

2. 避免重复调用 min() 和 max()
   如果你多次排序同一组数据，可以提前计算并缓存 min 和 max。

3. 处理负数的技巧
   如果数组包含负数，只需调整偏移量即可。例如：index = num - min_val，min_val 可能是负数，但依然有效。

   # 示例：处理负数
   arr = [-3, -1, 0, 2, -1, 1]
   min_val = -3
   max_val = 2
   count = [0] * (max_val - min_val + 1)  # 长度 6，索引 0~5 对应 -3~2
   

4. 对极小范围使用内置排序
   当 k 很小（如 k < 10），直接用 sorted() 甚至更快，因为 Python 内置排序（Timsort）在小数组上表现极佳。

总结与学习建议

Python 计数排序是一个“高效率但有门槛”的算法。它不适用于所有场景，但一旦用对地方，它的性能几乎无与伦比。

作为开发者，我们不必记住所有算法，但要理解它们的适用边界。就像一把瑞士军刀，每种工具都有自己的用武之地。Python 计数排序就是那个专为“小范围整数排序”而生的利器。

建议你在学习过程中：

• 动手写一遍代码，不要只看。
• 用不同数据测试，比如含负数、重复多、范围大等。
• 与 sorted() 比较性能，感受“空间换时间”的威力。

当你能在合适的场景中准确使用 Python 计数排序，说明你已经从“写代码”迈入了“设计算法”的阶段。这才是真正的成长。

最后，别忘了：算法的本质，不是复杂，而是精准。