Python 计数排序（长文讲解）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

计数排序：一种高效的非比较型排序算法

前言

在编程世界中，排序算法是数据处理的核心工具之一。无论是处理学生考试成绩、电商平台的商品库存，还是分析海量日志数据，排序都是优化效率的关键步骤。Python 提供了多种内置排序函数（如 sorted() 和 list.sort()），但了解底层排序算法的原理与实现方式，能帮助开发者在特定场景中选择最优方案。

本文将聚焦 Python 计数排序（Counting Sort），通过通俗易懂的讲解和代码示例，带读者深入理解这一算法的原理、实现步骤及实际应用场景。即使你对算法设计感到陌生，也能通过本文掌握这一高效工具的核心思想。

一、计数排序的基本原理

1.1 算法的核心思想

计数排序是一种典型的 非比较型排序算法，它通过统计元素出现的次数来实现排序，而非通过元素之间的比较。这一特性使其在特定场景下具有线性时间复杂度，远快于基于比较的传统算法（如快速排序或归并排序）。

想象一个图书馆管理员需要整理一排书籍，每本书都有唯一的编号。如果这些编号的范围较小（例如 1 到 100），管理员可以按以下步骤操作：

1. 统计每个编号的出现次数，例如编号 5 出现了 3 次，编号 8 出现了 1 次。
2. 根据统计结果重建有序序列，将编号按从小到大的顺序依次放置对应数量的书籍。

这就是计数排序的核心逻辑。

1.2 算法的适用场景

计数排序的优势在于：

• 元素范围有限：当待排序元素的值域（最大值与最小值的差）较小时，算法效率极高。
• 稳定排序：相同值的元素在排序后仍保持原有相对顺序。

但它的局限性也很明显：

• 不适用于浮点数或复杂对象：只能处理整数或可映射为整数的离散值。
• 空间消耗较大：需要额外内存来存储计数数组，可能不适合内存受限的场景。

二、计数排序的实现步骤

2.1 步骤分解

以一个整数列表 nums = [4, 2, 2, 8, 3, 3, 1] 为例，计数排序的具体步骤如下：

步骤 1：确定元素范围
找到数组中的最小值（min_val）和最大值（max_val）。

• min_val = 1
• max_val = 8
• 值域范围为 max_val - min_val + 1 = 8。

步骤 2：创建计数数组
初始化一个长度为值域范围的数组 count，初始值全为 0。

count = [0] * (max_val - min_val + 1)  

步骤 3：统计元素出现次数
遍历原始数组，对每个元素 num，将 count[num - min_val] 的值加 1。
例如，元素 2 出现两次，对应索引 2 - 1 = 1 的位置值变为 2。

步骤 4：累加计数数组
将计数数组转换为前缀和数组，使得每个位置的值表示该元素在最终排序后的结束位置。

for i in range(1, len(count)):  
    count[i] += count[i - 1]  

步骤 5：反向填充结果数组
从后往前遍历原始数组，根据计数数组确定每个元素的最终位置，并将计数数组对应位置减 1（确保稳定性）。

2.2 完整代码示例

def counting_sort(nums):  
    if not nums:  
        return []  

    min_val = min(nums)  
    max_val = max(nums)  
    count_range = max_val - min_val + 1  
    count = [0] * count_range  

    # 统计元素出现次数  
    for num in nums:  
        count[num - min_val] += 1  

    # 累加计数数组  
    for i in range(1, len(count)):  
        count[i] += count[i - 1]  

    # 反向填充结果数组  
    result = [0] * len(nums)  
    for num in reversed(nums):  
        idx = count[num - min_val] - 1  
        result[idx] = num  
        count[num - min_val] -= 1  

    return result  

nums = [4, 2, 2, 8, 3, 3, 1]  
print(counting_sort(nums))  # 输出：[1, 2, 2, 3, 3, 4, 8]  

三、时间与空间复杂度分析

3.1 时间复杂度

计数排序的时间复杂度为 O(n + k)，其中：

• n 是输入数组的长度。
• k 是值域的大小（max_val - min_val + 1）。

当 k 远小于 n 时（例如排序 0-9 的数字），时间复杂度接近 O(n)，效率极高；但若 k 接近 n 的平方（如排序 1e6 的随机数），则可能不如快速排序高效。

3.2 空间复杂度

计数排序的空间复杂度为 O(k)，需额外存储计数数组。这要求开发者需权衡内存开销与排序速度。

四、实际案例：学生成绩排序

4.1 场景描述

假设某班级有 100 名学生，成绩分布在 0 到 100 分之间。使用计数排序可快速生成成绩排名表。

4.2 代码实现

def sort_student_scores(scores):  
    min_score = 0  # 成绩最小值固定为 0  
    max_score = 100  
    count = [0] * (max_score - min_score + 1)  

    for score in scores:  
        count[score - min_score] += 1  

    # 累加计数数组后，生成排序后的列表  
    sorted_scores = []  
    for score in range(max_score, min_score - 1, -1):  
        count_val = count[score - min_score]  
        if count_val > 0:  
            sorted_scores.extend([score] * count_val)  
            count[score - min_score] = 0  

    # 逆序以升序排列  
    return sorted_scores[::-1]  

scores = [85, 92, 76, 85, 92, 68, 75]  
print(sort_student_scores(scores))  

4.3 优化点

在本例中，我们利用了成绩的固定值域（0-100），直接初始化计数数组，避免了动态计算 min/max 的开销。

五、计数排序与其他排序算法的对比

5.1 与快速排序的对比

5.2 与基数排序的关系

计数排序常作为基数排序（Radix Sort）的子过程，用于对每一位数字进行排序。例如，排序 100 以内的数字时，基数排序可分解为十位和个位的计数排序操作。

六、进阶技巧与注意事项

6.1 处理负数

若输入数组包含负数，需调整计数数组的索引计算。例如，假设 min_val = -5，则 num - min_val 的值始终为非负数。

6.2 优化空间使用

当值域较大但稀疏时（如大部分数值为 0，但最大值极大），可改用字典（hash map）替代数组存储计数，降低空间复杂度。

6.3 结合其他算法

在混合场景中，可将计数排序与其他算法结合。例如，先用计数排序处理整数部分，再用快速排序处理小数部分。

结论

Python 计数排序 是一种在特定场景下极具优势的排序算法，其线性时间复杂度使其成为处理小值域数据的利器。通过本文的讲解，读者应已掌握其核心原理、实现代码及优化技巧。

在实际开发中，开发者需根据数据特性灵活选择排序算法：若面对大量整数且值域有限，计数排序能显著提升性能；若数据无序且范围广泛，则需考虑快速排序或归并排序。

通过不断实践与对比分析，你将逐步构建起适合自己的算法工具箱，为复杂问题提供更高效的解决方案。