【算法&数据结构体系篇class06】：比较器

比眉伴天荒 2024-03-27 13:49 59阅读 0赞

> 业务中经常需要对数据做一个排序动作，比如有系统自带的比较函数，Arrays.sort(),对一个基础数据类型做排序，但我们业务中更多的数据类型是封装成一个对象，面向对象进行数据处理。而自己的实体类就需要自己来定义比较器了，用系统自带是无法实现的。

比较器有内部比较器和外部比较器，这里将外部比较器，拓展性更好

### 一、比较器核心 ###

*  定义一个比较器类，该类需要实现Comparator<T> 接口，然后类里需要实现抽象方法compare()方法，这里就是定义数据的排序方式，是升序还是降序。

*  compare()方法的返回值是int类型，这里需要注意返回值分三种 -1，0，1：

// 如果返回负数，认为方法的第一个参数(即对象)应该排在前面

// 如果返回正数，认为第二个参数应该排在前面

// 如果返回0，认为谁放前面无所谓

### 二、比较器代码 ###

自定义比较器类如下：

package class06;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    
    public class ShowComparator {
    
        public static class Student {
            public String name;
            public int id;
            public int age;
    
            public Student(String name, int id, int age) {
                this.name = name;
                this.id = id;
                this.age = age;
            }
        }
    
        // 谁id大，谁放前！
        public static class IdComparator implements Comparator<Student> {
    
            // 如果返回负数，认为第一个参数应该排在前面
            // 如果返回正数，认为第二个参数应该排在前面
            // 如果返回0，认为谁放前面无所谓
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.id < o2.id) {
                    return 1;
                } else if (o2.id < o1.id) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
        
        // 谁age大，谁放前！
        public static class AgeComparator implements Comparator<Student> {
    
            // 如果返回负数，认为第一个参数应该排在前面
            // 如果返回正数，认为第二个参数应该排在前面
            // 如果返回0，认为谁放前面无所谓
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age < o2.age) {
                    return 1;
                } else if (o2.age < o1.age) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
    
        public static void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        public static void printStudents(Student[] students) {
            for (int i = 0; i < students.length; i++) {
                System.out.println(students[i].name + ", " + students[i].id + ", " + students[i].age);
            }
        }
    
        public static void main(String[] args) {
            int[] arr = { 8, 1, 4, 1, 6, 8, 4, 1, 5, 8, 2, 3, 0 };
            printArray(arr);
            Arrays.sort(arr);
            printArray(arr);
    
            Student s1 = new Student("张三", 5, 27);
            Student s2 = new Student("李四", 1, 17);
            Student s3 = new Student("王五", 4, 29);
            Student s4 = new Student("赵六", 3, 9);
            Student s5 = new Student("左七", 2, 34);
    
            Student[] students = { s1, s2, s3, s4, s5 };
            printStudents(students);
            System.out.println("=======");
            Arrays.sort(students, new IdComparator());
            printStudents(students);
            System.out.println("=======");
    
            ArrayList<Student> arrList = new ArrayList<>();
            arrList.add(s1);
            arrList.add(s2);
            arrList.add(s3);
            arrList.add(s4);
            arrList.add(s5);
            for (Student s : arrList) {
                System.out.println(s.name + ", " + s.id + ", " + s.age);
            }
            System.out.println("=======");
            arrList.sort(new AgeComparator());
            for (Student s : arrList) {
                System.out.println(s.name + ", " + s.id + ", " + s.age);
            }
            System.out.println("=======");
            student1 = new Student("A", 4, 40);
            student2 = new Student("B", 4, 21);
            student3 = new Student("C", 5, 12);
            student4 = new Student("D", 4, 62);
            student5 = new Student("E", 4, 42);
    //注意这里有用TreeMap有序表保存对象做排序，键用的是自定义类对象类型，而且用了该类的id属性做比较器进行升序排序输//出，如果不定义比较器会报错显示该类没有实现比较器类无法识别比较。而有序表默认是按key做排序，基础数据类型会自带//排序，不需写比较器，且要求唯一不重复，同理用自定义类的id做比较器所以id不能重复添加，结果排序可以看到添加多个i//d=4的对象，只有第一个值为40的添加成功，其余都不能添加
            TreeMap<Student, String> treeMap = new TreeMap<>((a, b) -> (a.id - b.id));
            treeMap.put(student1, "我是学生1，我的名字叫A");
            treeMap.put(student2, "我是学生2，我的名字叫B");
            treeMap.put(student3, "我是学生3，我的名字叫C");
            treeMap.put(student4, "我是学生4，我的名字叫D");
            treeMap.put(student5, "我是学生5，我的名字叫E");
            for (Student s : treeMap.keySet()) {
                System.out.println(s.name + "," + s.id + "," + s.age);
            }
        }
    
    }

输出如下：

8 1 4 1 6 8 4 1 5 8 2 3 0 
    0 1 1 1 2 3 4 4 5 6 8 8 8 
    张三, 5, 27
    李四, 1, 17
    王五, 4, 29
    赵六, 3, 9
    左七, 2, 34
    =======
    张三, 5, 27
    王五, 4, 29
    赵六, 3, 9
    左七, 2, 34
    李四, 1, 17
    =======
    张三, 5, 27
    李四, 1, 17
    王五, 4, 29
    赵六, 3, 9
    左七, 2, 34
    =======
    左七, 2, 34
    王五, 4, 29
    张三, 5, 27
    李四, 1, 17
    赵六, 3, 9
    =======
    A,4,40
    C,5,12
    Process finished with exit code 0

### 三、总结核心点 ###

1.  对象的比较，一般就取属性来做比较，如代码示例按类的id属性和age属性，两个比较器做一个降序排序，当然也可以复合多个属性或者更复杂的逻辑进行返回排序

1.  核心就是返回值，compare()方法这里有个简洁写法，不用做if判断

如果要得到升序，直接：return o1.id - o2.id

如果要得到降序，直接：return o2.id - o1.id

> 注意这里有用TreeMap有序表保存对象做排序，键用的是自定义类对象类型，而且用了该类的id属性做比较器进行升序排序输出，如果不定义比较器会报错显示该类没有实现比较器类无法识别比较。而有序表默认是按key做排序，基础数据类型会自带排序，不需写比较器，且要求唯一不重复，同理用自定义类的id做比较器所以id不能重复添加，结果排序可以看到添加多个id=4的对象，只有第一个值为40的添加成功，其余都不能添加

> 这里简单解释下为什么？ 升序解释：compare()方法，如果返回负数，认为第一个参数应该排在前面；  
> 如果返回正数，认为第二个参数应该排在前面；如果返回0，认为谁放前面无所谓  
> 所以验证： o1-o2如果小于0，那么返回负数，表示o1<o2,且将第一个参数o1返回；如果大于0，那么返回正数，表示o1>o2,且将第二个参数o2返回，如果等于0，相等，返回任意一个，这里可以发现这三种情况返回的都是此时比较的较小值，所以较小的先输出，排在前面。 即为升序，降序同理。

### 四、扩展系统的优先队列类PriorityQueue、String类的compareTo()方法 ###

#### PriorityQueue ####

这个数据结构其实是最小堆，虽然起名时queue队列。

> 基础数据类型存放入堆，会直接按默认的最小堆性质，升序排序入堆，依次poll出的元素得到的是一个升序排序。而同时当数据是自定义类对象时，同样如上写一个比较器，将其放到创建PriorityQueue的构造器参数里面即可实现

#### String类的compareTo()方法 ####

> 底层是按字典序来排序，即按字符串的每个字符依次对比，如果个数相当，则依次从左到右对比，如果左侧有出现第一组不等的字符，则看对应的ASCII码谁大，则那个字符串就大于另外一个字符串；  
> 如"abc".compareTo("b") 返回 负数 因为第一个字符 b>a，虽然"b"只有一个字符。  
> "abc".compareTo("a") 返回 正数，第一位a=a，而第二位b , "a"没有第二位 所以大于"a"

代码如下：

package class06;
    
    import javax.sound.midi.Soundbank;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class ShowComparator2 {
    
        public static class MyComparator implements Comparator<Integer> {
    
            // 负，第一个参数在前
            // 正，第二个参数在前
            // 0, 谁放前都行
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 < o2) {
                    return 1;
                } else if (o1 > o2) {
                    return -1;
                } else {
                    return 0;
                }
            }
    
        }
    
        public static class Student {
            public String name;
            public int id;
            public int age;
    
            public Student(String name, int id, int age) {
                this.name = name;
                this.id = id;
                this.age = age;
            }
        }
    
        // 谁id大，谁放前！
        public static class IdComparator implements Comparator<Student> {
    
            // 如果返回负数，认为第一个参数应该排在前面
            // 如果返回正数，认为第二个参数应该排在前面
            // 如果返回0，认为谁放前面无所谓
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.id < o2.id) {
                    return 1;
                } else if (o2.id < o1.id) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
    
        public static void main(String[] args) {
            String str1 = "abc";
            String str2 = "a";
            System.out.println("abc".compareTo("b"));
            System.out.println(str1.compareTo(str2));
            PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
            Student s1 = new Student("张三", 5, 27);
            Student s2 = new Student("李四", 1, 17);
            Student s3 = new Student("王五", 4, 29);
            Student s4 = new Student("赵六", 3, 9);
            Student s5 = new Student("左七", 2, 34);
            heap.add(s1);
            heap.add(s2);
            heap.add(s3);
            heap.add(s4);
            heap.add(s5);
            System.out.println("=========");
            while (!heap.isEmpty()) {
                Student s = heap.poll();
                System.out.println(s.name + ", " + s.id + ", " + s.age);
            }
            System.out.println("=========");
            PriorityQueue<Integer> heap2 = new PriorityQueue<>();
            heap2.add(3);
            heap2.add(9);
            heap2.add(7);
            heap2.add(1);
            heap2.add(6);
            System.out.println(heap2);
            System.out.println(heap2.peek());
        }
    
    }

输出如下：

-1
    2
    =========
    张三, 5, 27
    王五, 4, 29
    赵六, 3, 9
    左七, 2, 34
    李四, 1, 17
    =========
    [1, 3, 7, 9, 6]
    1
    
    Process finished with exit code 0