[数据结构与算法]高薪程序员&面试题精讲系列15之Java中的对象如何实现排序？

一. 面试题及剖析

1. 今日面试题

我们在项目开发时，有时候会遇到列表搜索查询等效果，其中大部分都可以利用SQL语句来实现，但也有些特殊的搜索排序利用SQL是很难实现的，比如对中文进行排序。说到排序，你可能会想到很多排序算法，比如常见的冒泡排序、堆排序、插入排序等，但Java本身其实也提供了排序API，所以有时候面试官会提问这样的面试题：

说一下Java中的对象如何实现排序？

Java如何操作对象(bean)进行动态排序？

Java对实体类(bean)如何进行动态排序？

......

2. 题目剖析

今日这道面试题，其实考察的还是我们对Java中常用API的掌握情况，尤其是对Java对象的排序实现，比如按照类中的某一个属性(或多个属性)来对类的对象进行排序。

二. 参考答案

1. Java排序实现方式

要想实现对某个对象的排序，排序方式整体可以分为 自定义排序和实现Java中的比较器接口排序 这2种方式。

自定义对象排序：我们可以根据自定义对象的数据结构，自定义排序规则来实现。

实现Java中的比较器接口排序：可以实现Java中的两个常用接口，Comparable和Comparator。

在本文中，壹哥 主要带各位复习 Comparable 和 Comparator两个接口，并比较两者的差异，再利用这两个接口来实现排序案例。

2. Comparable接口

Comparable 是Java提供的进行自然排序的接口。Comparable接口会对实现该接口的每个类对象都强加一个整体排序，这个排序称为类的自然排序(默认为升序)，所以一个类实现了Comparable接口，就意味着该类支持排序。一旦该类支持排序，那么存储了该类的List列表或Array数组就可以通过Collections.sort() 或 Arrays.sort() 方法进行自然排序。

Comparable 接口中只包括一个自然比较方法，源码如下：

public interface Comparable<T> {
    /**
     * Compares this object with the specified object for order.  Returns a
     * negative integer, zero, or a positive integer as this object is less
     * than, equal to, or greater than the specified object.
     *
     * <p>The implementor must ensure <tt>sgn(x.compareTo(y)) ==
     * -sgn(y.compareTo(x))</tt> for all <tt>x</tt> and <tt>y</tt>.  (This
     * implies that <tt>x.compareTo(y)</tt> must throw an exception iff
     * <tt>y.compareTo(x)</tt> throws an exception.)
     *
     * <p>The implementor must also ensure that the relation is transitive:
     * <tt>(x.compareTo(y)&gt;0 &amp;&amp; y.compareTo(z)&gt;0)</tt> implies
     * <tt>x.compareTo(z)&gt;0</tt>.
     *
     * <p>Finally, the implementor must ensure that <tt>x.compareTo(y)==0</tt>
     * implies that <tt>sgn(x.compareTo(z)) == sgn(y.compareTo(z))</tt>, for
     * all <tt>z</tt>.
     *
     * <p>It is strongly recommended, but <i>not</i> strictly required that
     * <tt>(x.compareTo(y)==0) == (x.equals(y))</tt>.  Generally speaking, any
     * class that implements the <tt>Comparable</tt> interface and violates
     * this condition should clearly indicate this fact.  The recommended
     * language is "Note: this class has a natural ordering that is
     * inconsistent with equals."
     *
     * <p>In the foregoing description, the notation
     * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical
     * <i>signum</i> function, which is defined to return one of <tt>-1</tt>,
     * <tt>0</tt>, or <tt>1</tt> according to whether the value of
     * <i>expression</i> is negative, zero or positive.
     *
     * @param   o the object to be compared.
     * @return  a negative integer, zero, or a positive integer as this object
     *          is less than, equal to, or greater than the specified object.
     *
     * @throws NullPointerException if the specified object is null
     * @throws ClassCastException if the specified object's type prevents it
     *         from being compared to this object.
     */
    public int compareTo(T o);
}

从上面的源码注释上可以看出，Comparable类中的compareTo()方法用于将当前对于与指定的对象进行对比排序，compareTo()方法可以返回3种数值，比较规则如下：

假设我们通过 x.compareTo(y) 来“比较x和y的大小”，若返回“负数”，则意味着“x比y小”；

若返回 “零”，则意味着 “x等于y”；

若返回 “正数”，则意味着 “x大于y”。

3. Comparator接口

Comparator 也是一个比较器接口，如果我们需要控制某个类的次序，而该类本身并不支持排序，也就是没有实现Comparable接口，那么我们可以使用该接口来进行排序。我们可以将Comparator比较器传递给排序方法(Collections.sort或Arrays.sort)，就可以实现对不具有排序功能的对象列表提供排序功能，并且可以对排序的顺序进行升序或降序的控制。

Comparator源码核心方法如下：

@FunctionalInterface
public interface Comparator<T> {
    /**
     * Compares its two arguments for order.  Returns a negative integer,
     * zero, or a positive integer as the first argument is less than, equal
     * to, or greater than the second.<p>
     *
     * In the foregoing description, the notation
     * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical
     * <i>signum</i> function, which is defined to return one of <tt>-1</tt>,
     * <tt>0</tt>, or <tt>1</tt> according to whether the value of
     * <i>expression</i> is negative, zero or positive.<p>
     *
     * The implementor must ensure that <tt>sgn(compare(x, y)) ==
     * -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>.  (This
     * implies that <tt>compare(x, y)</tt> must throw an exception if and only
     * if <tt>compare(y, x)</tt> throws an exception.)<p>
     *
     * The implementor must also ensure that the relation is transitive:
     * <tt>((compare(x, y)&gt;0) &amp;&amp; (compare(y, z)&gt;0))</tt> implies
     * <tt>compare(x, z)&gt;0</tt>.<p>
     *
     * Finally, the implementor must ensure that <tt>compare(x, y)==0</tt>
     * implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all
     * <tt>z</tt>.<p>
     *
     * It is generally the case, but <i>not</i> strictly required that
     * <tt>(compare(x, y)==0) == (x.equals(y))</tt>.  Generally speaking,
     * any comparator that violates this condition should clearly indicate
     * this fact.  The recommended language is "Note: this comparator
     * imposes orderings that are inconsistent with equals."
     *
     * @param o1 the first object to be compared.
     * @param o2 the second object to be compared.
     * @return a negative integer, zero, or a positive integer as the
     *         first argument is less than, equal to, or greater than the
     *         second.
     * @throws NullPointerException if an argument is null and this
     *         comparator does not permit null arguments
     * @throws ClassCastException if the arguments' types prevent them from
     *         being compared by this comparator.
     */
    int compare(T o1, T o2);

    boolean equals(Object obj);
    
    ......
        
 }    

Comparator接口一般不单独使用，而是传递给Collections或Arrays的sort方法。Collections.sort(List list, Comparator<? super T> c)，Arrays.sort(T[] a, Comparator<? super T> c)两个方法会根据指定的比较器对指定的列表进行排序，我们只需要在Comparator比较器中重写int compara(T o1,To2)方法即可实现排序。该方法用于“比较o1和o2的大小”，若返回“负数”，则意味着“o1比o2小”；若返回“零”，则意味着“o1等于o2”；若返回“正数”，则意味着“o1大于o2”。

所以compara(T o1，To2)方法的排序规则如下：

如果遇到数值比较，直接在方法内返回两个对象属性的差值，例如o1.getValue()-o2.getValue()>0是升序，o2.getValue()-o1.getValue()>0则是降序；

如果遇到字符串形式的比较，可以利用compareTo(T o)方法进行比较，该方法会从头开始比较每一个字符，当前者大于后者返回1，当前者小于后者返回-1。

三. 实现代码

接下来我们编写两个案例，分别讲解对比 Comparable接口 与Comparator接口 的使用。

1. Comparable接口使用案例

1.1 Student类

首先我们编写一个Student类，实现Comparable接口，复写内部的compareTo()方法。

//实现Comparable<Student>接口并带入Student类作为泛型
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Student implements Comparable<Student> {

    private Integer id;

    private String name;

    private Integer age;

    private Float score;

    //复写compareTo()方法，以score字段作为排序属性
    @Override
    public int compareTo(Student o) {
        if (score > o.getScore()) {
            return 1;
        } else if (score < o.getScore()) {
            return -1;
        } else {
            return 0;
        }
    }

}

注意在该类中，我使用了lombok插件来减少构造方法与getter、setter等方法的编写。

1.2 ComparableTest11测试类

然后我们再编写另一个ComparableTest11测试类，测试排序效果。

public class ComparableTest11 {

    public static void main(String[] args) {
        Student s1 = new Student(1, "syc", 20, 98.9f);
        Student s2 = new Student(2, "yyg", 25, 66.5f);
        Student s3 = new Student(3, "一一哥", 30, 50.1f);
        Student s4 = new Student(4, "孙一一", 18, 88.9f);
        List<Student> students = new ArrayList<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);
        for (Student stu : students) {
            System.out.println("排序前--->id=" + stu.getId() + ", name=" + stu.getName() + ", score=" + stu.getScore());
        }

        System.out.println("=========================华丽分割线===========================");

        //对集合进行排序
        Collections.sort(students);
        for (Student stu : students) {
            System.out.println("排序后--->id=" + stu.getId() + ", name=" + stu.getName() + ", score=" + stu.getScore());
        }
    }

}

1.3 执行结果

从代码的执行结果上可以看出，排序前List列表中的元素是按照添加到集合的顺序输出的，但排序后就是按照score的值升序排列的，由此可见Comparable接口的排序效果。

2. Comparator接口使用案例

2.1 Teacher类

这里我们简单定义一个Teacher类，封装几个属性。

@Data
@NoArgsConstructor
@AllArgsConstructor
public class Teacher {

    private Integer id;

    private String name;

    private Integer age;

}

2.2 ComparatorTest12测试类

接着编写ComparatorTest12测试类，进行对象的排序比较。

public class ComparatorTest12 {

    public static void main(String[] args) {
        List<Teacher> list = new ArrayList<>();
        list.add(new Teacher(1, "yyg", 30));
        list.add(new Teacher(2, "syc", 18));
        list.add(new Teacher(3, "sun", 22));

        for (Teacher teacher : list) {
            System.out.println("排序前--->id=" + teacher.getId() + ", name=" + teacher.getName() + ", age=" + teacher.getAge());
        }

        Collections.sort(list, new Comparator<Teacher>() {
            @Override
            public int compare(Teacher o1, Teacher o2) {
                //数值型数据的比较
                if (o1.getId().equals(o2.getId())) {
                    return o1.getId() - o2.getId();
                }
                
                //字符串类型的比较
                return o1.getAge().compareTo(o2.getAge());
            }
        });

        System.out.println("=========================华丽分割线===========================");

        for (Teacher teacher : list) {
            System.out.println("排序后--->id=" + teacher.getId() + ", name=" + teacher.getName() + ", age=" + teacher.getAge());
        }
    }

}

2.3 执行结果

从代码的执行结果可以看出，排序前List列表中的元素也是按照添加到集合的顺序输出的，但排序后就是按照age的值升序排列的，由此可见Comparator接口的排序效果。

四. 结论

至此，壹哥 就带各位复习了一下Java中对象的排序功能，Java中对象的排序功能，有2种实现方式，即自定义排序和实现Java中的比较器接口排序，本文中主要是利用比较器接口来实现的。最后 壹哥 再给各位梳理一下本文重点。

1. 对象排序方式

如果我们需要对类对象按照类中的某一个属性(或者多个属性)来进行排序，有两种方式可以实现：

1. 自然排序方式：参与排序的对象需要实现comparable<T>接口，泛型T即为排序类对象，然后调用Collections.sort(List)方法进行排序；
2. 定制排序,或自定义排序方式：某个类不实现Comparable<T>接口，在排序时使用Collections.sort(List, Comparator<T>)方法，利用匿名内部类，new一个Comparator接口的比较器对象c，实现其中的Comparator<T>接口方法。

2. Comparable 与 Comparator 区别

1. Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。
2. Comparator是比较器，如果我们需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
3. Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
4. Comparable实现排序不够灵活，实体类实现了Comparable接口后，会提高耦合性，如果在项目中可能要会在不同的位置，根据不同的属性进行排序，就需要反复修改比较规则(比如到底是按name还是按age排序？)。
5. Comparator排序就比较灵活，我们只需在需要的地方，创建内部类的实例，重写其比较方法即可。

如果你对Java对象排序还有什么疑问，请在评论区留言讨论哦！