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

前言

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

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

一、比较器的使用

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]