桶排序

基本思想

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计 数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间 [0，1]上。
　 桶排序的思想就是把区间[0，1]划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1]上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。
在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。桶排序的算法如下，其中floor(x)是地板函数，表示不超过x的最大整数。
桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。

PS:其实就是利用Hash表来排序。

算法实现

 
procedure Bin_Sort(var A:List);
begin
  n:=length(A);
  for i:=1 to n do
    将A[i]插到表B[floor(n*A[i])]中;
  for i:=0 to n-1 do
    对表B[i]进行排序;
  将表B[0],B[1],...,B[n-1]按顺序合并;
end;

原版权

整理筛选自http://www.bioisland.com/Algorithm/ShowArticle.asp?ArticleID=161