桶排序的数组实现
铲斗排序Bucket Sort从1956年开始使用，该算法的基本思想由E. J. Issac R. C. Singleton提出。
桶排序是目前为止最快的排序方法，其时间复杂度只有(n )，即线性复杂度！ 不可思议吧？ 但那是有条件的
桶排序(BucketSort )总结：
1桶排序的中心思想是根据数据规模n来划分的，是m个同样大小的区间(每个区间为一个桶，桶可以理解为容器)
2每个存储段内存段中的元素(段为半开段(0，10 )或(200，300 ) )
使3n个元素在规定范围内分布在各个桶中
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/mlog ) n/m ) )
9通常桶越多，执行效率越快，也就是说越节约时间，但桶越多，空间消耗量越大，是一种用空间交换时间的方式
举个例子：
有一年全国高考考生500万人，数学一科的分数使用标准分，最低0，最高150，没有小数。 请按顺序排列这500万要素的排列。 我们抓住这样一个非常特殊的条件，可以在毫秒水平上完成这500万的排名。 那就是最低0，最高150，没有小数，全部能出现的分数可能有多少种呢？ 一共150-0 1=151，有那么多种类。 想想看。 有什么“投机的方法”吗？ 方法是制作151个“水桶”，从头到尾遍历一次排列，针对不同的分数向不同的“水桶”充值。 例如，如果一个考生得了140分，则在140分的桶(下标为140-100 )上加1，完成后遍历该桶数组，根据桶的值填充原始数组，100分的为1000人。 于是
可执行代码：
//buckets sort in arrays，the same element in each bucket
#包含
#include //memset函数在此头文件中定义
#define MAX_LEN 100
using namespace std；
int main () )
{
intarr [ ]={ 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
intelemnum=sizeof(arr )/sizeof ) arr[0]； //计数原序列中的数的个数，表示为ElemNum
for(I=0； I
{
int v=arr[i]；
bucket[v]； //记录对应的索引I在原数组arr中出现的次数，未出现的要素从默认的0存储到数组bucket中
}
for(I=0； I
{
wile(bucket[I]0) ) )
{
出局
bucket[I]----；
}
}
出局
返回0；
}
可以从控制台输入的程序：
#包含
#包含
using namespace std；
int main () )
{
int arr[100]，n，c，I；
while(1)。
{
cinn；
memset(arr，0，sizeof ) arr )；
for(I=0； I
{
cinc；
arr[c]；
}
for(I=0； i100； I )
{
wile(arr[I]0) )
{
出局
ARR[I]----；
}
}
出局
}
返回0；
}
最简单的c语言实现：
#包含
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 (；
返回0；
}