程序算法艺术与实践:经典排序算法之桶排序
最后更新于：2022-04-01 21:40:49
桶排序Bucket Sort从1956年就开始被使用，该算法的基本思想是由E.J.Issac R.C.Singleton提出来。本博介绍BucketSort算法相关知识。
#### 算法描述与伪代码
假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果.算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中**.**最后将所有的链表依次连接起来就是排序结果.这个过程可以简单的分步如下:
1. 设置一个定量的数组当作空桶子。
1. 寻访序列，并且把项目一个一个放到对应的桶子去。
1. 对每个不是空的桶子进行排序。
1. 从不是空的桶子里把项目再放回原来的序列中。
注意:1)note: 待排序元素越均匀, 桶排序的效率越高. 均匀意味着每个桶在中间过程中容纳的元素个数都差不多,不会出现特别少或者特别多的情况, 这样在排序子程序进行桶内排序的过程中会达到最优效率.2)note: 将元素通过恰当的映射关系将元素尽量等数量的分到各个桶(值区间)里面, 这个映射关系就是桶排序算法的关键.桶的标记(数组索引Index)的大小也要和值区间有对应关系
~~~
BUCKET_SORT (A)
n ← length [A]
For i = 1 to n do
Insert A[i] into list B[nA[i]]
For i = 0 to n-1 do
Sort list B with Insertion sort
Concatenate the lists B[0], B[1], . . B[n-1] together in order.
~~~
**映射函数**bindex=f(key) 其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1key=0;
bucket_table[i]->next=NULL;
}
for(int j=0;jkey=A[j];
node->next=NULL;
int index=A[j]/10;
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)++;
}
}
}
~~~
注：上述部分codes采用桶内数据排序，我们使用了基于单链表的直接插入排序算法。可以使用基于双向链表的快排算法提高效率。
关于[程序算法艺术与实践](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多讨论与交流，敬请关注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).
';