搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发

episode53:桶排序

统计学知识分享平台 2020-07-01

文章链接:https://blog.csdn.net/liangjiubujiu/article/details/82813014

桶排序(bucket sort)假设输入数据服从均匀分布。平均情况下他的时间代价是O(n)。计数排序假设输入数据分布于一个小区间的整数,而桶排序则假设输入是一个随机过程产生的,该过程将元素均匀独立地分布于[0,1)区间上。1.桶排序的基本思想 桶排序将[0,1)区间划分为n个相同的大小的子区间,这些子区间被称为桶。然后将n个输入元素分别放入各自的桶中。因为输入时均匀独立的,所以一般不会有很多数同时落在一个桶中的情况。这样,我们想对各个桶中的数据进行排序,然后遍历每个桶,按照次序把各个桶中的元素列出来即可。一个桶排序的示例如图:

  1. def bucketSort(nums):

  2. # 选择一个最大的数

  3. max_num = max(nums)

  4. # 创建一个元素全是0的列表, 当做桶

  5. bucket = [0]*(max_num+1)

  6. # 把所有元素放入桶中, 即把对应元素个数加一

  7. for i in nums:

  8. bucket[i] += 1

  9. # 存储排序好的元素

  10. sort_nums = []

  11. # 取出桶中的元素

  12. for j in range(len(bucket)):

  13. if bucket[j] != 0:

  14. for y in range(bucket[j]):

  15. sort_nums.append(j)

  16. return sort_nums

  17. nums = [5,6,3,2,1,65,2,0,8,0]

  18. print bucketSort(nums)

  19. """



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《episode53:桶排序》的版权归原作者「统计学知识分享平台」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注统计学知识分享平台微信公众号

统计学知识分享平台微信公众号:statistic13920942516

统计学知识分享平台

手机扫描上方二维码即可关注统计学知识分享平台微信公众号

统计学知识分享平台最新文章

精品公众号随机推荐