算法探秘：不用比较也能排序（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;
} 运行结果
