计数排序（Counting Sort）是一种非比较性排序算法，适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数，然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法，具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。
计数排序的工作原理
计数排序的基本思想是：
- 统计数组中每个元素出现的次数，得到元素的频率统计信息。
- 根据频率统计信息，重建有序数组。 计数排序的关键在于如何统计元素的频率以及如何重建有序数组。计数排序适用于整数排序，特别适用于有限范围内的整数排序。
下面是一个示例，演示计数排序的过程：
原始数组：[4, 2, 2, 8, 3, 3, 1]
- 统计数组中每个元素出现的次数，得到频率统计信息：{1: 1, 2: 2, 3: 2, 4: 1, 8: 1}。
- 根据频率统计信息，重建有序数组：[1, 2, 2, 3, 3, 4, 8]。
Python实现计数排序
下面是Python中的计数排序实现：
代码语言：javascript复制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进行计数排序的示例代码：
代码语言：javascript复制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 是元素范围的大小。计数排序是一种非比较性排序算法，适用于整数排序，特别适用于有限范围内的整数排序。
总之，计数排序是一种高效的非比较性排序算法，通过统计每个元素的频率，重建有序数组，实现了对整数数组的排序。了解计数排序有助于理解非比较性排序算法的思想，并为特定场景提供了一个高效的排序解决方案。
