文档章节

桶排序的思想

Yason_Luo
 Yason_Luo
发布于 2014/01/20 13:40
字数 705
阅读 78
收藏 0
点赞 0
评论 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的个数统计,比如统计高考分数分布。(为每个可能的高考分数创建一个桶,统计每个桶内的记录个数即可)

© 著作权归作者所有

共有 人打赏支持
Yason_Luo

Yason_Luo

粉丝 250
博文 45
码字总数 5378
作品 0
深圳
高级程序员
排序算法整理

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

Seas0n_ ⋅ 2016/03/06 ⋅ 0

20180324基数排序(没太看懂)

基数排序 前置知识 + 基数排序(radix sort)是计数排序和桶排序的衍生,一种基于分配式排序思想和多关键字排序思想的算法,主要思想是“分配”和“收集”。+ 之前的排序都是比较便宜,最快也...

im天行 ⋅ 03/24 ⋅ 0

[桶排序]最大间隙问题

这个问题很经典,解法很巧妙。如果是要求O(nlogn)的做法,那么只需要简单地排序一下就行了。但是这里要求O(n),就需要另外的方法了。基于比较的排序方法,最好的也是O(nlogn),但是,还有...

m2012 ⋅ 2012/05/19 ⋅ 0

简单桶排序——Kotlin与Java实现

转载请标明出处:拿客 www.coderknock.com 桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或...

拿客-三产 ⋅ 2016/06/22 ⋅ 0

buddy算法和k桶算法

再读BUDDY算法 http://blog.csdn.net/lights_joy/article/details/2732441 著名的大数量的排序算法--K桶排序法~在数据文本式的大数据排序时,K桶法会是一个不错的选择! k桶法:k桶法有两个主...

慎道 ⋅ 2011/07/22 ⋅ 0

【数据结构】排序算法总结

在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生改变,则称这种...

aminqiao ⋅ 2014/04/15 ⋅ 0

十种常见排序算法

1.常见算法分类 十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆...

architect刘源源 ⋅ 01/28 ⋅ 0

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

LCZ777 ⋅ 2014/08/18 ⋅ 0

排序算法总结

花了很长时间终于把排序的基础学了一下,这段时间学了很多东西,总结一下: 学的排序算法有:插入排序,合并排序,冒泡排序,选择排序,希尔排序,堆排序,快速排序,计数排序,基数排序,桶...

扶殊88 ⋅ 2012/02/19 ⋅ 0

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

疯狂的兔子 ⋅ 2014/08/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 45分钟前 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 49分钟前 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 52分钟前 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

云计算的选择悖论如何对待?

人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云计算为...

linux-tao ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部