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

yipeiwu_com7年前Python基础

计数排序

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

例如:

计数排序实现

下面为列表的计数排序

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. 最后整个桶数组就是排列好的数据,再将其返回给原序列

举例:

桶排序实现

这里选择桶的数量为序列元素个数+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计数排序与桶排序详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对【听图阁-专注于Python设计】网站的支持!

相关文章

python面向对象之类属性和类方法案例分析

python面向对象之类属性和类方法案例分析

本文实例讲述了python面向对象之类属性和类方法。分享给大家供大家参考,具体如下: 目标 类的结构 类属性和实例属性 类方法和静态方法 01. 类的结构 1.1 术语 —— 实例 使用...

python如何获取列表中每个元素的下标位置

Git是编程中的基本技能之一,互联网公司几乎都在使用Git进行协作编程,昨天还有位禅友在微信上专门告诉我说星期五面试的时候刚好被问到 Git,幸好在这几天学了一下。Git并不难,但会Gi...

django使用图片延时加载引起后台404错误

django使用图片延时加载引起后台404错误

环境 django 1.10.6 缘起 今天接到一个任务——解决终端满屏日志中的无用错误。 django 会尽可能给你准确报出错误位置,但是一些复杂,深层次的错误它自带的错误日志有些不足...

Ubuntu18.04中Python2.7与Python3.6环境切换

Ubuntu18.04中Python2.7与Python3.6环境切换

本文为大家分享了Python2.7与Python3.6环境切换的具体方法,供大家参考,具体内容如下 系统支持为:Ubuntu18.04 系统默认安装:Python2.7 自己安装:Pyt...

Python OpenCV图像指定区域裁剪的实现

在工作中。在做数据集时,需要对图片进行处理,照相的图片我们只需要特定的部分,所以就想到裁剪一种所需的部分。当然若是图片有规律可循则使用opencv对其进行膨胀腐蚀等操作。这样更精准一些。...