| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 442 人关注过本帖
标题:桶排序
只看楼主 加入收藏
楚煜
Rank: 1
来 自:L
等 级:新手上路
帖 子:15
专家分:0
注 册:2020-1-21
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:6 
桶排序
初步接触桶排序算法,感觉有点蒙,不知道它的基本逻辑及运算,请问桶排序该怎么去理解😣
搜索更多相关主题的帖子: 运算 算法 排序 逻辑 
2020-06-02 23:28
雪影辰风
Rank: 6Rank: 6
来 自:衡阳市
等 级:贵宾
威 望:21
帖 子:169
专家分:332
注 册:2019-6-17
收藏
得分:5 
这个其实挺好的理解的

比如说我定义了一个数组为a[11]
然后就是,数组的下标表示数列中的相同的数字,然后改下标对应的是这个数字出现次数
比如说,定义变量num一次输入3,2,3,4,5,2,6,1,8
Step 1:输入3,那么其所对应的“桶”就是3号桶,所以a[3]++
Step 2:输入2,那么对应2号桶,所以a[2]++
Step 3:输入3,同样的,对应3号桶,a[3]++
......
Step n:输入num,则a[num]++

经过如上操作以后,列举出各桶存放的数量
桶号: 0  1  2  3  4  5  6  7  8  9  10
数量:0  1  2  2  1  1  1  0  1  0  0
【简而言之,数量表示桶号在给出数列中出现的次数】
接下来是输出操作,我们发现,有些桶里是空的,也就是0次,所以我们无需输出,则:
找到0号桶,为空,跳过
找到1号桶,不为空,设其数量为n,则重复输出n次桶号;此时,n=1,所以输出一次1
找到2号桶,不为空,如上;此时n=2,输出2次2
找到3号桶,不为空,如上;此时n=2,输出2次3
...
找到n号桶,如果为空,则跳过;如果不为空,输出n桶中存的数值,并重复输出其数值次n

示例(仅供参考)
程序代码:
#include <cstdio>
using namespace std;
int a[1001];
int main() {
    int n;
    printf("输入你想排序的数字个数:");
    scanf("%d",&n);
    printf("输入你想排序的数字:");
    for(int i=1,t; i<=n; i++) {
        scanf("%d",&t);
        a[t]++; //出现次数+1
    }
    printf("排序结果输出:"); 
    for(int i=0; i<=1000; i++) {
        if(a[i]!=0) { //对空桶的筛选
            for(int j=1; j<=a[i]; j++)
                printf("%d ",i);
        }
    }
    return 0;
}
2020-06-05 20:35
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:208
帖 子:2003
专家分:11148
注 册:2014-12-6
收藏
得分:5 
回复 2楼 雪影辰风
这是桶排序吗?计数排序吧。
其实我也看到很多文章把桶排序和计数排序混淆的,但计数排序是基于非比较的排序,只能排一定范围内的正整数(排多大范围取决于你最大申请到的内存且小于计算机正整数最大范围),计数排序时间复杂度为O(n),空间复杂度为O(max+1),假如排5个数,其中最大数为10000的话,得申请10001个额外空间辅助排序,极其浪费。
下述关于桶排序的介绍摘自百度:
桶排序的原理是将数组分到有限数量的桶中,再对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。

排序过程:

1,假设待排序的一组数统一的分布在一个范围中,并将这一范围划分成几个子范围,也就是桶
2,将待排序的一组数,分档规入这些子桶,并将桶中的数据进行排序
3,将各个桶中的数据有序的合并起来

显然,桶排序是基于数据比较类型的排序,可以排序任何类型数据。该算法将待排数据根据大小分配到对应数据大小范围的桶中后,还需要再用传统排序方法对桶中数据进行二次排序,最后再将各桶中数据按桶编号顺序合并即可。其实这可以理解为一种变种的归并排序算法,当只有一个桶时,就和普通排序无二了。但假如待排序数绝对均匀分布,且桶个数和排序数据个数相等时,这个算法也能做到O(n)的复杂度。实际上待排序数据不可能均匀分布的,即有的桶中数据多,有的数据少,为了应对这种情况,很多算法会以链表方式组织桶数据。

能编个毛线衣吗?
2020-06-05 21:49
雪影辰风
Rank: 6Rank: 6
来 自:衡阳市
等 级:贵宾
威 望:21
帖 子:169
专家分:332
注 册:2019-6-17
收藏
得分:0 
回复 3楼 wmf2014
不好意思确实有问题,我后来查了网上资料,发现桶排序是另一种方式,这个是计数排序(书上把这个说是桶排序,可能编者也搞错了)

[此贴子已经被作者于2020-6-6 08:56编辑过]

2020-06-06 08:51
楚煜
Rank: 1
来 自:L
等 级:新手上路
帖 子:15
专家分:0
注 册:2020-1-21
收藏
得分:0 
嗯,谢谢大家^_^!

为了梦想,为了未来,为了信仰。
2020-06-09 21:46
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:33
帖 子:1085
专家分:3403
注 册:2011-12-3
收藏
得分:0 
以下是引用wmf2014在2020-6-5 21:49:31的发言:

显然,桶排序是基于数据比较类型的排序,可以排序任何类型数据。该算法将待排数据根据大小分配到对应数据大小范围的桶中后,还需要再用传统排序方法对桶中数据进行二次排序,最后再将各桶中数据按桶编号顺序合并即可。其实这可以理解为一种变种的归并排序算法,当只有一个桶时,就和普通排序无二了。但假如待排序数绝对均匀分布,且桶个数和排序数据个数相等时,这个算法也能做到O(n)的复杂度。实际上待排序数据不可能均匀分布的,即有的桶中数据多,有的数据少,为了应对这种情况,很多算法会以链表方式组织桶数据。

你说错了 你对基于比较的排序理解有问题
全部元素用比较决定次序的排序才是基于比较的排序

能不能排序任意类型数据 无法用于区分是不是比较排序

计数排序也好 桶排序也好 都不属于比较排序
最明显的区别是 桶排序时间复杂度是 O(n) 突破了比较排序时间复杂度下限O(n log n)


https://zh.
2020-06-11 18:37
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:208
帖 子:2003
专家分:11148
注 册:2014-12-6
收藏
得分:0 
回复 6楼 lin5161678
好吧,你是正确的。
由于并没有自己用代码实现,所以看到“每个桶存储一定范围内的数”、“用传统排序方法二次排序”后,想当然地要用数据比较的方法来确定待排序数放进哪个桶。后来自己花时间想了想,其实确定一个待排序数放进哪个桶,完全可以用计算的方式得到,不需要数据比较,同时,二次排序也可以继续用桶排序完成,所以全过程不需要数据比较。至于区分比较和非比较是否用突破O(nlogn)来界定,我没百度到,我还是按照是否进行排序数据之间的比较来界定。
我在三楼关于“很多算法会以链表方式组织桶数据”的观点也不准确,其实只需要申请一个空桶空间和一个预备空间n就可以完成桶排序,空间复杂度为O(n+k),当k>=n,一个桶中只有一个数或多个相等的数时,就不需要二次排序了,复杂度就是O(n)。
至于“排序所有类型数据”只是为了说明区别计数排序的:不作特殊处理,计数排序只能排正整数,桶排序可以排任何类型数。
最近较忙,空下来时实现一下,看看这个算法在不同桶数的情况下到底比c qsort快多少。

[此贴子已经被作者于2020-6-11 20:22编辑过]


能编个毛线衣吗?
2020-06-11 20:20
快速回复:桶排序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.048760 second(s), 8 queries.
Copyright©2004-2020, BCCN.NET, All Rights Reserved