Java-比较与排序

每日一言

Pirates are evil? The Marines are righteous?… Justice will prevail, you say? But of course, it will! Whoever wins this war becomes justice! – Donquixote Doflamingo
from One Piece

Comparable接口

在java.lang中定义了Comparable接口，其定义如下：

package java.lang;

public interface Comparable<T> {
    public int compareTo(T o);
}

该接口只有一个方法就是comparaTo方法。继承了该接口的类可以通过实现comparable方法来定义该类的比较方法。从而可以使用排序库来方便的实现自定义类的排序问题。

public class Student implements Comparable<Student> {
    private String name;
    private int score;
  
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
  
    @Override
    public int compareTo(Student other) {
        // 按分数降序排列
        return other.score - this.score;
  
        // 如果要按分数升序排列
        // return this.score - other.score;
  
        // 如果要先按分数再按姓名
        // if (this.score != other.score) {
        //     return this.score - other.score;
        // }
        // return this.name.compareTo(other.name);
    }
  
    // getter, setter, toString等方法...
}

compareTo方法

compareTo方法的定义如下：

public int compareTo(T o);

T o 代表传入进来与之比较的参数

返回值的含义：

• 返回负数：表示当前对象小于参数对象
• 返回0：表示当前对象等于参数对象
• 返回正数：表示当前对象大于参数对象

注意：在实现compareTo方法时，应该注意与 equals方法的一致性，即 x.equals(y)为 true时，x.compareTo(y)应返回0。

自然排序

在Comparable中实现的比较方法在java中被称为自然排序，这是一个类自身所固有的、默认的比较方式。

实现compareTo方法后，就有许多排序和排序和查找库可以供我们使用：

Arrays类中的排序方法

import java.util.Arrays;

// 对数组进行排序
Arrays.sort(array);  // 数组元素必须实现Comparable接口

// 对数组部分排序
Arrays.sort(array, fromIndex, toIndex);  // 排序指定范围内的元素

Collections类中的排序方法

import java.util.Collections;
import java.util.List;

// 对List集合进行排序
Collections.sort(list);  // 集合元素必须实现Comparable接口

// 使用二分查找（需要先排序）
int index = Collections.binarySearch(list, key);

TreeSet和TreeMap

import java.util.TreeSet;
import java.util.TreeMap;

// TreeSet自动排序
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("banana");
treeSet.add("apple");
treeSet.add("orange");
// 自动按字母顺序排列: [apple, banana, orange]

// TreeMap键自动排序
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");
// 键自动按数字顺序排列

PriorityQueue优先队列

import java.util.PriorityQueue;

// 优先队列根据compareTo方法确定优先级
PriorityQueue<String> queue = new PriorityQueue<>();
queue.add("banana");
queue.add("apple");
queue.add("orange");

// poll()方法每次取出最小元素
String first = queue.poll();  // "apple"

自定义排序

与Comparable 不同，Comparator 是用于自定义排序规则的接口，但是不需要修改被比较的类，而是作为一个独立的比较器。

Comparator 定义

在 java.util 包中，定义如下：

public interface Comparator<T> {
    int compare(T o1, T o2);
}

Comparator的静态方法

Java 8开始，Comparator接口提供了多种静态方法来创建和组合比较器：

方法	描述	示例
comparing(Function<T,U>)	根据指定函数提取的键创建比较器	Comparator.comparing(Student::getName)
comparingInt/Long/Double(ToIntFunction)	根据提取的基本类型值创建比较器	Comparator.comparingInt(Student::getScore)
naturalOrder()	返回自然顺序比较器	Comparator.naturalOrder()
reverseOrder()	返回自然顺序的逆序比较器	Comparator.reverseOrder()
nullsFirst(Comparator)	修改比较器使null值排在前面	Comparator.nullsFirst(comparingInt(Student::getScore))
nullsLast(Comparator)	修改比较器使null值排在后面	Comparator.nullsLast(comparing(Student::getName))
reversed()	返回当前比较器的逆序版本	comparing(Student::getScore).reversed()
thenComparing(Comparator)	组合两个比较器，当第一个返回0时使用第二个	comparing(Student::getScore).thenComparing(Student::getName)
thenComparingInt/Long/Double(ToIntFunction)	组合比较器，第二个使用基本类型	comparing(Student::getGrade).thenComparingInt(Student::getScore)

创建Comparator

创建Comparator比较器的方法有很多种，我们从最简单学起：

首先假设我们有一个Person类：

class Person {
    private String name;
    private int age;
    private double height;

    public Person(String name, int age, double height) {
        this.name = name;
        this.age = age;
        this.height = height;
    }

    public String getName() { return name; }
    public int getAge() { return age; }
    public double getHeight() { return height; }

    @Override
    public String toString() {
        return "Person{" + "name='" + name + '\'' + ", age=" + age + ", height=" + height + '}';
    }
}

创建类方式(传统方式)

import java.util.Comparator;

// 按姓名升序排序的比较器
class PersonNameComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // String 类本身实现了 Comparable，可以直接用 compareTo
        return p1.getName().compareTo(p2.getName());
    }
}

// 按年龄降序排序的比较器
class PersonAgeDescendingComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // p2 在前，p1 在后，实现降序
        return p2.getAge() - p1.getAge(); //(注意潜在溢出)
  
    }
}

使用匿名内部类

import java.util.Comparator;

// ... 在需要使用 Comparator 的地方 ...
Comparator<Person> ageComparator = new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getAge(), p2.getAge()); // 按年龄升序
    }
};

使用Lambda表达式

import java.util.Comparator;

// 按年龄升序
Comparator<Person> ageComparatorLambda = (p1, p2) -> Integer.compare(p1.getAge(), p2.getAge());
// 或者更简洁，如果 Person::getAge 返回的是 Comparable 类型 (Integer 是)
// Comparator<Person> ageComparatorLambda = Comparator.comparingInt(Person::getAge); // 见下文

// 按姓名升序
Comparator<Person> nameComparatorLambda = (p1, p2) -> p1.getName().compareTo(p2.getName());
// Comparator<Person> nameComparatorLambda = Comparator.comparing(Person::getName); // 见下文

使用 Comparator 的静态工厂方法 (Java 8+, 非常推荐，功能强大且易读)

import java.util.Comparator;

// 按年龄升序 (使用 comparingInt 优化基本类型)
Comparator<Person> compareByAge = Comparator.comparingInt(Person::getAge);

// 按姓名升序 (使用 comparing)
Comparator<Person> compareByName = Comparator.comparing(Person::getName);

// 按身高降序 (使用 comparingDouble + reversed)
Comparator<Person> compareByHeightDesc = Comparator.comparingDouble(Person::getHeight).reversed();

// 组合比较：先按年龄升序，如果年龄相同，再按姓名升序
Comparator<Person> compareByAgeThenName = Comparator.comparingInt(Person::getAge)
                                                   .thenComparing(Person::getName);

// 组合比较：先按年龄降序，如果年龄相同，再按姓名升序
Comparator<Person> compareByAgeDescThenName = Comparator.comparingInt(Person::getAge).reversed()
                                                        .thenComparing(Person::getName);

// 处理 null 值：将 null 排在最前面，然后按年龄升序
Comparator<Person> compareByAgeNullsFirst = Comparator.nullsFirst(Comparator.comparingInt(Person::getAge));

// 处理 null 值：将 null 排在最后面，然后按姓名升序
Comparator<Person> compareByNameNullsLast = Comparator.nullsLast(Comparator.comparing(Person::getName));

使用Comparator

1. Collections.sort(List <T> list, Comparator)

2. Arrays.sort(T[] a, Comparator)

3. 创建有序集合 (TreeSet,TreeMap) 时指定排序规则

   Comparator<Person> byAge = Comparator.comparingInt(Person::getAge);
   Set<Person> sortedPeople = new TreeSet<>(byAge);