计数排序python
时间: 2023-06-21 10:18:36 浏览: 47
计数排序(Counting Sort)是一种非基于比较的排序算法,其时间复杂度为O(n+k),其中n是待排序元素的个数,k是待排序元素的最大值与最小值之差加1。计数排序的核心思想是确定每个元素之前有多少个元素小于它。
以下是Python实现计数排序的代码:
```python
def counting_sort(arr):
# 找到最大值和最小值
min_val = min(arr)
max_val = max(arr)
# 计数数组
count = [0] * (max_val - min_val + 1)
# 统计每个元素的个数
for i in arr:
count[i - min_val] += 1
# 统计前缀和
for i in range(1, len(count)):
count[i] += count[i - 1]
# 排序结果数组
res = [0] * len(arr)
# 填充排序结果数组
for i in arr:
res[count[i - min_val] - 1] = i
count[i - min_val] -= 1
return res
```
其中,min_val和max_val是输入数组arr中的最小值和最大值。首先,创建一个计数数组count,其长度为max_val - min_val + 1,用于统计每个元素出现的次数。然后,遍历输入数组arr,统计每个元素出现的个数。接下来,计算count数组的前缀和,以便确定每个元素在排序结果数组中的位置。最后,遍历输入数组arr,将每个元素放入排序结果数组res中。
示例:
```python
arr = [5, 2, 3, 1, 4, 5, 2, 3, 1, 4]
print(counting_sort(arr)) # [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
```