java Comparator 如何稳定

在 Java 里，Comparator 本身并不能“让排序稳定”，排序是否稳定取决于你使用的排序算法 / API，而不是 Comparator。

下面把关键点讲清楚：

1️⃣ 什么是“稳定排序”

稳定排序：
如果两个元素 a 和 b 在排序前顺序为 a 在前、b 在后，并且它们“相等”（compare(a,b) == 0），排序后仍然保持 a 在前、b 在后。

2️⃣ Java 中哪些排序是稳定的？

✅ 稳定的

• List.sort(Comparator)（Java 8+）
• Collections.sort(List, Comparator)
• Arrays.sort(Object[])（对象数组）

底层使用的是 TimSort（稳定）

list.sort(Comparator.comparing(User::getAge));

✅ 相等元素保持原顺序

❌ 不稳定的

• Arrays.sort(int[])、Arrays.sort(long[]) 等基本类型数组
• 自己写的快排 / 选择排序等

int[] arr = {3, 1, 2};
Arrays.sort(arr); // 不稳定（但基本类型无所谓）

⚠️ 基本类型没有“原顺序”概念，所以无所谓稳定不稳定

3️⃣ Comparator 如何“配合”稳定排序

✅ 正确做法：用“次要字段”保证顺序可控

如果你想在稳定排序中进一步控制顺序：

list.sort(
    Comparator
        .comparing(User::getAge)
        .thenComparing(User::getId) // 稳定的次要排序
);

如果 age 相同，按 id 排
如果 id 也相同，原顺序保留（稳定）

4️⃣ 如果必须“手动稳定排序”

方法：加“原始索引”

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

list.stream()
    .map((v, i) -> new Indexed<>(v, i))
    .sorted(Comparator
        .comparing((Indexed<User> x) -> x.value.getAge())
        .thenComparingInt(x -> x.index))

✅ 即使底层排序不稳定，也能保证原顺序

5️⃣ 常见误区 ❌

• ❌ “我写个 Comparator 就能稳定”
• ❌ “compare 返回 0 就稳定”
• ✅ 稳定 ≠ Comparator，而是排序算法

✅ 总结一句话

Java 中只要用 List.sort / Collections.sort，并且比较结果为 0 的元素你不在乎顺序，就已经是稳定的。

如果你有具体场景（比如并发、TreeMap、自定义排序），可以继续问。