1.桶排序特点
1.待排序数服从均匀分布；
2.待排序数可分配到多个单调的部分；
3..待排序数分配到哪个部分实现容易；
4.平局情况下时间复杂度为O(n)；
如下图，即把排序数分配到M1，M2 ... M(k-1), M(k)这k分部分，且M(i) < M(j) ,i < j时。
算法-桶排序1.png
2.桶排序介绍
桶排序，假设输入数据服从均匀分布，平局情况下它的时间复杂度为O(n)。把输入数据可以均匀映射到区间[0,1)上，再把区间[0,1)划分为n个相同大小的子区间，该子区间就称为桶，然后将n个输入数分别放到各个桶中，因为输入数是均匀独立分布在[0,1)区间，所以一般不会出现很多数集中落入一个桶内，对每个桶内的数进行排序，然后按桶的大小次序列出每个桶中排序好的数。
3.桶排序的伪代码
BUCKET-SORT(A)
1 n = A.length
2 let B[0..n-1] be a new array
3 for i = 0 to n-1
4 make B[i] an empty list
5 for i = 0 to n-1
6 把A[i]插入到B[f(A[i])]桶中 // 该处的f(x)函数为一一映射函数，把A[i]映射[0,1)区间的某个数
7 for i = 0 to n-1
8 排序B[i]桶内的数
9 列出B[0],B[1] ... B[n-1]桶中的数即为排序好的顺序
实例如下图：
算法-桶排序2.png
4.时间和空间复杂度分析
1.时间复杂度
第1步，时间复杂度1
第2步，时间复杂度n
第3步，时间复杂度n
第4步，时间复杂度1
第5步，时间复杂度n
第6步，时间复杂度1
第7步，时间复杂度n
第8步，时间复杂度期望为2-1/n（这个与排序数均匀分布在各个桶有关）
第9步，时间复杂度n
因此时间复杂度为O(n)。
2.空间复杂度
多了B[0..n-1]且B[i]是一个列表，B[i]的期望空间是1
