Comparator 如何稳定排序

在 Java 中，Comparator 本身不保证稳定排序，是否稳定取决于使用的排序算法。
如果你希望排序是稳定的，需要同时满足两个条件：

一、什么是“稳定排序（Stable Sort）”

稳定排序是指：

相等元素的相对顺序在排序后保持不变

例如：

原顺序：
(1, "A")
(2, "B")
(1, "C")

按第一个字段排序后（稳定）：
(1, "A")
(1, "C")
(2, "B")

如果 "A" 和 "C" 的顺序被交换，就不是稳定排序。

二、Java 中哪些排序是稳定的？

✅ 稳定的排序方式

1️⃣ Collections.sort(List)

Collections.sort(list, comparator);

• 稳定
• 底层使用 TimSort
• 时间复杂度：O(n log n)

✅ 推荐用于稳定排序

2️⃣ List.sort(Comparator)（Java 8+）

list.sort(comparator);

• 稳定
• 与 Collections.sort 底层一致

❌ 不稳定的排序方式

3️⃣ Arrays.sort(T[])（对象数组）

Arrays.sort(array, comparator);

• 不稳定
• 使用的是 归并排序的变体，但不保证稳定

⚠️ 官方文档未承诺稳定

4️⃣ Stream.sorted(comparator)

list.stream()
    .sorted(comparator)
    .collect(Collectors.toList());

• 不保证稳定
• 可能是稳定，也可能不是（实现相关）

❌ 不建议用于依赖稳定性的场景

三、Comparator 本身如何写才“配合稳定排序”

✅ 正确示例（推荐）

Comparator<Person> comparator = Comparator
        .comparing(Person::getAge)
        .thenComparing(Person::getName);  // 次级排序

• 稳定排序算法 + 多级比较
• 相等元素（age 相同）保持原顺序

⚠️ 错误示例（破坏稳定性）

Comparator<Person> comparator = (a, b) -> {
    if (a.getAge() != b.getAge()) {
        return a.getAge() - b.getAge();
    }
    return Math.random() > 0.5 ? 1 : -1; // ❌ 随机顺序
};

即使排序算法稳定，比较器本身不稳定，最终结果也不稳定。

四、如何“强制”稳定排序（通用做法）

✅ 方法 1：使用 Collections.sort

Collections.sort(list, comparator);

✅ 最简单、最安全

✅ 方法 2：加入“原始索引”作为兜底

class Indexed<T> {
    T value;
    int index;
}

listWithIndex.sort(Comparator
        .comparing((Indexed<T> i) -> i.value, comparator)
        .thenComparingInt(i -> i.index));

✅ 适用于任何排序算法
✅ 稳定排序的“终极方案”

五、总结速查表

如果你愿意，可以告诉我：

• 用的是 List / 数组 / Stream
• Java 版本
• 实际业务场景（如分页、分组、数据库排序）

我可以给你一个最合适的稳定排序方案。