桶排序思想介绍：桶排序介绍 相邻两数最大差值问题 有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n
思路：
- 定义一个长度为待排序数组arr,长度为length, 然后用一个length 1的数组用来抽象的表示桶；
- 取出arr中的最小值和最大值，把min到max范围等分成length 1份，根据((num - min) * len / (max - min))将每个元素分到length 1个桶中。其中必存在至少一个空桶。
- 因为空桶的存在，最大差值一定不来自同一个桶中。因为从1号桶开始（因为0号桶一定非空），如果是空的，跳到下一个桶，如果是非空的，找前一个非空桶。对于每一个非空桶，都找它前一个非空桶的max和当前这个桶的min，通过max-min计算差值，去其中最大的一个。
问题：最大差值一定来自空桶的左右两个桶吗？
如上图所示，显然不是。方法的空桶只是用来排除最大差值在同一桶中出现可能。
代码语言：javascript复制public class findMaxGap {
public static int maxGap(int[] arr){
if(arr == null || arr.length < 2){
return 0;
}
//获得数组最大最小值
int len = arr.length;
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;
for (int i = 0; i < len; i ) {
min = Math.min(min, arr[i]);
max = Math.max(max, arr[i]);
}
if(min == max) {
return 0;
}
//将数组等分为length 1
//每一个同桶中，只存储最大、最小值，和判断桶中是否有元素的bool变量
boolean[] hasNum = new boolean[len 1];
int[] maxs = new int[len 1];
int[] mins = new int[len 1];
int bid = 0;
for (int i = 0; i < len; i ) {
bid = bucket(arr[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
for (int i = 1; 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));
}
}
