创建一个新列表,遍历计数列表,依次在新列表中添加对应数量的元素。0和1都是0个,不需要添加,2有两个,在新列表中添加两个2。添加后计数列表中减掉对应的数量。
?...三、Python实现计数排序
# coding=utf-8
def counting_sort(array):
if len(array) < 2:
return array...2, 5, 9, 5, 7, 6]
print(counting_sort(array))
运行结果:
[2, 2, 3, 3, 5, 5, 5, 6, 7, 7, 7, 9]
代码中,使用Python...然后根据上面分析的排序原理,进行计数,再将数据添加到新列表中。i 表示计数列表的索引,也表示待排序列表中值为 i 的元素,j 表示值为 i 的元素有 j 个。
四、计数排序的时间复杂度和稳定性
1....时间复杂度
在计数排序中,需要走访待排序列表中的每一个元素,进行计数,列表长度为 n ,然后需要遍历计数列表,添加数据到新列表中,计数列表长度为 k+1 ,时间复杂度为 T(n)=n+k+1,再乘计数和添加数据的步骤数