时间复杂度：O(N)
额外空间复杂度：O(N)
是否可实现稳定性：否
思路：
桶排序的思路：首先找到数组中的最大值，然后新建一个数组，bucket 此数组的长度是数组最大值+1，其实新建的这个数组中的下标值就是原数组的数据值，这里为什么长度是数组最大值加一呢
注意*：是因为比如数组最大值是9，然后如果你设置bucket数组的长度为9，那么他的下标最大值就是8，那么原数组的9就没有桶存了
好了继续，找到最大值后，开始遍历原数组，把原数组的数据加入bucket的下表中，bucket[i]，每当有1个i bucket[i]的值就加一， 然后已经装入桶后， 遍历桶，如果bucket[j]位置-->0就说明此下标有数据，也就是说，此下标在原数组里有这个值， 然后排序 就是从大到小了 arr[i++]=j;
代码：
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;
}
}
}
利用桶排序思想做题：
荷兰国旗类问题：
题目要求：求一个数组排序后相邻值的最大差值 排序的时间复杂度为O（n）
思路：
思路：找出数组中的最小值和最大值，一共有n个数就创建n+1个桶，把最小值放入第一个桶，最大值放到最后一个桶， 然后每一个桶都有一个存值的范围 范围的求法 (max-min)/桶的个数
比如 1 4 3 2 范围就是1-1.6 1.6-2.2 2.2-2.8 2.8-3.4 3.4-4
然后五个桶的编号从0开始 因为存桶的数组的下标从0开始，然后开始装数 ((num - min) * len / (max - min)); 正常理解应该*（len+1）但是因为桶的下标从0开始 所以 *len
最重要的原理是 用后一个桶的最小值减去上一个桶的最大值， 找出这样的最大值 就是最大差值，因为一个桶内的差值肯定不超过桶的范围
代码：
public static int maxGap(int[] nums){
if (nums==null||nums.length<2){
return 0;
}
//通常写法
int len = nums.length;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0;i<len;i++){
min = Math.min(min,nums[i]);
max = Math.max(max,nums[i]);
}
//最小值最大值相等就返回0
if (max==min){
return 0;
}
//桶的编号
int bid = 0;
//三个平型数组，记录同一编号，即一个桶的信息
int[] mins = new int[len+1];
int[] maxs = new int[len+1];
boolean[] hasNum = new boolean[len + 1];
for (int i =0;i<len;i++){
//数组值装桶
bid = bucket(nums[i], len, min, max);
//每次比较桶内的最小值
mins[bid] = hasNum[bid] ? Math.min(mins[bid],nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
//第一个桶的最大值
int lastMax = maxs[0];
int i = 1;
//小于等于len是因为比如三个数 四个桶，最大最小数放在第一个最后一个同，这样就能把每一个桶遍历到
for (;i<=len;i++){
if (hasNum[i]){
res = Math.max(res,mins[i]-lastMax);
lastMax = maxs[i];
}
}
return res;
}
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
