桶排序 (Bucket sort)或所谓的箱排序，是一种分块的排序算法，工作的原理是将数组分到有限数量的桶里，每个桶的大小都相等。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
把待排序序列（数组）中的数据根据函数映射方法分配到若干个桶中，在分别对各个桶进行排序，最后依次按顺序取出桶中的数据。
适用于数据分配均匀，数据比较大，相对集中的情况。
简单来说就是把数据按某种方法分类，每一个类放进一个容器（箱子）中，然后用其他排序方法对每个容器中的数据排序，最后再按分配方法产生的顺序依次取出数据。
假设数据都为2或3位的正整数（0~999），那么对应的映射函数可以为
f(x)=x/100 也就是把百位相同的数据都放在同一个容器中，总共有10个容器
映射函数要根据数据情况合理的适用，排序的优劣与函数映射有很大的关系，不同的映射方法就决定了不同的桶的大小以及桶的数量。
极端的方法就是，可以达到每个桶中只有一个元素，使得时间复杂度最优，空间复杂度最高。
函数映射方法的选择要根据具体的情况来选择，没有最好的方法，只有比较合适的方法。
总的来说有两类实现方法，一类是在把数据从总的容器分配到每一个容器中时就按大小放进去
另一类是把数据全部放入容器中，再来排序。后一类方法可以调用新的排序方法，也可以调用桶排序，形成迭代。
我生成了20个3位的随机数(0~999)，按照百位的数字分别插入到不同的链表中。
函数映射： f(x)=x/100
排序方法： 在从总的数组中分配到每个链表时，按大小插入有序链表
最后按照链表的下标，按顺序取就可以了。
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num; //数据域
struct node *next; //指针域
}KeyNode;
void bucket_sort(int a[],int size,int bucket_size) {
int i,j; //数组，数组长度，桶的大小
//定义动态的指针数组
KeyNode **bucket_num = (KeyNode **)malloc(bucket_size * sizeof(KeyNode*));
for(i = 0;i < bucket_size;i++)
{
bucket_num[i] = (KeyNode*)malloc(sizeof(KeyNode));//为每个链表定义头结点
bucket_num[i]->num = 0;
bucket_num[i]->next = NULL; //指针变量初始化为空
}
for(j = 0;j < size;j++) //准备插入
{
KeyNode *node = (KeyNode *)malloc(sizeof(KeyNode));//定义一个节点
node->num = a[j]; //数据域存数据
node->next = NULL; //指向空
int index = a[j]/100; //映射函数 计算桶号
KeyNode *p = bucket_num[index];//p指向链表的头
//链表结构的插入排序
while(p->next != NULL && p->next->num <= node->num)
{
p = p->next; //1.链表为空，p->next==NULL，进入不了循环
} //2.链表不为空，因为链表从无开始按顺序插入，数据为有序的，
//可以找到 前一个节点 <= node <=后一个节点
//节点插入链表
node->next = p->next;
p->next = node;
(bucket_num[index]->num)++; //记录一下该链表中有几个有效节点
}
//打印结果
KeyNode * k = NULL; //定义一个空的结构体指针用于储存输出结果
for(i = 0;i < bucket_size;i++)
{
//for(k = bucket_num[i]->next;k!=NULL;k=k->next)//通过最后一个指针指向空
k = bucket_num[i]->next;
for(int m=0;m<bucket_num[i]->num;m++) //通过头指针记录节点数
{
printf("%d ",k->num);
k=k->next;
}
printf("\n");
}
int main()
{
int a[20];
for(int i=0;i<20;i++)
{
a[i]=rand()%1000; //给数组赋随机数
printf("%d ",a[i]);
}
puts("");
puts("");
//int a[]={491,381,615,917,716,13,217,419,19,138,61,917,176,113,27,419,419,38,615,917,16,113,217,419};
int size = sizeof(a)/sizeof(int); //计算数组长度
bucket_sort(a,size,10);//数组名，数组长度，桶的个数
}
