算法九：桶排序(O(n))

定义：

　　假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数，基本思想将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]，B[0..n-1]是一指针数组，指向桶（链表）。

 

算法思想：

 

        算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果.

这个过程可以简单的分步如下:

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

note: 待排序元素越均匀, 桶排序的效率越高. 均匀意味着每个桶在中间过程中容纳的元素个数都差不多,不会出现特别少或者特别多的情况, 这样在排序子程序进行桶内排序的过程中会达到最优效率.

note: 将元素通过恰当的映射关系将元素尽量等数量的分到各个桶(值区间)里面, 这个映射关系就是桶排序算法的关键.桶的标记(数组索引Index)的大小也要和值区间有对应关系