COUNTING-SORT算法
时间: 2023-11-10 09:21:15 浏览: 58
COUNTING-SORT算法是一种稳定的排序算法,它的时间复杂度为O(n+k),其中n为待排序元素的个数,k为待排序元素中的最大值。
算法步骤:
1. 找出待排序元素中的最大值max,创建一个长度为max+1的计数数组count,并将每个元素的计数都初始化为0。
2. 遍历待排序数组,将每个元素在计数数组中对应的位置上加1。
3. 遍历计数数组,将每个元素的值更新为前一个元素的值加上当前元素的值。
4. 从待排序数组的末尾开始遍历,将每个元素在计数数组中对应的位置上的值减1,并将其放到排序数组的相应位置上。
5. 待排序数组就被排序完成了。
COUNTING-SORT算法的优点是具有线性时间复杂度,适用于排序范围比较小的数列。缺点是需要额外的存储空间,且只适用于非负整数排序。
相关问题
counting sort
计数排序(Counting Sort)是一种非比较排序算法,其时间复杂度为 O(n+k),其中 k 表示待排序数组中最大值与最小值之差加上 1。计数排序的基本思想是对于给定的输入序列中的每一个元素 x,确定该序列中值小于 x 的元素的个数,利用这一信息,就可以将 x 直接存放到最终的输出序列的正确位置上。
counting sort python
计数排序是一种非比较排序算法,它的时间复杂度为O(n+k),其中n是待排序元素的个数,k是待排序元素中最大值和最小值的差值加1。在Python中,可以使用以下代码实现计数排序:
def counting_sort(arr):
# 找到最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 初始化计数数组
count_arr = [] * (max_val - min_val + 1)
# 统计每个元素出现的次数
for i in arr:
count_arr[i - min_val] += 1
# 对计数数组进行前缀和操作
for i in range(1, len(count_arr)):
count_arr[i] += count_arr[i - 1]
# 初始化排序后的数组
sorted_arr = [] * len(arr)
# 从后往前遍历原数组,将元素放入排序后的数组中
for i in range(len(arr) - 1, -1, -1):
sorted_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
count_arr[arr[i] - min_val] -= 1
return sorted_arr
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)