自定义排序如何设计比较键？多关键字排序有哪些坑？

简化版

自定义排序先明确排序键和优先级：先比主键，主键相同再比次级键，仍相同再决定是否保留原顺序或继续比较唯一键。比较器必须满足自反、反对称、传递性，不能写成随状态变化的逻辑，也不要用整数相减避免溢出。多关键字题常见模式是“频率降序 + 数值升序”“结束时间升序 + 开始时间升序”“分数降序 + 原下标升序”。

详细版

很多排序面试题难点不在排序算法，而在比较器设计。比较器要回答两个问题：先按什么排？相等时怎么打破平局？例如“按频率从高到低，频率相同按数值从小到大”，就先比较频率，频率不同返回高频在前；频率相同再比较数值。

items.sort((a, b) -> {
    if (freq.get(a) != freq.get(b)) {
        return Integer.compare(freq.get(b), freq.get(a)); // 频率降序
    }
    return Integer.compare(a, b); // 数值升序
});

面试要特别说明比较器合法性。不能写 return b.score - a.score，因为可能溢出；不能在比较过程中修改参与比较的字段；不能让 a < b、b < c、c < a 同时成立。若要求稳定排序，可以使用语言提供的稳定排序，或把原始下标作为最后一个 tie-breaker。

完整版教学

一、先把需求翻译成排序键

自定义排序的第一步不是写 lambda，而是把自然语言需求拆成有序的 key 列表。比如“成绩高的在前，成绩相同年龄小的在前，仍相同保持原顺序”，对应 key 是 score desc、age asc、originalIndex asc。只要 key 列表清楚，比较器就会非常稳定。

如果不拆 key，很容易写出互相冲突的判断。比如“VIP 优先、价格低优先、时间早优先”，要先确认 VIP 是否比价格更重要。如果 VIP 是主键，那么普通用户价格再低也排在 VIP 后；如果价格是主键，那 VIP 只在价格相同时生效。面试中主动澄清优先级，会显得很专业。

需求描述	主键	次级键	备注
分数高优先，时间早优先	分数降序	时间升序	排行榜常见
频率高优先，数值小优先	频率降序	数值升序	Top 频率题常见
区间结束早优先	结束升序	开始升序	贪心区间题常见

二、比较器必须满足一致性

排序库通常假设比较器是一个合法的“严格弱序”或全序近似。用面试话术讲，就是比较结果要稳定一致：同一对元素反复比较结果不能变；如果 a 应排在 b 前，b 应排在 c 前，那么 a 也应该排在 c 前；相等元素要返回 0 或继续用 tie-breaker 明确顺序。

反例很常见：比较器里调用随机数，或者根据当前时间决定顺序，会导致同一对元素前后结果不一致。另一类反例是循环偏好，比如石头剪刀布式比较：石头胜剪刀、剪刀胜布、布胜石头。这种关系不能排序，因为不存在线性顺序。

合法排序需要避免：
a < b
b < c
c < a

记忆钩子：比较器不是“判断一次谁赢”，而是给所有元素安排一条不会自相矛盾的队伍。

三、不要用减法写比较结果

很多人喜欢写 return b.score - a.score 表示降序，但这有整数溢出风险。若 b.score = Integer.MAX_VALUE、a.score = -1，相减会溢出成负数，排序方向直接错。更稳妥的写法是 Integer.compare(b.score, a.score) 或语言对应的安全比较函数。

还有一个坑是浮点数比较。浮点里可能有 NaN、-0.0 等特殊值，直接用减法转 int 更危险。面试中如果字段可能溢出或是浮点，主动说用安全比较函数，会比手写减法更可靠。

// 不推荐
return b.score - a.score;

// 推荐
int cmp = Integer.compare(b.score, a.score);
if (cmp != 0) return cmp;
return Integer.compare(a.age, b.age);

四、多关键字排序的代码结构

多关键字排序推荐写成“逐层比较，非 0 立即返回”。这样逻辑和需求一一对应，也便于审查。降序可以交换参数位置，升序按自然顺序比较。字符串可以用 compareTo，布尔值可以映射成 0/1 或用比较函数。

例如排序学生：分数降序、年龄升序、姓名字典序升序。若 A 分数 95、年龄 20，B 分数 95、年龄 18，那么 B 应排前，因为主键相同后比较年龄。若年龄也相同，再比姓名，避免相等元素顺序在不稳定排序中漂移。

students.sort((a, b) -> {
    int c1 = Integer.compare(b.score, a.score); // 分数降序
    if (c1 != 0) return c1;
    int c2 = Integer.compare(a.age, b.age);     // 年龄升序
    if (c2 != 0) return c2;
    return a.name.compareTo(b.name);            // 姓名升序
});

五、稳定排序和原始下标

如果题目要求“相同 key 保持原顺序”，需要稳定排序。若语言库保证当前排序稳定，可以直接依赖；如果不确定，或者底层排序不稳定，就给每个元素附加原始下标作为最后一个比较键。这样即使排序算法不稳定，也能模拟稳定效果。

举例：原始输入 A(90), B(90), C(80)，按分数降序且同分保持原顺序。比较器最后加 originalIndex asc，A 的下标小于 B，所以 A 在 B 前。这个技巧在日志排序、排行榜同分排序、分页结果一致性中很常见。

方法	是否依赖排序稳定性	额外成本	适用
使用稳定排序	是	低	语言明确保证稳定
原下标 tie-breaker	否	存一个下标	需要跨语言稳妥
不处理平局	否	低	平局顺序无要求

六、排序键预计算能避免重复成本

比较器会被调用 O(n log n) 次，如果每次比较都重新计算昂贵 key，会拖慢排序。例如按字符串解析后的日期排序，若在比较器里反复 parseDate，同一条记录可能被解析很多次。更好的做法是先把 key 预计算出来，再排序引用或包装对象。

带数字估算：n=100000 时，排序比较次数约 100000 * log2(100000) ≈ 166万。如果每次比较都解析两个日期，就可能产生 300 多万次解析；预计算只需要 10 万次。这个优化在自定义排序题里经常作为追问出现。

原始做法：比较时 parse(a.date), parse(b.date)
优化做法：预先 dateKey = parse(date)，比较时直接比 dateKey

七、常见误区与追问

误区：比较器返回 true/false 就够了。 大多数排序接口需要负数、0、正数来表达小于、等于、大于，布尔值无法表达完整关系。
误区：用 b-a 写降序最简单。 整数可能溢出，应该用 Integer.compare、Long.compare 或安全比较函数。
误区：相等时随便返回 1。 相等元素如果不返回 0 或明确 tie-breaker，会破坏比较器一致性。
追问：如何保证同分保持原顺序？ 使用稳定排序，或把原始下标作为最后一个升序比较键。
追问：比较器里能查哈希表吗？ 可以，但哈希表内容必须在排序期间不变；昂贵 key 最好预计算。
追问：多关键字排序怎么验证？ 构造主键不同、主键相同次级键不同、所有 key 相同三类用例。

八、加强记忆

自定义排序的核心是“先列 key，再写比较器”。主键决定大方向，次级键负责平局，原始下标负责稳定性。比较器必须一致、可传递、无副作用；降序不要用减法，昂贵 key 要预计算。遇到多关键字排序题，就把需求写成 key1 asc/desc -> key2 asc/desc -> tie-breaker，代码自然不会乱。

简化版

详细版