桶排序(Bucket Sort)的数组实现
桶排序(Bucket Sort)的数组实现
桶排序的数组实现
桶排序Bucket Sort从1956年就开始被使用，该算法的基本思想是由E. J. Issac R. C. Singleton提出来。
桶排序(Bucket Sort)是迄今为止最快的一种排序法，其时间复杂度仅为Ο(n)，也就是线性复杂度！不可思议吧？但它是有条件的
桶排序(BucketSort) 小结：
1 桶排序核心思想是：根据数据规模n划分，m个相同大小的区间 （每个区间为一个桶，桶可理解为容器）
2 每个桶存储区间内的元素(区间为半开区间例如[0,10)或者[200,300) )
3 将n个元素按照规定范围分布到各个桶中去
4 对每个桶中的元素进行排序，排序方法可根据需要，选择快速排序，或者归并排序，或者插入排序
5 依次从每个桶中取出元素，按顺序放入到最初的输出序列中(相当于把所有的桶中的元素合并到一起)
6 桶可以通过数据结构链表实现
7 基于一个前提，待排序的n个元素大小介于0~k之间的整数 或者是(0, 1)的浮点数也可（算法导论8.4的例子）
8 桶排序的时间代价，假设有m个桶，则每个桶的元素为n/m;
当辅助函数为冒泡排序O(n2)时,桶排序为 O(n)+mO((n/m)2);
当辅助函数为快速排序时O(nlgn)时,桶排序为 O(n)+m*O(n/m log(n/m))
9 通常桶越多，执行效率越快，即省时间，但是桶越多，空间消耗就越大，是一种通过空间换时间的方式
举个例子：
某一年的全国高考考生人数为500万，数学一科分数使用标准分，最低0，最高150，没有小数，你把这500万元素的数组排个序。我们抓住了这么个非常特殊的条件，就能在毫秒级内完成这500万的排序，那就是：最低0，最高150，没有小数，那一共可出现的分数可能有多少种呢？一共有150-0+1=151，那么多种，想想看，有没有什么“投机取巧”的办法？方法就是创建151个“桶”，从头到尾遍历一次数组，对不同的分数给不同的“桶”加料，比如有个考生考了140分，那么就给140分的那个桶(下标为140-100)加1，完成后遍历一下这个桶数组，按照桶值，填充原数组，100分的有1000人，于是从0填到999，都填100，102分的有1200人，于是从1000到2019，都填入102…
可运行的代码：
// buckets sort in arrays, the same element in each bucket
#include<iostream>
#include<string.h> // memset函数在此头文件中定义
#define MAX_LEN 100
using namespace std;
int main()
{
int arr[]={3,1,4,8,2,13,3,5,2}; // 简单情形：没有小数(如果有小数，可以考虑先整体*10^n，n为小数位最大值，后面再复原)
int i, bucket[MAX_LEN];
memset(bucket,0,sizeof(bucket)); // 用多个桶分别来记录相应索引i在原数组arr中出现的次数，全初始化为0
int ElemNum=sizeof(arr)/sizeof(arr[0]); // 计算原序列中数的个数，记为ElemNum
for(i=0;i<ElemNum;i++)
{
int v=arr[i];
bucket[v]++; // 记录相应索引i在原数组arr中出现的次数，没有出现的元素，存默认的0到数组bucket中
}
for(i=0;i<MAX_LEN;i++)
{
while(bucket[i]>0)
{
cout<<i<<" "; // 按序出桶
bucket[i]--;
}
}
cout<<endl;
return 0;
}可从控制台输入的程序：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int arr[100],n,c,i;
while(1)
{
cin>>n;
memset(arr,0,sizeof(arr));
for(i=0;i<n;i++)
{
cin>>c;
arr[c]++;
}
for(i=0;i<100;i++)
{
while(arr[i]>0)
{
cout<<i<<" ";
arr[i]--;
}
}
cout<<endl;
}
return 0;
}最简单的C语言实现：
#include<stdio.h>
int main()
{
int bucket[1001],i,j,temp,n;
for(i=0;i<=1000;i++)
bucket[i]=0;
scanf("%d",&n); //输入一个数n，表示接下来有n个数
for(i=1;i<=n;i++) //循环读入n个数，并进行桶排序
{
scanf("%d",&temp); //把每一个数读到变量temp中
bucket[temp]++; //进行计数，对编号为temp的桶放一个小旗子
}
for(i=0;i<=1000;i++) //依次判断编号1000~0的桶
for(j=1;j<=bucket[i];j++) //出现了几次就将桶的编号打印几次
printf("%d ",i);
getchar();
return 0;
}