摘要
桶排序和基数排序类似，相当于基数排序的另外一种逻辑。它是将取值范围当做创建桶的数量，桶的长度就是序列的大小。通过处理比较元素的数值，把元素放在桶的特定位置，然后遍历桶，就可以得到有序的序列。
逻辑
创建一定数量的桶（数组或者链表）。制定规则将序列中的元素均匀地分布在不同的桶中。然后对每个桶内排序，最后合并非空的桶。
流程
- 创建一定数量的桶
- 元素均匀分布在桶中（根据规则来看）
- 桶内排序
- 合并非空的桶
下面还用无序的整数元素序列，将这个序列给排序有序。
实现
获取序列中的最大值，这里按照最大值有多少位，来确定外部循环多少次后得到有序的序列，也就是每一位都会循环遍历比较。
// 获取最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
桶排序实现方法
每一个整数的进制位是 0 到 9 这 10 个数，所以这里就创建10个桶，分别对应这10个数，每个桶的高度就是序列的长度。
下一步就是创建记录每个桶大小的数组，来放置元素个数，在取出桶中的元素时，就可以确定遍历的长度，减少遍历无用的空间。同时这是元素在桶中的索引位置。
// 桶数组
int[][] buckets = new int[10][array.length];
// 每个桶中的元素数量
int[] bucketSizes = new int[buckets.length];
接下来，就是根据最大值的进位数量，从个位进位开始对元素进行处理排序，bucketSizes 记录对应位置数值的数量，并提供给 buckets 数组在桶中的元素索引位置。
这里比较难理解一些，比如有 23和43 这两个数据，若从个位开始处理，因为个位都是 3，那么放在桶中的位置应该是 buckets[3][0]。如果是这样，23 会被后来的 43 覆盖。那么就用一个记录 3 数值出现次数的数组，即 bucketSizes[3]，当存放 23 之后，bucketSizes[3] 加 1, 那么后面放 43 的时候，它的位置就是 buckets[3][1], 避免了覆盖。
当所有元素放置完成之后，就遍历 buckets 桶，依次取出元素，在遍历桶循环时，每个桶遍历的最大值就是 bucketSizes 中的数量，就不需要把桶的长度全部遍历完，减少遍历次数。
for (int divider = 1; divider <= max; divider *= 10) {
for (int i = 0; i < array.length; i++) {
int no = array[i] / divider % 10;
buckets[no][bucketSizes[no] ++] = array[i];
}
}
int index = 0;
for (int i = 0; i < buckets.length; i++) {
for (int j = 0; j < bucketSizes[i]; j++) {
array[index ++] = buckets[i][j];
}
bucketSizes[i] = 0;
}
时间和空间复杂度
- 时间复杂度：O(n + n * logn - n * logm)
- 空间复杂度：O(n+m)
- 属于稳定排序
m 是桶的数量
