Java 通用排序接口及其原理

Comparable 接口

如果一个类实现了 Comparable 接口，就说明这个类支持直接用 Java 提供的 Arrays.sort() 方法和 Collections.sort() 方法来排序。

Comparator 接口

如果一个类没有实现 Comparable 接口，能不能不修改这个类的源码就能用 Java 自身提供的方法进行排序？

解决方案就是写一个实现 Comparator 接口的类，这个类只提供自定义的比较规则，排序过程依然交给 Java 自带的 sort() 方法。

通用排序方法原理

实现 Comparable 接口必须覆盖 int compareTo() 方法，实现 Comparator 接口必须覆盖 int compare() 方法，两个方法的返回值都是 int 类型，并且返回值只能是以下三种：

• 1：表示大于
• -1：表示小于
• 0：表示相等

Java 的 sort() 方法在排序过程中根据这个 int 类型的返回值来确定数据要挪动到哪个位置， sort() 方法是结合使用了归并排序、快速排序等类似于二叉搜索树的算法，本质上这些算法跟二叉搜索树一样都运用了分治法的思想。

分治法就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

例如二叉搜索树的构造过程是：使用第一个元素作为根节点，后续的元素如果比根节点小就放在左子树，如果比根节点大，就放在右子树，最后使用中序遍历（左子树—> 根结点 —> 右子树）方法读取。

sort() 方法通用性很高，这实际上是运用了分治排序法以及面向对象的运行时多态，并不是网上很多人说的用了设计模式中的策略模式。

示例代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class User implements Comparable {

    Integer age;

    public User(Integer age) {
        this.age = age;
    }

    @Override
    public int compareTo(Object o) {
        User a = this;
        User b = (User) o;

        if (a.age > b.age) {
            return 1;
        } else if (a.age < b.age) {
            return -1;
        }
        return 0;
    }

    @Override
    public String toString() {
        return "User{" +
                "age=" + age +
                '}';
    }

    public static void main(String[] args) {
        User user1 = new User(23);
        User user2 = new User(30);
        User user3 = new User(18);

        List list = new ArrayList<>();
        list.add(user1);
        list.add(user2);
        list.add(user3);

        System.out.println("排序前：" + Arrays.toString(list.toArray()));

        Collections.sort(list);

        System.out.println("排序后：" + Arrays.toString(list.toArray()));
    }


}

import java.util.*;

class StudentComparator implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        Student a = (Student) o1;
        Student b = (Student) o2;

        if (a.age > b.age) {
            return 1;
        } else if (a.age < b.age) {
            return -1;
        }
        return 0;
    }

}


public class Student {

    Integer age;

    public Student(Integer age) {
        this.age = age;
    }


    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                '}';
    }

    public static void main(String[] args) {
        Student student1 = new Student(23);
        Student student2 = new Student(30);
        Student student3 = new Student(18);

        List list = new ArrayList<>();
        list.add(student1);
        list.add(student2);
        list.add(student3);

        System.out.println("排序前：" + Arrays.toString(list.toArray()));

        Collections.sort(list, new StudentComparator());

        System.out.println("排序后：" + Arrays.toString(list.toArray()));
    }


}