计数排序（Counting Sort）是一种非比较排序算法，适用于范围有限的整数序列排序。它的时间复杂度为 $O（n+k）$，其中 $n$ 是输入数据的大小，$k$ 是值的范围大小。
计数排序的基本思想
计数阶段：
统计每个元素出现的次数。
累加阶段：
根据统计数据，计算每个元素在排序后数组中的正确位置。
重构阶段：
将原数组中的元素按照计算的位置放入新数组。
计数排序适用场景
适用于整数排序。
数据范围 $k$ 不宜过大，否则空间消耗较高。
计数排序的步骤与代码实现
创建输入数据：
假设有一个整数数组 `[4, 2, 2, 8, 3, 3, 1]`。
统计每个数字的出现次数：
创建一个计数数组 `count`，数组的索引表示数字，值表示对应数字的出现次数。
构造累积计数：
累积计数数组可以帮助确定每个数字在排序结果中的正确位置。
根据累积计数构建排序结果：
从原数组中从右到左依次取数字，将其放置在累积计数数组对应位置，并将对应计数减 1。
Python代码实现
```python
def counting_sort(arr):
if not arr:
return []
找到数组中的最大值和最小值
max_val = max(arr)
min_val = min(arr)
创建计数数组，大小为最大值-最小值+1
count = * (max_val - min_val + 1)
填充计数数组
for num in arr:
count[num - min_val] += 1
通过计数数组构建结果
sorted_arr = []
for i, cnt in enumerate(count):
sorted_arr.extend([i + min_val] * cnt)
return sorted_arr
示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr) 输出: [1, 2, 2, 3, 3, 4, 8]
```
计数排序的优点
时间复杂度为 $O（n+k）$，在 $k$ 较小时表现优异。
稳定排序，能保持相同值的元素顺序不变。
计数排序的缺点
需要额外的空间存储计数数组和输出数组，空间复杂度为 $O（k）$。
不适合数据范围很大的场景。
总结
计数排序是一种高效的排序算法，特别适用于整数排序且数据范围有限的情况。尽管它需要额外的空间，但其时间复杂度使其在处理小规模数据时表现出色。