如何使用python实现计数排序与桶排序

发布时间:2021-04-07 10:47:31 作者:小新
来源:亿速云 阅读:206

这篇文章将为大家详细讲解有关如何使用python实现计数排序与桶排序,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

计数排序

  1. 找到给定序列的最小值与最大值

  2. 创建一个长度为最大值-最小值+1的数组,初始化都为0

  3. 然后遍历原序列,并为数组中索引为当前值-最小值的值+1

  4. 此时数组中已经记录好每个值的数量,自然也就是有序的了

例如:

如何使用python实现计数排序与桶排序

计数排序实现

下面为列表的计数排序

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实现计数排序与桶排序

桶排序实现

这里选择桶的数量为序列元素个数+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()
  # 回填,这里桶内部排序直接调用了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实现计数排序与桶排序”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

推荐阅读:
  1. 使用PHP实现简单的桶排序原理
  2. 如何使用js实现计数排序

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:如何使用python实现维吉尼亚算法

下一篇:如何使用python实现Virginia无密钥解密

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》