桶排序

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