桶排序思想

无序数组排序后的最大相邻差
有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。

解法一：先排序再遍历

解法二：结合计数排序思想

1. 利用计数排序的思想，先求出原数组的最大值 max 与最小值 min 的区间长度 k（k=max-min+1），以及偏移量 d =min。
2. 创建一个长度为 k 的新数组 Array。
3. 遍历原数组，每遍历一个元素，就把新数组 Array 对应下标的值 +1。例如原数组元素的值为 n，则将Array[n -min] 的值加 1。遍历结束后，Array 的一部分元素值变成了 1 或更高的数值，一部分元素值仍然是 0。

4. 遍历新数组 Array，统计出 Array 中最大连续出现 0 值的次数 +1，即为相邻元素最大差值。

   解法三：桶排序思想

5. 利用桶排序的思想，根据原数组的长度 n ，创建出 n 个桶，每一个桶代表一个区间范围。其中第 1 个桶从原数组的最小值 min 开始，区间跨度是（max-min）/（n -1）。

6. 遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值。
7. 遍历所有的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。 ```java // 桶 private static class Bucket { Integer min; Integer max; }

public static int getMaxSortedDistance(int[] array) { // 得到数列的最大值和最小值 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) max = array[i]; if (array[i] < min) min = array[i]; } int d = max - min; // 如果 max 和 min 相等，说明数组所有元素都相等，返回 0 if (d == 0) return 0; // 初始化桶 int bucketNum = array.length; Bucket[] buckets = new Bucket[bucketNum]; for (int i = 0; i < bucketNum; i++) { buckets[i] = new Bucket(); } // 遍历原始数组，确定每个桶的最大最小值 for (int i = 0; i < array.length; i++) { // 确定数组元素所属的桶下标 int index = ((array[i] - min) * (bucketNum - 1) / d); if (buckets[index].min == null || buckets[index].min > array[i]) { buckets[index].min = array[i]; } if (buckets[index].max == null || buckets[index].max < array[i]) { buckets[index].max = array[i]; } } // 遍历桶，找到最大差值 int leftMax = buckets[0].max; int maxDistance = 0; for (int i = 1; i < buckets.length; i++) { if (buckets[i].min == null) { continue; } if (buckets[i].min - leftMax > maxDistance) { maxDistance = buckets[i].min - leftMax; } leftMax = buckets[i].max; } return maxDistance; } ``` 时间复杂度