优秀网文,优化师是一份怎样的工作,苏州网站开发公司鹅鹅鹅,网站建设合同doc计数排序与桶排序python实现 计数排序 计数排序原理#xff1a; 找到给定序列的最小值与最大值 创建一个长度为最大值-最小值1的数组#xff0c;初始化都为0 然后遍历原序列#xff0c;并为数组中索引为当前值#xff0d;最小值的值#xff0b;#xff11; 此时数组中… 计数排序与桶排序python实现 计数排序 计数排序原理 找到给定序列的最小值与最大值 创建一个长度为最大值-最小值1的数组初始化都为0 然后遍历原序列并为数组中索引为当前值最小值的值 此时数组中已经记录好每个值的数量自然也就是有序的了 例如 计数排序实现 下面为列表的计数排序
def count_sort(s):计数排序# 找到最大最小值min_num min(s)max_num max(s)# 计数列表count_list [0]*(max_num-min_num1)# 计数for i in s:count_list[i-min_num] 1s.clear()# 填回for ind,i in enumerate(count_list):while i ! 0:s.append(indmin_num)i - 1if __name__ __main__:a [3,6,8,4,2,6,7,3]count_sort(a)print(a)计数排序的缺点 当数值中有非整数时计数数组的索引无法分配 桶排序 桶排序原理 桶排序与计数排序类似但可以解决非整数的排序 桶排序相当于把计数数组划分为按顺序的几个部分 每一部分叫做一个桶它来存放处于该范围内的数 然后再对每个桶内部进行排序可以使用其他排序方法如快速排序 最后整个桶数组就是排列好的数据再将其返回给原序列 举例 桶排序实现 这里选择桶的数量为序列元素个数1范围分别是5等分与最大值和上面那个图一样。 具体问题应该按照具体情况进行桶划分 这里桶内部排序直接调用了sorted
def bucket_sort(s):桶排序min_num min(s)max_num max(s)# 桶的大小bucket_range (max_num-min_num) / len(s)# 桶数组count_list [ [] for i in range(len(s) 1)]# 向桶数组填数for i in s:count_list[int((i-min_num)//bucket_range)].append(i)s.clear()# 回填这里桶内部排序直接调用了sortedfor i in count_list:for j in sorted(i):s.append(j)if __name__ __main__:a [3.2,6,8,4,2,6,7,3]bucket_sort(a) print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]总结 计数排序与桶排序都是以牺牲空间换时间虽然很快但由于可能产生大量的空位置导致内存增大尤其是计数排序。 桶排序中尽量使每个桶中的元素个数均匀分布最好 转载于:https://www.cnblogs.com/sfencs-hcy/p/10612422.html
