文档章节

桶排序

 野渡书生
发布于 2016/05/03 11:11
字数 674
阅读 4
收藏 0

1、定义

    箱排序的变种。为了区别于上述的箱排序,姑且称它为桶排序(实际上箱排序和桶排序是同义词)。

2、基本思想

    桶排序的思想是把[0,1)划分为n个大小相同的子区间,每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序,然后依次将各非空桶中的记录连接(收集)起来即可。

    注意:

    这种排序思想基于以下假设:假设输入的n个关键字序列是随机分布在区间[0,1)之上。若关键字序列的取值范围不是该区间,只要其取值均非负,我们总能将所有关键字除以某一合适的数,将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0,1)上的。

3、桶排序算法

    伪代码算法为:

void BucketSon(R)
   { //对R[0..n-1]做桶排序,其中0≤R[i].key<1(0≤i<n)
     for(i=0,i<n;i++) //分配过程.
       将R[i]插入到桶B[「n(R[i].key)」]中; //可插入表头上
     for(i=0;i<n;i++) //排序过程
       当B[i]非空时用插人排序将B[i]中的记录排序;
     for(i=0,i<n;i++) //收集过程
       若B[i]非空,则将B[i]中的记录依次输出到R中;
    }

 注意:

    实现时需设置一个指针向量B[0..n-1]来表示n个桶。但因为任一记录R[i]的关键字满足:0≤R[i].key<1(0≤i≤n-1),所以必须将R[i].key映射到B的下标区间[0,n-1)上才能使R[i]装入某个桶中,这可通过└n*(R[i].key)┘来实现。

4、桶排序算法分析

    桶排序的平均时间复杂度是线性的,即O(n)。但最坏情况仍有可能是O(n2)。

    箱排序只适用于关键字取值范围较小的情况,否则所需箱子的数目m太多导致浪费存储空间和计算时间。

    【例】n=10,被排序的记录关键字ki取值范围是0到99之间的整数(36,5,16,98,95,47, 32,36,48)时,要用100个箱子来做一趟箱排序。(即若m=n2时,箱排序的时间O(m+n)=O(n2))。


© 著作权归作者所有

粉丝 9
博文 217
码字总数 158821
作品 0
南京
私信 提问

暂无文章

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部