桶排序是一种排序的思想，其实现包括计数排序和基数排序两种，冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序都是基于比较的排序，而桶排序提出了一种新的思路，即基于数据状态的排序。
1. 桶排序的思想
(1) 得到无序数组的取值范围
(2) 根据取值范围"创建"对应数量的"桶"
(3) 遍历数组，把每个元素放到对应的"桶"中
(4) 按照顺序遍历桶中的每个元素，依次放到数组中，即可完成数组的排序。
"桶"是一种容器，这个容器可以用多种数据结构实现，包括数组、队列或者栈。
2. 复杂度
- 时间复杂度：遍历数组求最大值最小值为O(n)，遍历数组放入"桶"中复杂度为O(n)，遍历桶取出每个值的复杂度为O(n)，最终的时间复杂度为O(3n)，也就是O(n)
- 空间复杂度：额外的空间取决于元素的取值范围，总的来说为O(n)
- 稳定性：桶排序是否稳定取决于"桶"用什么数据结构实现，如果是队列，那么可以保证相同的元素"取出去"后的相对位置与"放进来"之前是相同的，即排序是稳定的，而如果用栈来实现"桶"，则排序一定是不稳定的，因为桶排序可以做到稳定，所以桶排序是稳定的排序算法
3. 桶排序的实现之计数排序
(1) 计数排序图示过程
- 找出无序数组的最大值，创建一个长度为最大值+1的空数组
- 遍历原数组，统计每个元素出现的次数
- 遍历"桶"，即用于元素个数统计的数组，得到有序的数组
(2) 计数排序Java代码实现
public static void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
4. 桶排序的实现之基数排序（待更新）
(1) 基数排序图示过程
(2) 基数排序Java代码实现
