东莞网站建设制作免费咨新媒体运营培训学校
1.前言
因为昨天写了一个基数排序，今天我来写一道用基数排序实现的题解，希望可以帮助你理解基数排序。
这个题本身不难，就是线性时间和线性额外空间(O(n))的算法，有点难实现
基数排序的时间复杂度是O(d*(n+radix))，其中d是最大值的位数，n是数组长度，radix是基数（10）然后化简就是 O(n)
2.思路分析
-
首先，找到待排序数组中的最大值，确定最大值的位数。假设最大值是max，位数是d。
-
创建10个桶（0-9），每个桶用来存放对应位数上的数字。
-
从低位（个位）开始，根据当前位数的值将待排序数组中的数字放入对应的桶中。
-
将桶中的数字按照顺序取出，覆盖原数组，然后进入下一位数的排序。
-
重复步骤3和步骤4，直到排完最高位（即 d 位）。
-
最后，遍历排序后的数组，计算相邻数字之间的差值，找到最大的差值，即为最大间距。
3.代码实现
这里我获取最大值最小值使用了stream流，下面我来介绍一下
int maxVal = Arrays.stream(arr).max().getAsInt(); 获取最大值
//Arrays.stream(arr) 将数组转换为一个流。
//max() 方法找到流中的最大值，返回一个 OptionalInt 对象。
//getAsInt() 方法从 OptionalInt 对象中获取最大值作为 int 类型的值。如果最大值不存在（即数组为空），则会抛出 NoSuchElementException 异常。
/*
* 基数排序实现 求相邻元素的差值(最大间距)
*
* */import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class sortHomework3 {public static int maximumGap(int[] nums) {radixSort(nums);int r = 0;for (int i = 1; i < nums.length; i++) {r = Math.max(r,nums[i] - nums[i - 1]);}return r;}public static void radixSort(int[] arr) {if (arr == null || arr.length == 0){return;}int max = Arrays.stream(arr).max().getAsInt();//获得最大值,确定最高位数int min = Arrays.stream(arr).min().getAsInt();//获得最小值int digit = 1; // 从最低位开始排序int base = 10; // 基数为10，即十进制(是个桶)// 转换负数为正数if (min < 0) {max -= min;for (int i = 0; i < arr.length; i++) {arr[i] -= min;}}while(max / digit > 0){countingSort(arr, base, digit);digit *= base;//处理更高位数}//排序完毕后// 将转换后的正数转换回负数if (min < 0) {for (int i = 0; i < arr.length; i++) {arr[i] += min;}}}private static void countingSort(int[] arr, int base, int digit) {// 定义桶的大小 (里面的泛型<表示动态数组>)为10个桶List<List<Integer>> buckets = new ArrayList<>(10);for (int i = 0; i < 10; i++) {buckets.add(new ArrayList<>()); // 创建空的桶(不创建空桶默认里面存的都是null不是桶)}for (int i : arr) {int index = i / digit % base;//获得位数buckets.get(index).add(i);//添加到集合中}int k = 0;//将元素在插入arr中for (int i = 0; i < buckets.size(); i++) {if (buckets.get(i).isEmpty()){continue;}//把各个桶中的元素存储到数组中for (int j = 0; j < buckets.get(i).size(); j++) {arr[k++] = buckets.get(i).get(j);}//取出来一个桶,咱就删除一个桶buckets.get(i).clear();}}public static void main(String[] args) {int[] arr = {5, 2, 8000, 3, 1};int[] expected = {1, 2, 3, 5, 8};System.out.println(Arrays.toString(arr));maximumGap(arr);System.out.println(Arrays.toString(arr));}
}