自定义排序比较器必须满足哪些契约？写错会有什么后果？

简化版

自定义比较器必须定义出一致、可传递、反对称的顺序关系。

如果比较器写错，比如用减法导致溢出、比较结果不传递、依赖随机数或可变外部状态，排序算法可能得到错误结果，甚至在某些语言里抛出异常。

比较器不是随便返回正负数，它是排序正确性的基础。

详细版

比较器常见契约包括：

契约	含义
反对称	`compare(a,b)` 和 `compare(b,a)` 符号相反
传递性	`a < b` 且 `b < c`，则 `a < c`
一致性	同一组输入多次比较结果一致
相等处理	compare 返回 `0` 时语义清楚

错误示例：

(a, b) -> a.score - b.score

如果分数很大，减法可能溢出。更稳写法是 Integer.compare(a.score, b.score)。

完整版教学

1. 比较器决定了排序的顺序定义

排序算法并不知道业务上谁应该排前面。

它只会不断调用比较器：

compare(a, b)

然后根据返回结果调整位置。

所以比较器如果定义不出可靠顺序，排序算法就像拿着一把会变形的尺子量东西。

2. 反对称是什么意思

如果 a < b，那么反过来必须是 b > a。

也就是说：

sign(compare(a, b)) == -sign(compare(b, a))

如果比较器对 a,b 和 b,a 都说前者更小，排序就无法建立一致顺序。

3. 传递性为什么重要

传递性要求：

如果 a < b 且 b < c，那么 a < c

如果比较器违反传递性，可能出现循环：

a < b
b < c
c < a

这会让排序算法无法收敛到一个合理有序结果。

比较器的传递性，是排序结果能被称为“有序”的基本前提。

4. 一致性为什么重要

比较器不应该依赖随机数、当前时间或会变化的外部状态。

错误思路：

compare(a, b) 每次随机返回正负

或者排序过程中修改参与比较的字段。

同一对元素前后比较结果不同，排序算法会得到不可预测结果。

5. 为什么不要用减法比较

很多人写：

(a, b) -> a - b

如果 a 很大、b 是负数，减法可能整数溢出，导致符号错误。

更安全写法：

Integer.compare(a, b)
Long.compare(x, y)

这个坑在时间戳、距离、分数排序里非常常见。

6. 多关键字排序怎么写

多关键字排序要按优先级逐层比较。

例如：

分数降序；
时间升序；
id 升序。

可以表达成：

if score different: higher score first
else if time different: earlier time first
else smaller id first

不要把多个字段随便相加或相减，因为会改变业务含义。

7. compare 返回 0 的含义

返回 0 表示两个元素在排序 key 上等价。

如果使用的是稳定排序，返回 0 的元素会保留原相对顺序；如果排序不稳定，就不保证。

排序类型	compare 为 0 的相对顺序
稳定排序	保留
不稳定排序	不保证

如果业务要求结果完全确定，可以添加 tie-breaker，比如唯一 id。

8. 常见误区与追问

误区：比较器只要能返回正负数就行。 它必须满足反对称、传递和一致性等契约。
误区：减法比较简单安全。 整数溢出会让比较结果反转。
误区：稳定排序能修复错误比较器。 稳定性只处理相等元素顺序，不能修复违反契约的比较器。
追问：为什么有些排序会因为比较器错误抛异常？ 因为算法检测到比较方法违反一般契约。
追问：多关键字排序如何保证确定性？ 在主要字段相等时继续比较次要字段，最后可用唯一 id 打破平局。

简化版

详细版