桶排序

桶排序(Bucket sort)是一种基于计数的排序算法（计数排序可参考上节的内容），工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）

算法步骤

设置固定数量的空桶。

把数据放到对应的桶中。

对每个不为空的桶中数据进行排序。

拼接不为空的桶中数据，得到结果。

图解过程

复杂度及应用分析：

桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)。

小结

在此说明一下，在创建桶的时候，桶和桶之间的数值间距不是一定要定义为1，可以定义为任意数值，要适情况而定，比如当知道要排序的数值在0-100之间，就可以定义10个桶，桶与桶间的距离为10。
桶排序适用在知道要排序数值的范围的情况下，若不知道范围，最好不要适用该算法。
桶排序是典型的以空间换时间的排序算法

在使用桶排序的时候，有一个小技巧，比如定义每个桶的容量为10，每个桶中的第一个数据要定义为该桶中已经存入的数据的个数，也就是每个桶的实际容量为9，这样做的好处是可以直接知道该桶中下一个将要存入的数据的位置
（应用：P1068 分数线划定代码的12、13行）