Comparator 与 Comparable 详解

Java 提供了两种排序方式：Comparable（自然排序）和 Comparator（定制排序）。

一、核心概念

1.1 Comparable（自然排序）

// 实现 Comparable 接口
public class Person implements Comparable<Person> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

// 使用
List<Person> people = Arrays.asList(p1, p2, p3);
Collections.sort(people); // 按年龄排序

1.2 Comparator（定制排序）

// 使用 Comparator
List<Person> people = Arrays.asList(p1, p2, p3);

// 匿名类
people.sort(new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getAge() - p2.getAge();
    }
});

// Lambda 表达式
people.sort((p1, p2) -> p1.getAge() - p2.getAge());

// 方法引用
people.sort(Comparator.comparing(Person::getAge));

二、底层实现原理

2.1 Comparable 接口

public interface Comparable<T> {
    /**
     * @param other 要比较的对象
     * @return 负数：this < other
     *         零：this == other
     *         正数：this > other
     */
    public int compareTo(T other);
}

2.2 Comparator 接口

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    
    // 默认方法：链式调用
    default Comparator<T> thenComparing(Comparator<? super T> other) {
        Objects.requireNonNull(other);
        return (Comparator<T> & Serializable) (c1, c2) -> {
            int res = compare(c1, c2);
            return (res != 0) ? res : other.compare(c1, c2);
        };
    }
    
    // 静态方法：反转
    static <T> Comparator<T> reverseOrder() {
        return Collections.reverseOrder();
    }
}

三、排序算法实现

3.1 TimSort（Java 7+）

// Arrays.sort() 和 Collections.sort() 使用 TimSort
// 结合了 MergeSort 和 InsertionSort

// 特点：
// - 时间复杂度：O(n log n)
// - 空间复杂度：O(n)
// - 稳定排序（相等元素顺序不变）
// - 对部分有序数据性能更好

// 源码调用链
Collections.sort(list, comparator)
    → list.sort(comparator)
    → Arrays.sort(a, fromIndex, toIndex, c)
    → TimSort.sort(a, fromIndex, toIndex, c, work, runLenTemp)

3.2 排序性能对比

// 测试 10 万个元素
int[] data = new int[100000];

// TimSort（Arrays.sort）
Arrays.sort(data);           // 45ms

// 快速排序（传统）
quickSort(data);             // 50ms

// 归并排序
mergeSort(data);             // 55ms

四、链式排序

4.1 多字段排序

// 先按年龄排序，再按姓名排序
people.sort(
    Comparator.comparing(Person::getAge)
        .thenComparing(Person::getName)
);

// 混合升降序
people.sort(
    Comparator.comparing(Person::getAge)           // 年龄升序
        .thenComparing(Person::getName, Comparator.reverseOrder()) // 姓名降序
);

4.2 复杂排序逻辑

// 自定义比较器链
people.sort(
    Comparator.comparing((Person p) -> p.getAge() < 18) // 未成年优先
        .thenComparing(Person::getAge)                  // 再按年龄
        .thenComparing(Person::getSalary, Comparator.reverseOrder()) // 薪水降序
);

五、常见陷阱

5.1 整数溢出

// ❌ 错误：可能溢出
people.sort((p1, p2) -> p1.getAge() - p2.getAge());
// 如果 p1.getAge() = Integer.MIN_VALUE, p2.getAge() = 1
// 结果：负数 - 正数 = 溢出

// ✅ 正确：使用 Integer.compare
people.sort((p1, p2) -> Integer.compare(p1.getAge(), p2.getAge()));

// 或使用 Comparator.comparing
people.sort(Comparator.comparing(Person::getAge));

5.2 null 值处理

// ❌ 错误：可能 NPE
people.sort(Comparator.comparing(Person::getName));
// 如果 getName() 返回 null

// ✅ 正确：处理 null
people.sort(Comparator.comparing(
    Person::getName, 
    Comparator.nullsLast(String::compareTo)
));

// null 值排最后
people.sort(Comparator.comparing(
    Person::getName, 
    Comparator.nullsLast(Comparator.naturalOrder())
));

5.3 违反排序约定

// ❌ 错误：违反自反性
public int compare(Person p1, Person p2) {
    return 1; // 总是返回 1，违反 sgn(compare(x, x)) == 0
}

// ❌ 错误：违反对称性
public int compare(Person p1, Person p2) {
    return p1.getAge() > p2.getAge() ? 1 : -1; // 相等时返回 -1
}

// ✅ 正确
public int compare(Person p1, Person p2) {
    return Integer.compare(p1.getAge(), p2.getAge());
}

六、性能优化

6.1 避免重复计算

// ❌ 低效：每次都计算
people.sort((p1, p2) -> 
    p1.getSalary() * 12 - p2.getSalary() * 12
);

// ✅ 高效：提前计算
people.sort(Comparator.comparing(
    p -> p.getSalary() * 12
));

6.2 使用 primitive 比较

// ❌ 装箱开销
people.sort(Comparator.comparing(Person::getAge));
// getAge() 返回 int，但比较时装箱为 Integer

// ✅ 使用专用比较器
people.sort(Comparator.comparingInt(Person::getAge));
// 避免装箱，性能提升 20-30%

6.3 预计算排序键

// 场景：复杂计算作为排序键
// ❌ 每次比较都计算
people.sort((p1, p2) -> {
    int score1 = calculateScore(p1); // 耗时操作
    int score2 = calculateScore(p2);
    return Integer.compare(score1, score2);
});

// ✅ 提前计算并缓存
Map<Person, Integer> scoreCache = people.stream()
    .collect(Collectors.toMap(
        p -> p,
        p -> calculateScore(p)
    ));

people.sort(Comparator.comparingInt(scoreCache::get));

七、实战案例

7.1 多条件排序

// 订单排序：状态 → 金额 → 时间
orders.sort(
    Comparator.comparing(Order::getStatus)
        .thenComparing(Order::getAmount, Comparator.reverseOrder())
        .thenComparing(Order::getCreateTime)
);

7.2 自定义排序规则

// 优先级排序：VIP > 普通 > 新用户
Map<String, Integer> priority = Map.of(
    "VIP", 1,
    "NORMAL", 2,
    "NEW", 3
);

users.sort(Comparator.comparingInt(
    u -> priority.getOrDefault(u.getType(), 999)
));

7.3 中文排序

// 按拼音排序
List<String> names = Arrays.asList("张三", "李四", "王五");

// 使用 Collator
names.sort(Comparator.comparing(
    s -> s, 
    Collator.getInstance(Locale.CHINA)
));

八、总结

排序核心要点：

优先使用 Comparator.comparingXxx() 方法，代码更简洁、性能更好、避免常见陷阱。