Python算法——计数排序

计数排序（Counting Sort）是一种非比较性排序算法，适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数，然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法，具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。

计数排序的工作原理

计数排序的基本思想是：

1. 统计数组中每个元素出现的次数，得到元素的频率统计信息。
2. 根据频率统计信息，重建有序数组。 计数排序的关键在于如何统计元素的频率以及如何重建有序数组。计数排序适用于整数排序，特别适用于有限范围内的整数排序。

下面是一个示例，演示计数排序的过程：

原始数组：[4, 2, 2, 8, 3, 3, 1]

1. 统计数组中每个元素出现的次数，得到频率统计信息：{1: 1, 2: 2, 3: 2, 4: 1, 8: 1}。
2. 根据频率统计信息，重建有序数组：[1, 2, 2, 3, 3, 4, 8]。

Python实现计数排序

下面是Python中的计数排序实现：

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    # 初始化计数数组
    count = [0] * range_val

    # 统计元素频率
    for num in arr:
        count[num - min_val] += 1

    # 重建有序数组
    result = []
    for i in range(range_val):
        result.extend([i + min_val] * count[i])

    return result

• arr 是待排序的整数数组。
• max_val 和 min_val 分别是数组的最大值和最小值。
• range_val 表示元素范围的大小。
• 初始化计数数组 count，用于统计每个元素出现的次数。
• 统计元素频率，注意需要将元素减去最小值以适配计数数组。
• 重建有序数组，根据计数数组信息构建有序数组。

示例代码

下面是一个使用Python进行计数排序的示例代码：

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    count = [0] * range_val

    for num in arr:
        count[num - min_val] += 1

    result = []
    for i in range(range_val):
        result.extend([i + min_val] * count[i])

    return result

# 测试排序
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序后的数组:", sorted_arr)

时间复杂度

计数排序的时间复杂度为 O(n + k)，其中 n 是数组的长度，k 是元素范围的大小。计数排序是一种非比较性排序算法，适用于整数排序，特别适用于有限范围内的整数排序。

总之，计数排序是一种高效的非比较性排序算法，通过统计每个元素的频率，重建有序数组，实现了对整数数组的排序。了解计数排序有助于理解非比较性排序算法的思想，并为特定场景提供了一个高效的排序解决方案。