1.完成计数排序代码的实现
时间: 2024-04-30 15:22:56 浏览: 16
计数排序是一种非比较排序算法,它利用一个计数数组来记录每个元素出现的次数,然后根据计数数组将元素排列成有序序列。
以下是计数排序的代码实现:
```python
def counting_sort(arr):
n = len(arr)
if n <= 1:
return arr
# 找出数组中的最大值和最小值
min_val, max_val = min(arr), max(arr)
# 初始化计数数组
count = [0] * (max_val - min_val + 1)
# 计算每个元素出现的次数
for i in range(n):
count[arr[i] - min_val] += 1
# 计算每个元素在有序序列中的位置
for i in range(1, len(count)):
count[i] += count[i - 1]
# 将元素排序到有序序列中
sorted_arr = [0] * n
for i in range(n - 1, -1, -1):
index = count[arr[i] - min_val] - 1
sorted_arr[index] = arr[i]
count[arr[i] - min_val] -= 1
return sorted_arr
```
计数排序的时间复杂度为 O(n+k),其中 n 是数组的长度,k 是数组中不同元素的个数。计数排序的空间复杂度为 O(n+k)。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)