算法探秘:不用比较也能排序(3)
——桶排序
前两期算法探秘,赵码匠介绍了两种线性排序算法——计数排序与基数排序(点击可跳转查看对应文章),其中都用到了一个概念——“桶”。
计数排序的“桶”用来装相同元素,表示其出现的次数;基数排序的“桶”则用来装某数位上的值相同的元素。这两种“桶”都是特殊的桶,是基于桶排序的理论特化后的版本。因此本期赵码匠要来介绍一下普通的桶排序。
桶排序的基本思想
将待排序的数据分到几个有序的桶中,每个桶内的数据在单独进行排序。排序完成后,再把每个桶内的数据按照桶顺序依次取出,组成的序列就是有序的。
桶排序的基本步骤
以数组
a[10]={35,22,26,8,1,36,12,19,47,11}为例:
1、确定桶:先找出数组的大小(10)、数组的最大值和最小值(47和1),确定桶的数量和分桶策略(分为5个桶,分别我0~9、10~19、20~29、30~39、40~49)
2、初始化桶:一般来说,创建vector二维数组来作为桶,其中vector[i]表示桶的序号,vector[i][j]表示桶中被分配的元素;
3、分配元素:遍历待排序数组,根据策略将数据分配到对应的桶中。其中,策略可以为值取模桶的数量、值的范围等;
排序前 | 桶1 | 桶2 | 桶3 | 桶4 | 桶5 |
范围 | 0~9 | 10~19 | 20~30 | 30~40 | 40~50 |
值 | 8,1 | 12,19,11 | 22,26 | 35,36 | 47 |
4、桶内排序:一般来说,桶内元素不多可使用多种排序算法,一般来说都使用sort()进行快速排序,如果桶内元素较多,则可以采用计数排序等其他高效的排序算法;
排序前 | 桶1 | 桶2 | 桶3 | 桶4 | 桶5 |
范围 | 0~9 | 10~19 | 20~30 | 30~40 | 40~50 |
值 | 1,8 | 11,12,19 | 22,26 | 35,36 | 47 |
5、合并桶:按照桶的顺序将所有元素合并,合并后的序列就是排序完成的序列。
合并后:
a[10]={1,8,11,12,19,22,26,35,36,47};
桶排序的时空复杂度分析
设原数组长度为n,桶的个数为k,每个桶平均有m个元素,其中n=m*k。
首先将数组元素遍历找到最大值最小值,进行策略设计,时间复杂度为O(n);
其次根据策略再次遍历数组,将每个值分配到对应的桶中,时间复杂度也是O(n);
接着桶内元素进行快速排序,平均时间复杂度为O(mlogm);
最后将所有元素合并,时间复杂度仍然是O(n);
因此,桶排序的总时间复杂度为O(n+mlogm),当桶内元素个数远少于数组长度时,桶排序的时间复杂度就渐进为O(n)。
桶排序的空间复杂度为O(n+m*k),且当m足够小时,空间复杂度为O(n+k)。
总结
桶排序作为计数排序和基数排序的父算法,克服了只能对整数进行排序的弊端,针对浮点数、简单字符串也能有良好的排序表现(主要由于桶内的排序算法可以任意选),适用于数据量较大但是分布较为均匀、数据范围已知且方便分配到桶的情况。
但是由于桶排序本质上是对数据进行分布式计算,充分发挥了并行处理的优势,因此如果数据无法被分配得均匀,桶排序的高效就没办法体现出来了。
【代码展示】
#include<iostream>
#include<ctime>
#include<vector>
#include<algorithm>
using namespace std;
#define N 20 //以20个元素的数组为例
int a[N];
vector<int> tong[N];//最多N个桶
int main(){
srand(time(0));
cout<<"排序前:";
for(int i=0;i<N;i++){
a[i]=rand()%100;//随机生成20个100以内的数字
cout<<a[i]<<" ";
}
cout<<endl;
//找最大值,进行数据准备
int maxx=0;
for(int i=0;i<N;i++){
maxx=max(maxx,a[i]);
}
//下面开始桶排序
//第一步:分配
for(int i=0;i<N;i++){
tong[a[i]/10].push_back(a[i]);//规则:按十位数分桶
}
//展示每个桶的元素
for(int i=0;i<=maxx/10;i++){
cout<<"第"<<i<<"个桶里的元素有:" ;
for(auto j: tong[i]){
cout<<j<<" ";
}
cout<<endl;
}
//第二步:桶内排序
for(int i=0;i<=maxx/10;i++){
sort(tong[i].begin(),tong[i].end());
}
//第三步,还原
int num=0;
for(int i=0;i<=maxx/10;i++){
for(auto j: tong[i]){
a[num++]=j;
}
}
cout<<"排序结果:";
for(int i=0;i<N;i++){
cout<<a[i]<<" ";
}
return 0;
}
运行结果