vlambda博客
学习文章列表

算法面试与实战-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基础整理