CSP-J/S常考算法探秘:不用比较也能排序(3)——桶排序

算法探秘：不用比较也能排序（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、分配元素：遍历待排序数组，根据策略将数据分配到对应的桶中。其中，策略可以为值取模桶的数量、值的范围等；

4、桶内排序：一般来说，桶内元素不多可使用多种排序算法，一般来说都使用sort()进行快速排序，如果桶内元素较多，则可以采用计数排序等其他高效的排序算法；

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; 
}

运行结果