桶排序
本次介绍的这个桶排序，用的比较少，下面分析其思想。
思想：遍历数组,找到数组中的最大值和最小值,计算差值,然后选择桶的个数，有了差值和桶个数,进而可以确定每个桶的取值范围，之后再次遍历数组,将元素放入桶中,对每个桶内的元素排序,最后依次输出桶内值，如果桶用数组表示,那么数组的大小必须是原数组的大小,因为最坏情况下所有数在一个桶，这样的话,空间复杂度就高了，如果桶用链表的话,可以省空间,但是对桶内数据进行排序的时候,时间复杂度是O(N^2)。时间上又浪费，综上所述,省时间费空间,省空间费时间.所以桶排序一般不常用。
大O分析
1.时间复杂度
1）.求最大值最小值n
2）.桶初始化k
3）.遍历装桶n
4）.桶内排序n/k*log(n/k)*k
5）.结果输出n
6）.3n+k+n*log(n/k)约等于n+k
7）.最坏n方(一个桶)
8）.最好为n(n个桶而且值排列均匀)
2.空间复杂度
1）. n+k
2）. 但实际上空间做到最好的话,就只能用链表,时间就做不到最好.