当前位置:脚本大全 > > 正文

python利用空列表进行数字排序(python实现计数排序与桶排序实例代码)

时间:2021-10-24 10:44:04类别:脚本大全

python利用空列表进行数字排序

python实现计数排序与桶排序实例代码

计数排序

  1. 找到给定序列的最小值与最大值
  2. 创建一个长度为最大值-最小值+1的数组,初始化都为0
  3. 然后遍历原序列,并为数组中索引为当前值-最小值的值+1
  4. 此时数组中已经记录好每个值的数量,自然也就是有序的了

例如:

python利用空列表进行数字排序(python实现计数排序与桶排序实例代码)

计数排序实现

下面为列表的计数排序

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • def count_sort(s):
  •   """计数排序"""
  •   # 找到最大最小值
  •   min_num = min(s)
  •   max_num = max(s)
  •   # 计数列表
  •   count_list = [0]*(max_num-min_num+1)
  •   # 计数
  •   for i in s:
  •     count_list[i-min_num] += 1
  •   s.clear()
  •   # 填回
  •   for ind,i in enumerate(count_list):
  •     while i != 0:
  •       s.append(ind+min_num)
  •       i -= 1
  •  
  • if __name__ == '__main__':
  •   a = [3,6,8,4,2,6,7,3]
  •   count_sort(a)
  •   print(a)
  • 计数排序的缺点

    当数值中有非整数时,计数数组的索引无法分配

    桶排序

    桶排序原理:

    1. 桶排序与计数排序类似,但可以解决非整数的排序
    2. 桶排序相当于把计数数组划分为按顺序的几个部分
    3. 每一部分叫做一个桶,它来存放处于该范围内的数
    4. 然后再对每个桶内部进行排序,可以使用其他排序方法如快速排序
    5. 最后整个桶数组就是排列好的数据,再将其返回给原序列

    举例:

    python利用空列表进行数字排序(python实现计数排序与桶排序实例代码)

    桶排序实现

    这里选择桶的数量为序列元素个数+1,范围分别是5等分与最大值,和上面那个图一样。

    具体问题应该按照具体情况进行桶划分

    这里桶内部排序直接调用了sorted

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 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()
  •   # 回填,这里桶内部排序直接调用了sorted
  •   for 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]
  • 总结

    计数排序与桶排序都是以牺牲空间换时间,虽然很快,但由于可能产生大量的空位置导致内存增大,尤其是计数排序。

    桶排序中尽量使每个桶中的元素个数均匀分布最好

    以上所述是小编给大家介绍的python计数排序与桶排序详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对开心学习网网站的支持!

    原文链接:https://www.cnblogs.com/sfencs-hcy/p/10612422.html
    上一篇下一篇

    猜您喜欢

    热门推荐