桶排序应用之 【计算无序数组有序之后的最大相邻元素差】

1 题目

编写一个函数，传入一格无序的数组，返回无序数组排序之后的最大相邻元素的差。 举例：

输入：[5, 7, 2, 9, 10, 20, 44, 39] 输出：19

2 思路1（暴力破解）

先使用一种时间复杂度为O(logn)的排序算法将无序数组排好序然后在依次求相邻元素的差，并保存最大的差值。

这种方法肯定能解决该问题，但是这样做的算法时间复杂度太高，接近O(n*n)。

public int bruteForce(int []nums){ int distance = 0; QuickSort quickSort = new QuickSort(nums); quickSort.increaseSortBySingle(); for (int i = 0; i < nums.length-1; i++) { if (nums[i+1] - nums[i] > distance) distance = nums[i+1] - nums[i]; } return distance; }

其中，QuickSort类，参见这篇博文。

2.1 算法复杂度分析

快速排序的算法复杂度为O(nlogn)比较差值的算法复杂度为O(n)

所以该算法的时间复杂度为O(nlogn)。

3 思路2（桶排序）

使用桶排序的思想，每次只需将相邻桶之间的最大值（左侧桶）和最小值（右侧桶）进行比较即可，时间复杂度可以降到O(n)。 步骤：

先找出数组中的最大值和最小值得出桶的大小，并创建空桶给桶中放入元素，这里只需要放入本应该放入该桶中的最大值和最小值遍历所有桶，使用右侧桶的最小值减去左侧桶的最大值即是响铃元素的差 public int greatestGapSort(int[] nums) { //(1) 确定数组中的最大值和最小值 int min = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { min = Math.min(min, nums[i]); max = Math.max(max, nums[i]); } //（2）确定桶的长度，并创建空桶 int bucketNum = (max - min) / nums.length + 1; List<List<Integer>> bucket = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { bucket.add(new ArrayList<>()); } //(3) 计算每个桶的最大值和最小值，最小值放在0的位置，最大值放在1的位置 for (int i = 0; i < nums.length; i++) { int numIndex = (nums[i] - min) / nums.length; //确定桶中的最小值 if (bucket.get(numIndex).size() != 0) { if (nums[i] < bucket.get(numIndex).get(0)) bucket.get(numIndex).add(0, nums[i]); } else bucket.get(numIndex).add(0, nums[i]); //确定桶中的最大值 if (bucket.get(numIndex).size() >= 2) { if (nums[i] > bucket.get(numIndex).get(1)) bucket.get(numIndex).add(1, nums[i]); } else bucket.get(numIndex).add(1, nums[i]); } //(4) 计算有序之后的最大相邻差， int leftMax = 0;//用来保存前一个桶中的最大值 int distance = Integer.MIN_VALUE;//最大相邻差 for (int i = 0; i < bucketNum; i++) { if (bucket.get(i).size() != 0) { if (bucket.get(i).get(0) - leftMax > distance) //如果当前相邻值的差，大于之前的距离则覆盖之前的 distance = bucket.get(i).get(0) - leftMax; leftMax = bucket.get(i).get(1);//前一个桶的最大值移动 } } return distance; }