您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

数据结构与算法 ---- 详解堆排序、桶排序、基数排序及比较器内容(二)

时间:05-13来源:作者:点击数:

前言

本章内容前文 (不影响本章阅读)

数据结构与算法 ---- 详解堆排序、桶排序、基数排序及比较器内容(一)

一、比较器的使用

1)比较器的实质就是重载比较运算符

2)比较器可以很好的应用在特殊标准的排序上

3)比较器可以很好的应用在特殊标准排序的结构上

我们都知道,java.util.Arrays下面提供了一种将指定的列表按从小到大排序的方法----sort()

拿参数为数组的sort举例

    /**
     * 将指定的数组按数字升序排序
     *
     * 参数:a - 要排序的数组
     */
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

它的底层原理涉及到快速排序、归并排序、插入排序等等,这里就暂不追究了。它的作用是将一组数从小到大排序,例如:

    public static void main(String[] args) {
        int[] arr = {6,7,5,1,2,3,9};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

运行结果:[1, 2, 3, 5, 6, 7, 9]

到这里,如果你觉得sort()的用法仅此是升序排序,那就大大错了!

事实上,Arrays.sort()方法是有两个参数的

在这里插入图片描述

第二个参数就是确定数组顺序的比较器。如果指定了比较器,我们就可以根据该比较器的规则对某个对象进行排序。

好了,现在我有这样一个需求:我有一个Student对象,一共有三个属性,并给初始化值放到Student[]数组中,请问,我要如何实现按id升序(降序)呢?

    public static class Student{
        public String name;   //姓名
        public int id;		 //id
        public int age;		//年龄

        public Student(String name, int id, int age) {
            this.name = name;
            this.id = id;
            this.age = age;
        }
        
    public static void main(String[] args) {
        Student student1 = new Student("A",2,20);
        Student student2 = new Student("B",3,21);
        Student student3 = new Student("C",1,22);
        Student[] students = new Student[]{student1,student2,student3};
        }

答案是:实现Comparator接口,重写compare方法

首先要知道,比较器这样几个原则:

1)返回负数的时候,第一个参数排在前面

2)返回正数的时候,第二个参数排在前面

3)返回0的时候,谁在前面无所谓

也就是说,我们控制好返回值,就能决定排序顺序

    //按id升序
    public static class IdAscendingComparator implements java.util.Comparator<Student>{
        @Override
        public int compare(Student o1, Student o2) {
            return o1.id - o2.id;   //2-3<0,升序
        }
    }
    //按id降序
    public static class IdDescendinComparator implements java.util.Comparator<Student>{
        @Override
        public int compare(Student o1, Student o2) {
            return o2.id - o1.id;  //3-2>0,降序
        }
    }

测试如下

    public static void main(String[] args) {
        Student student1 = new Student("A",2,20);
        Student student2 = new Student("B",3,21);
        Student student3 = new Student("C",1,22);

        Student[] students = new Student[]{student1,student2,student3};
        //按照id升序比较
        System.out.println("按id升序");
        Arrays.sort(students,new IdAscendingComparator());
        printStudent(students);
        System.out.println("=============================");
        //按照id降序比较
        System.out.println("按id降序");
        Arrays.sort(students,new IdDescendinComparator());
        printStudent(students);
    }
    public static void printStudent(Student[] students){
        for (Student stu: students){
            System.out.println(stu);
        }
    }
在这里插入图片描述

这就是比较器的一个基本使用方式

这里补充一下上一篇堆排序的比较器的使用

数据结构与算法 ---- 详解堆排序、桶排序、基数排序及比较器内容(一)

PriorityQueue<Integer> heap = new PriorityQueue<>()

java中PriorityQueue优先级队列是默认从小到大排序的,如果要实现一组数从大到小排序,那就要指定比较器,结合刚刚所知,代码如下

    public static class Acomp implements Comparator<Integer>{
        //如果返回负数,认为第一个参数应该放在上面
        //如果返回正数,认为第二个参数应该放在上面
        //如果返回0,认为谁放在上面都行
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Acomp());
        heap.add(6);
        heap.add(9);
        heap.add(3);
        heap.add(2);
        heap.add(10);
        while (!heap.isEmpty()){
            System.out.println(heap.poll());  //大根堆
        }
    }

运行结果:10,9,6,3,2

Process finished with exit code 0

二、桶排序

桶排序思想下的排序

1)计数排序

2)基数排序

分析:

1)桶排序思想下的排序都是不基于比较的排序

2)时间复杂度为O(N),额外空间复杂度O(M)

3)应用范围有限,需要样本的诗句状况能满足桶的划分

桶排序的原理

桶排序的原理其实十分简单,一组数,出桶入桶就完成了排序。为什么说他是不基于比较的排序呢?

假设某个班成绩数据A2,A4,A6,A1,A3…An(总之数据是无序的,A1<A2…且数据长度小于等于M),要将它们进行排序。那么我先准备一个大小为M的称为count的数组

在这里插入图片描述

count有M个单元(或称为桶),依次将数据放入指定桶内,初始为0。当每读入Ai的时候,对应count[Ai]增1(类似于一个计数器),然后依次出桶完成排序

在这里插入图片描述

这就是桶排序的原理,也是计数排序思想。它的时间复杂度为O(N),空间复杂度为O(M)。但是,这个算法也有缺陷,如果我需求的数据很大的话,那是不是意味着我的桶的数量也要非常大,这就很消耗空间内存。

对于“桶”概念有了一定的了解后,我们再来看看基数排序,这也是一个十分重要的排序。

三、基数排序

基数排序原理

像刚刚说的,如果给一个值域很大的一堆数,我要对其进行排序。显然不能用桶排序,那样需要准备太多桶了。

所以,基数排序的思想就从准备n个桶转变为进行n趟桶排序,利用从低位“数字”到高为“数字”不断的进桶出桶完成排序。什么意思呢?举个例子

我有一组初始元素

[051,026,160,234,445,202]

因为所有位上最大的数只有6,所以我准备7个桶(0~6),按照个位、十位、百位顺序依次进桶,如图所示:

在这里插入图片描述

这样三趟进出桶,就完成了排序,这里桶的实现是队列(先进先出)。

为什么按照这样的方式就能完成排序呢?

因为,基数排序可以看做是一个优先级排序(本人理解)。

拿“160”“234”来看,

1)按个位进出桶后,“234”排后面(因为它个位数大);

2)按十位进出桶后,“160”在后面

3)按百位进出桶后,“234”最终排在“160后面”

也就是说,个位、十位、百位的优先级是逐渐递增的,优先级越高,越往后走,所以最终只需要三趟就能完成排序。

代码实现

import java.util.Arrays;

//基数排序
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {4,6,9,7,2,5,3};
        radixSort(arr);
    }
    public static void radixSort(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        System.out.println(Arrays.toString(radixSort(arr,0,arr.length-1,maxbits(arr))));
        //radixSort(arr,0,arr.length-1,maxbits(arr));
    }
    //在L。。R上排序;digit是这一批数字中最大的值有多少个十进制为
    public static int[] radixSort(int[] arr,int L,int R,int digit){
        final int radix = 10;   //以10位基地
        int i = 0,j=0;
        //有多少个数准备多少个辅助空间
        int[] bucket = new int[R-L+1];
        for (int d = 1;d<=digit;d++){ //有多少位就进出几次
            //10个空间
            //count[0] 当前位(d位)是0的数字有多少个
            //count[1] 当前位(d位)是(0和1)的数字有多少个
            //count[2] 当前位(d位)是(0\1和2)的数字有多少个
            //count[i] 当前位(d位)是(0~i)的数字有多少个
            int[] count = new int[radix];  //count[0..9]
            for (i = L;i<=R;i++){
                j = getDigit(arr[i],d);  //d是1取个位,d是2取十位......
                count[j]++;   //计数器+1
            }
            for (i = 1 ; i<radix;i++){
                count[i] = count[i] + count[i-1];  //累加,看某位数比i位数值小的有多少个
            }
            //数组从右往左遍历
            for (i = R; i>=L;i--){
                j = getDigit(arr[i],d);
                bucket[count[j] - 1] =arr[i]; //从右往左把数放进新数组中
                count[j]--;  //计数器-1
            }
            for (i=L,j=0;i<=R;i++,j++){
                arr[i] = bucket[j];    //把新数组中的数放回arr[i],再继续出桶入桶,直到有序
            }
        }
        return arr;
    }
    //最大值的位数
    public static int maxbits(int[] arr){
        int max = Integer.MIN_VALUE;
        //遍历过程中找到最大值
        for (int i = 0;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        //res用来表示最大值有多少十进制位
        int res = 0;
        while (max !=0){
            res++;
            max /= 10;
        }
        return res;
    }
    //取个位上的数
    public static int getDigit(int x,int d){
        return ((x/((int)Math.pow(10,d-1)))%10);
    }
}

测试结果:[2, 3, 4, 5, 6, 7, 9]

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门