Python算法—计数排序
计数排序
1.算法介绍
计数排序是⼀种⾮基于⽐较的排序算法，其空间复杂度和时间复杂度均为O(n+k)，其中k是整数的范围。基于⽐较的排序算法时间复杂度最⼩是O(nlogn)的。
计数排序的核⼼在于将输⼊的数据值转化为键存储在额外开辟的数组空间中。作为⼀种线性时间复杂度的排序，计数排序要求输⼊的数据必须是有确定范围的整数。
计数排序对于数据范围很⼤的数组，需要⼤量时间和内存。
2.算法思想
假设要排序的数组为 A = {1,0,3,1,0,1,1}这⾥最⼤值为3，最⼩值为0，
那么我们创建⼀个数组C，长度为3+1-0=4。然后⼀趟扫描数组A，得到A中各个元素的总数，并保持到数组C的对应单元中。⽐如0 的出现次数为2次，则 C[0] = 2;1 的出现次数为4次，则C[1] = 4。C=[2,4,0,1]由
于C 是以A的元素为下标的，所以这样⼀做，A中的元素在C中⾃然就成为有序的了，然后我们分别统计⽐0,1,2,3⼩的元素个数，如⽐1⼩（包括1）的元素有6个。更新C,C=[2,6,6,7]，更新C是为了保证排序稳定。然后把这个在C中的记录按每个元素的计数展开到输出数组B中，排序就完成了。 也就是B[0] 到 B[1] 为0, B[2] 到 B[5]为1 这样依此类推。
3.算法过程
⾸先出数组中的最⼤值，那么数组中的所有值肯定在0到最⼤值之间，⽐如如果数组的范围是从0-10，那么数组中的值肯定都在0-10这11个数之间
建⽴⼀个元素全是0的数组，数组下标为0到最⼤值，假设最⼤值=10，则如下图所⽰：
元素00000000000
元素下标012345678910
举例讲解
先假设20个随机整数的值是：2，4，2，3，7，1，1，0，0，5，6，9，8，5，7，4，0，10，9，10
python获取数组长度
先遍历这个⽆序的随机数组，每个元素按照其值对号⼊座，再将数组下标的元素进⾏+1操作，⽐如，第⼀个元素是2，则下标为2的元素加1：
元素00100000000
元素下标012345678910
第⼆个元素是4，则下标为4的元素加1：
元素00101000000
元素下标012345678910
第三个元素是2，则下标为2的元素加1：
元素00201000000
元素下标012345678910
如此遍历原数组，最终结果：
元素32212212122
元素下标012345678910
这样就统计出了数组中每个值出现的次数，有了这个统计结果就可以直接遍历数组，输出数组元素的下标值，元素的值是⼏，就输出⼏次4.python代码实现
代码1
def count_sort1(arr):
maxi =max(arr)# 出最⼤值
count_arr =[0for _ in range(maxi +1)]# 创建⼀个全0列表
# 统计序列中每个元素出现的次数
for value in arr:
count_arr[value]+=1
arr.clear()# 将原列表清空
for index, element in enumerate(count_arr):# index：元素下标
for i in range(element):
arr.append(index)
def count_sort2(arr):
maxi =max(arr)# 出数组中的最⼤值
count_arr =[0for _ in range(maxi +1)]# 创建⼀个全0列表
# 统计序列中每个元素出现的次数
for value in arr:
count_arr[value]+=1
new_arr =[]# 创建⼀个新列表
for i in range(len(count_arr)):
while count_arr[i]!=0:
new_arr.append(i)
count_arr[i]-=1
return new_arr
import random
numbers =[random.randint(0,10)for _ in range(20)]
print(numbers)
count_sort1(numbers)
print(numbers)
numbers2=[3,4,5,6,9,5,2,1,2,3,6,8,9,7]
print(count_sort2(numbers2))
代码中的⼀些解释
1. enumerate()函数的⽤法：
enumerate() 函数⽤于将⼀个可遍历的数据对象(如列表、元组或字符串)组合为⼀个索引序列，同时列出数据和数据下标，⼀般⽤在for 循环当中，其⽤法如下：
语法格式：enumerate(sequence, [start=0])
参数说明:
1.sequence : ⼀个序列、迭代器或其他⽀持迭代对象
2.start : 下标起始位置
举例说明：存在⼀个sequence，对其使⽤enumerate将会得到如下结果：
1  start        sequence[0]
2  start+1  　sequence[1]
3  start+2      sequence[2]
...
实例：
seq =['one','two','three']
for i, element in enumerate(seq):
print(i, element）
结果输出：
0    one
1    two
2    three
这个函数会输出下元素值和其对应的下标索引
2. for _ in range(maxi + 1)的⽤法：
list1 =[0for _ in range(10)]
print(list)
list2=[2**2for _ in range(5)]
print(list2)
输出结果：
list1:[0,0,0,0,0,0,0,0,0,0]
list2:[2,2,2,2,2]
这⾥的下划线(_)是个占位符，不⽤管它⾥⾯什么内容，它的作⽤就是让前⾯的内容循环这么多次， 即 for _ in range(n)的作⽤是仅仅是重复循环 n 次
3. random.randint(0, 10) : 随机返回0-10之间的⼀个数，不包括10
优化后的代码3
上⾯的代码在⼀开始就求得了数列的最⼤值maxi，创建的数组count_arr，长度是maxi+1，以保证数组最后⼀个下标是maxi。
但是这段代码并不严谨，假如数组中的最⼩值是50，最⼤值是59，那么按照上⾯代码则需要创建长度为60的数组，为前⾯50个数(0-49)是没有的，那么就会浪费空间，所以数组长度应该是 : 最⼤值-最⼩值+1，⽽把数组最⼩值作为⼀个偏移量。
举例说明：假如数组为：55，54，59，50，51，52，51，53，56，55
则偏移量=最⼩值(50)，那么对于第⼀个数55⽽⾔，对应的数组下标应该是55-50=5
为了使排序是稳定的，我们可以依次统计⽐**[50,51,52, … ,59]⼩的元素个数，例如⽐ 51⼩的元素个数（包括51）有3个
原来的计数数组为：
元素次数1211121001偏移后下标0123456789
元素下标50515253545556575859
相加后的计数数组为
相加的原则使每个元素出现的次数=它前⾯所有元素出现次数+该元素出现的次数
相加次数134********偏移后下标0123456789
元素下标50515253545556575859
相加后计数数组元素的值就等于元素的所在位置，⽐如下标是6的元素值是9，代表原数列的值56最终的排序是在第9位
优化后的代码：
def count_sort2(arr):
maxi =max(arr)
mini =min(arr)
count_arr_length = maxi - mini +1# 计算待排序列表的数值区域长度，如4-9共9+1-4=6个数
count_arr =[0for _ in range(count_arr_length)]# 创建⼀个全为0的列表
for value in arr:
count_arr[value - mini]+=1# 统计列表中每个值出现的次数
# 使count_arr[i]存放<=i的元素个数，就是待排序列表中⽐某个值⼩的元素有多少个
for i in range(1, count_arr_length):
count_arr[i]= count_arr[i]+ count_arr[i -1]
new_arr =[0for _ in range(len(arr))]# 存放排序结果
for i in range(len(arr)-1,-1,-1):# 从后往前循环是为了使排序稳定
new_arr[count_arr[arr[i]- mini]-1]= arr[i]# -1是因为下标是从0开始的
count_arr[arr[i]- mini]-=1# 每归位⼀个元素，就少⼀个元素
return new_arr
if __name__ =='__main__':
user_input =input('输⼊待排序的数，⽤\",\"分隔:\n').strip()
#strip() ⽅法⽤于移除字符串头尾指定的字符（默认为空格）
unsorted =[int(item)for item in user_input.split(',')]
print(count_sort2(unsorted))
这⾥我说的⽐较可能不是太易懂，
计数排序适⽤于最⼤值和最⼩值相差不⼤的列表，如果⼀个列表的最⼩值是1，最⼤值是1亿，那么计数排序就需要开⼀个长度为1亿+1的列表，会⽐较费时

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。