例如：待排数字[6 2 4 1 5 9]
准备10个空桶,最大数个空桶
[6 2 4 1 5 9] 待排数组
[0 0 0 0 0 0 0 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号
1）顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,实现过程:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]
[6 2 4 1 5 9] 待排数组
[0 0 0 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
2）顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶
[6 2 4 1 5 9] 待排数组
[0 0 2 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
3,4,5,6省略,过程一样,全部入桶后变成下边这样
[6 2 4 1 5 9] 待排数组
[0 1 2 0 4 5 6 0 0 9] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9
示例源码：
测试输出：
空间复杂度
O(n)
时间复杂度
桶排序可以做到线性时间复杂度，比如10万个人的年龄排序。将10万条年龄数据输入，复杂度是O(N)，输出排序结果时遍历每个桶复杂度是O(M)，故总时间复杂度是O(M N)。而这种情况下桶的个数远远小于数据条数。
对于使用多趟桶排序的情形，时间复杂度是O(p*(N M))，其中N是输入的数据量，M是桶的个数，p是桶排序的趟数。
稳定性分析
桶排序是稳定的，对于相同的元素都是按待排次序放入到桶中的，再从桶中收集的时候也是按原来顺序收集的，不会改变顺序。
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，原理是假设初始序列有n个记录，则可以看成是n个有序的子序列，每个序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，...,如此重复，直至得到一个长度为n的有序序列。
归并排序示例：待排数组为{49,38,65,97,76,13,27}
设r[i…n]由两个有序子表r[i…m]和r[m 1…n]组成，两个子表长度分别为n-m 1、n-m。
- j=m 1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
- 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
- //选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i ； k ； 转⑵
否则，rf[k]=r[j]； j ； k ； 转⑵ - //将尚未处理完的子表中元素存入rf
如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空 - 合并结束。
案例实现：
比如初始数组：[24,13,26,1,2,27,38,15]
①分成了两个大小相等的子数组：[24,13,26,1] [2,27,38,15]
②再划分成了四个大小相等的子数组：[24,13] [26,1] [2,27] [38,15]
③此时，left 左边的下标< right 右下标还是成立，再分：[24] [13] [26] [1] [2] [27] [38] [15]
此时，有8个小数组，每个数组都可以视为有序的数组了！
