桶排序（代码自己写）

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。  

  例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

  可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储  

  (10..20]的整数，……集合B[i]存储(   (i-1)*10,   i*10]的整数，i   =   1,2,..100。总共有  

  100个桶。  

  然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。  

  然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任  

  何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这  

  样就得到所有数字排好序的一个序列了。  

  假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果  

  对每个桶中的数字采用快速排序，那么整个算法的复杂度是  

 

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

 

  从上式看出，当m接近n的时候，桶排序复杂度接近O(n)  

  当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  

  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的  

  排序了。  

需要特别注意的是桶的大小不能设置得太小，否则当随机数据堆积在一个小的范围是，会

造成桶的溢出（数组越界）

(以上代码是互联网上转来的，再次谢过)