counting sort python
时间: 2023-04-21 14:07:01 浏览: 70
计数排序是一种非比较排序算法,它的时间复杂度为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
相关问题
python sort 时间复杂度
Python的排序算法的时间复杂度可以根据具体的实现方式有所不同。下面是几种常见的排序算法及其时间复杂度:
1. 冒泡排序(Bubble Sort):最坏情况下的时间复杂度为O(n^2),平均情况下的时间复杂度也为O(n^2)。
2. 选择排序(Selection Sort):最坏情况下的时间复杂度为O(n^2),平均情况下的时间复杂度也为O(n^2)。
3. 插入排序(Insertion Sort):最坏情况下的时间复杂度为O(n^2),平均情况下的时间复杂度也为O(n^2)。
4. 快速排序(Quick Sort):最坏情况下的时间复杂度为O(n^2),平均情况下的时间复杂度为O(nlogn)。
5. 归并排序(Merge Sort):最坏情况下的时间复杂度为O(nlogn),平均情况下的时间复杂度也为O(nlogn)。
6. 堆排序(Heap Sort):最坏情况下的时间复杂度为O(nlogn),平均情况下的时间复杂度也为O(nlogn)。
7. 希尔排序(Shell Sort):最坏情况下的时间复杂度取决于增量序列的选择,平均情况下的时间复杂度为O(n^1.3)。
8. 计数排序(Counting Sort):时间复杂度为O(n+k),其中k是待排序数组中的最大值。
9. 桶排序(Bucket Sort):时间复杂度为O(n+k),其中k是桶的数量。
10. 基数排序(Radix Sort):时间复杂度为O(d(n+k)),其中d是数字的位数,k是每个位数可能的取值范围。
需要注意的是,这些排序算法的时间复杂度都是基于比较的排序算法。非基于比较的排序算法,例如计数排序、桶排序和基数排序,可以在特定情况下达到线性时间复杂度。
python 计数排序
计数排序(Counting Sort)是一种非比较型整数排序算法,它对输入的数据进行计数,然后根据计数值直接输出排序结果。计数排序适用于数据规模较小且数据分布均匀的情况,它的时间复杂度为O(n+k),其中n是输入数据的数量,k是输入数据的最大值。
在Python中实现计数排序的代码示例如下:
```python
def counting_sort(arr):
# 确定最大值和计数数组的长度
max_val = max(arr)
count_len = max_val + 1
# 初始化计数数组
count = * count_len
# 统计每个元素出现的次数
for num in arr:
count[num] += 1
# 计算每个元素应该放置的位置
for i in range(1, count_len):
count[i] += count[i-1]
# 创建输出数组并排序
output = * len(arr)
for num in arr:
output[count[num]-1] = num
count[num] -= 1
return output
```
上述代码中,我们首先确定输入数组中的最大值,并根据最大值创建一个计数数组,长度为最大值加一。然后统计输入数组中每个元素出现的次数,并将计数结果存入计数数组。接下来,我们通过累加计数数组中的元素,计算每个元素应该放置的位置。最后,我们根据计数数组中的计数值和位置信息,将输入数组中的元素排序并输出。
使用计数排序算法对整数数组进行排序的时间复杂度为O(n+k),空间复杂度为O(n)。在Python中实现计数排序算法时,需要占用一定的额外空间来存储计数数组和输出数组。但是,计数排序算法的稳定性较好,适用于整数数组的排序。在实际应用中,需要根据具体的数据规模和分布情况选择合适的排序算法。