文档章节

桶排序的思想

Yashin
 Yashin
发布于 2014/01/20 13:40
字数 705
阅读 405
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

【引用】

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
      例如要对大小为[1..1000]范围内的n个整数A[1..n]排序,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储(10..20]的整数,……集合B[i]存储((i-1)*10, i*10]的整数,i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任何排序法都可以。最后依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这样就得到所有数字排好序的一个序列了。   
      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序,那么整个算法的复杂度是O(n+m*n/m*log(n/m))=O(n+nlogn-nlogm)   
      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)   
      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。


桶排序思想:用空间复杂度换取时间复杂度的经典例子,简单来说桶排序就是将要排序的集合划分为多个顺序的子集,再对每个子集排序,最后合并各个顺序的子集。如上面引用所诉,在多数场景下是可以用桶排序提高时间效率的。桶排序的应用场景主要是:1.key范围不大,2.各子集分布平均。桶排序的思想还适用于对不同key的个数统计,比如统计高考分数分布。(为每个可能的高考分数创建一个桶,统计每个桶内的记录个数即可)

© 著作权归作者所有

Yashin

Yashin

粉丝 259
博文 55
码字总数 5378
作品 1
深圳
高级程序员
私信 提问
加载中

评论(0)

常用排序算法(五)基数排序、桶排序以及计数排序

这是三种线性时间复杂度的排序算法,它们是用运算而不是比较来确定排序顺序的 一、基数排序 1.简介 它一种与其他排序算法完全不同的排序方法,其他的排序算法都是通过关键字之间的比较和移动...

osc_od08lbhl
2018/07/16
4
0
排序算法整理

冒泡排序   冒泡排序是最简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样,因此而得名。举个栗子,对5,3,8,6,4这个无序...

Seas0n_
2016/03/06
144
0
数据结构与算法之美学习笔记:第十三讲

一、课前问题 上两节中,我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天,我会讲三种时间复杂度是O(n)的排序算法:桶排序、计数排序、基数排序。 因为这些...

活的潇洒80
2019/11/19
0
0
十大经典排序算法的python实现

十种常见排序算法可以分为两大类:   非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。包括:冒泡排序、选择排...

翠竹09
2018/09/03
0
0
面试中的 10 大排序算法总结

分享分享自己收藏的学习资料,有需要的朋友可以找我获取 根据自身面试经历整理以及不断收集的(珍藏版) 【推荐】2020年最新Java电子书集合.pdf(吐血整理) >>> https://www.cnblogs.com/xia...

Java小耿
05/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在Windows上安装pip? - How to install pip on Windows?

问题: pip is a replacement for easy_install . pip替代了easy_install 。 But should I install pip using easy_install on Windows? 但是我应该在Windows上使用easy_install安装pip吗? ......

fyin1314
今天
21
0
gitlit二级目录访问

由于我们只有一个域名暴露,特殊需求,所以需要二级目录访问 配置文件在 defaults.properties 第1985行 contextPath 改掉就好了 # Context path for the GO application. You might want to...

shzwork
今天
24
0
OSChina 周一乱弹 —— 我电脑传染了新冠脚气

@性感码农 :不结婚,被老爸说,回村里别人都瞧不起你,及即使你赚了很多钱,不结婚,永远没有人瞧得起你。挺纳闷的,要别人瞧得起我干嘛 又不回村里, 跟他们生活也没什么交集啊, 用得着他...

小小编辑
今天
24
0
类加载的过程

加载->链接->初始化; 其中链接又分为:验证->准备->解析。

曦鱼violet
今天
21
0
Linux下几个与磁盘空间和文件尺寸相关的命令

硬盘是计算机非常重要的一个部件,不管是代码,还是 UI 、声音、文档,抑或是没人时偷偷看的小视频,都需要保存在硬盘里。 对于很多 Linux 服务器,会进行很多的编译操作。而编译操作在很多情...

Linux就该这么学
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部