桶排序 Bin Sort

 
 
  
  
  桶排序 Bin Sort
  
  
平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则   假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。 
  
  
桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在   一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。 
  
  
在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤ A[i]