Python计数排序详解（手把手教你实现高效稳定的计数排序算法）

计数排序的适用场景

• 待排序数据为非负整数
• 数据范围（最大值 - 最小值）不太大
• 需要稳定排序（相同元素的相对位置不变）
• 追求线性时间复杂度的高性能排序

Python计数排序实现步骤

实现计数排序主要分为三步：

1. 统计频次：创建一个计数数组，记录每个数字出现的次数。
2. 累加计数（可选，用于稳定排序）：将计数数组转换为前缀和，表示小于等于当前值的元素个数。
3. 反向填充：从原数组末尾开始，根据计数数组确定每个元素在结果中的位置。

完整代码示例

下面是一个完整的、支持稳定排序的 Python计数排序 实现：

def counting_sort(arr):    if not arr:        return arr    # 找到最大值和最小值    min_val = min(arr)    max_val = max(arr)        # 创建计数数组，长度为 max_val - min_val + 1    range_of_elements = max_val - min_val + 1    count = [0] * range_of_elements        # 统计每个元素出现的次数    for num in arr:        count[num - min_val] += 1        # 将计数数组转换为前缀和（用于稳定排序）    for i in range(1, len(count)):        count[i] += count[i - 1]        # 创建输出数组    output = [0] * len(arr)        # 从后往前遍历原数组，保证稳定性    for i in range(len(arr) - 1, -1, -1):        num = arr[i]        pos = count[num - min_val] - 1        output[pos] = num        count[num - min_val] -= 1        return output# 测试示例if __name__ == "__main__":    data = [4, 2, 2, 8, 3, 3, 1]    sorted_data = counting_sort(data)    print("原始数组:", data)    print("排序后数组:", sorted_data)

代码解析

- 首先我们找出数组中的最小值和最大值，以确定计数数组的大小。

- 然后遍历原数组，统计每个数字出现的次数。

- 接着将计数数组转为前缀和，这样 count[i] 表示小于等于 i + min_val 的元素个数。

- 最后从后往前遍历原数组，将元素放入输出数组的正确位置，并更新计数，从而保证稳定排序算法的特性。

时间与空间复杂度

• 时间复杂度：O(n + k)，其中 n 是元素个数，k 是数据范围（max - min + 1）
• 空间复杂度：O(k)，需要额外的计数数组

总结

计数排序是一种高效的稳定排序算法，特别适合处理取值范围较小的整数数据。虽然它有使用限制，但在合适场景下性能远超快速排序、归并排序等 O(n log n) 算法。通过本篇Python排序教程，相信你已经掌握了计数排序的核心思想与实现方法。

关键词回顾：Python计数排序、计数排序算法、Python排序教程、稳定排序算法