箱排序的变种。为了区别于上述的箱排序，姑且称它为桶排序（实际上箱排序和桶排序是同义词）。
桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0，1)上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。
注意：
这种排序思想基于以下假设：假设输入的n个关键字序列是随机分布在区间[0，1)之上。若关键字序列的取值范围不是该区间，只要其取值均非负，我们总能将所有关键字除以某一合适的数，将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0，1)上的。
桶排序的平均时间复杂度是线性的，即O(n)。
箱排序只适用于关键字取值范围较小的情况，否则所需箱子的数目m太多导致浪费存储空间和计算时间。
例如n=10，被排序的记录关键字ki取值范围是0到99之间的整数(36，5，16，98，95，47, 32，36，48)时，要用100个箱子来做一趟箱排序。（即若m=n2时，箱排序的时间O(m+n)=O(n2)）。
例子
一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<iostream.h> #include<malloc.h> typedef struct node{ int key; struct node * next; }KeyNode; void inc_sort(int keys[],int size,int bucket_size){ KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); for(int i=0;i<bucket_size;i++){ bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); bucket_table[i]->key=0; //记录当前桶中的数据量 bucket_table[i]->next=NULL; } for(int j=0;j<size;j++){ KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode)); node->key=keys[j]; node->next=NULL; //映射函数计算桶号 int index=keys[j]/10; //初始化P成为桶中数据链表的头指针 KeyNode *p=bucket_table[index]; //该桶中还没有数据 if(p->key==0){ bucket_table[index]->next=node; (bucket_table[index]->key)++; }else{ //链表结构的插入排序 while(p->next!=NULL&&p->next->key<=node->key) p=p->next; node->next=p->next; p->next=node; (bucket_table[index]->key)++; } } //打印结果 for(int b=0;b<bucket_size;b++) for(KeyNode *k=bucket_table[b]->next; k!=NULL; k=k->next) cout<<k->key<<" "; cout<<endl; } void main(){ int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); inc_sort(raw,size,10); } |
上面源代码的桶内数据排序，我们使用了基于单链表的直接插入排序算法。可以使用基于双向链表的快排算法提高效率。
