桶排序的数组实现
桶排序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;
}