工程上用得不多，主要原因是得知道数据范围。最主要的意义在于，有利于发挥计算机的存储性。
/** * 〈一句话功能简述〉<br> * 〈桶排序,基于计数的桶〉 * * @author Administrator * @create 2019/5/25 * @since 1.0.0 */ public class BucketSort { 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];//建立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; } } }
很锻练自己coding能力的一个练习，值得深究，即如何用计算机优势实现物理动作的过程。查找最大值，时间和空间复杂度都为O(n)
/** * 〈一句话功能简述〉<br> * 〈排序后最大差值查找〉 * * @author Administrator * @create 2019/5/28 * @since 1.0.0 */ public class MaxGap { public static int maxGap(int[] arr) { if (arr == null || arr.length < 2) return 0; int len = arr.length; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max , arr[i]); min = Math.min(min , arr[i]);//找出数组里的最大数与最小数 } if (max == min) return 0; //这里是有数组里有Ｎ个数，那么分配Ｎ+１个桶这与基于基数的桶排序（按照最大数max作为分配桶的个数）是不同的 boolean[] hasNum = new boolean[len + 1];//这个桶进没进数的标志 int[] maxs = new int[len + 1];//记录每个桶里面的最大数 int[] mins = new int[len + 1]; int serialNum;//桶编号 以下是，找一个桶编号下对应的最大值与最小值 for (int i = 0; i < len; i++) { serialNum = bucket(arr[i] , len , max , min); maxs[serialNum] = hasNum[serialNum] ? Math.max(maxs[serialNum] , arr[i]) : arr[i];//依次找出数组中此桶号的最大值与最小值 mins[serialNum] = hasNum[serialNum] ? Math.min(mins[serialNum] , arr[i]) : arr[i]; hasNum[serialNum] = 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 max , long min) { return (int) ((num - min) * len / (max - min));//此处正是此问题的逻辑，这体现了算法的本质是数学问题，如何求某数放到哪个桶号的桶中呢？ //桶号／桶的总个数与(num-min)/(max-min) } public static int[] generaterRodomArray(int maxSize , int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//创建一个从0到maxSize+1 for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()); } return arr; } public static void printArr(int[] arr) { if (arr == null) return; for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int maxvalue = 100; int maxsize = 100; int resNum; int[] arr = generaterRodomArray(maxsize , maxvalue); printArr(arr); resNum = maxGap(arr); System.out.println(resNum); } }
