计数排序与桶排序python实现

2019-04-11 10:13:51来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

计数排序与桶排序python实现

计数排序

计数排序原理:

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

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

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

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

例如:

计数排序实现

下面为列表的计数排序


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,范围分别是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]

总结

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

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

?

原文链接:https://www.cnblogs.com/sfencs-hcy/p/10612422.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:yolo_v3训练自己的模型(人脸及deep-sort)

下一篇:Django ORM中,如何使用Count来关联对象的子集数量