分配排序——箱排序、桶排序、基数排序

1、分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。

详见 http://leowzy.iteye.com/blog/790413。

 

2、桶排序

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。 例如要对大小为[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个数字是平均分布这个假设的。这个假设是很强的，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

 

算法复杂度：

n是将n个元素装入不同的桶中，形如： 
for(i=1;i<=n;i++) 
放入合适的桶中; 
for(j=1;j<=m;j++) 
快排，复杂度为：O(n/m *log(n/m)) 

 

3、桶排序，详见 http://hxraid.iteye.com/blog/647759 和 http://www.cnblogs.com/sun/archive/2008/07/07/1237331.html。