算法面试与实战-05排序算法- 时间复杂度为O(n)的排序算法（桶排序）
上期我们学习了计数排序，但是计数排序也有局限性，比如针对于double型就不好使用计数排序。所以本期我们学习另一种排序算法来解决非整型排序：桶排序。
概念:将数组分到有限数量的桶里，然后对每个桶进行分别排序（有可能使用别的排序算法或者递归继续使用桶排序）。桶排序的思想近乎彻底的分治思想。
那么桶是什么概念呢？每一个桶代表一个区间范围，里面可以承载一个或者多个元素。桶排序的第一步，就是创建这些桶。确定每一个桶的区间范围。比如下图：
具体多少个桶，如何确定桶的区间，有很多不同的方式。这里我们创建的桶的数量可以自定义。我们看看桶排序的主要步骤有哪些？
根据给定的桶的数量来确定每个桶的区间大小
区间大小=[最大值-最小值+1]/桶的数量
double bucketValue = Math.ceil((den + 1) / num);如果给的数组是整数的话，向上取整就好。
int bucketValue = (int) Math.ceil((den + 1)*1.0 / num);根据目标数组元素的下标来确定桶的编号
int index = (int) ((array[i] - min) / bucketValue);遍历目标数组将每个元素放到不同的桶中
对每个桶内的元素进行排序
遍历每一个桶的元素构建新的有序数组
大致步骤如上所示，那么具体代码是如何呢？
非整数类型的排序
public static double[] buckSortplus(double[] array,int num){//1、求出最值double min=array[0];double max=array[0];for (double i:array) {max=Math.max(max,i);min=Math.min(min,i);}//2、获取差值double den=max-min;//3、构建桶ArrayList<LinkedList<Double>> linkedLists = new ArrayList<>(num);//4、初始化桶数据double bucketValue = Math.ceil((den + 1) / num);//每个桶的区间大小for (int i = 0; i <num ; i++) {linkedLists.add(new LinkedList<Double>());}//5、对每个桶赋值for (int i = 0; i <array.length ; i++) {//获取桶的下标int index = (int) ((array[i] - min) / bucketValue);linkedLists.get(index).add(array[i]);}//6、对每个桶进行排序for (int i = 0; i <num ; i++) {Collections.sort(linkedLists.get(i));}//7、整合int flag=0;double[] newArray = new double[array.length];for (LinkedList<Double> linkedList:linkedLists) {for (double i:linkedList) {newArray[flag++]=i;}}return newArray;}
整数类型和上面也差不多，将double换成int即可。反正也写了贴出来如下：
public static void main(String[] args) {int[] array = {3, 17, 25, 56, 23, 87, 91, 22, 18, 34};int[] ints = buckSortplus(array, 5);System.out.println(Arrays.toString(ints));}public static int[] buckSortplus(int[] array,int num){//1、求出最值int min=array[0];int max=array[0];for (int i:array) {max=Math.max(max,i);min=Math.min(min,i);}//2、获取差值int den=max-min;//3、构建桶ArrayList<LinkedList<Integer>> linkedLists = new ArrayList<>(num);//4、初始化桶数据int bucketValue = (int) Math.ceil((den + 1)*1.0 / num);//每个桶的区间大小for (int i = 0; i <num ; i++) {linkedLists.add(new LinkedList<Integer>());}//5、对每个桶赋值for (int i = 0; i <array.length ; i++) {//获取桶的下标int index = (array[i] - min) / bucketValue;linkedLists.get(index).add(array[i]);}//6、对每个桶进行排序for (int i = 0; i <num ; i++) {Collections.sort(linkedLists.get(i));}//7、整合int flag=0;int[] newArray = new int[array.length];for (LinkedList<Integer> linkedList:linkedLists) {for (Integer i:linkedList) {newArray[flag++]=i;}}return newArray;}
关于比较经典的排序算法，暂时就是这些，后面一会不时的去补充，知识还是一个不断学习与巩固的过程。坚持共勉~
小结：数据结构与经典排序算法告一段落，总体来说比较拖沓，不够坚持，后面继续改变。下一阶段我准备分成几个方向
实战算法题学习
java基础整理