只要前 100 名，为什么要把一百万条全排一遍

从 100 万条报名记录里取分数最高的 100 条，全排序要 501ms，用一个大小为 100 的堆只要 34ms。可是换成快速选择，取出来的 100 条和前两种不一样，三种写法都没有错，是比较器少了一条同分规则。

活动结束后要按分数给报名记录排名：导出全部名次、取前 100 名发奖、在线维护一个实时榜单。这三种需求都叫「排序」，但要的结果不同。导出全部名次需要全序；发奖只要前 K 名；实时榜单要在数据不断到来时随时回答「当前前 K 名是谁」。选错做法，要么多花几倍的时间，要么结果不稳定。

本文用同一份数据比较三种做法：全排序、大小为 K 的堆、快速选择。数据是 100 万条报名记录，每条有分数、提交时间和 ID，结果都在 JDK 21.0.5 上实测，见文末配套实验。站内的工程里用得上的十个算法套路里有堆的基本写法，这篇讲怎么选、怎么写对。

一、先把比较器写对

三种做法都依赖同一个比较器。比较器写错，哪种做法都救不回来。最常见的错误是用减法：

java

list.sort((a, b) -> (int) (a.createdAt() - b.createdAt()));   // 错：差值可能超出 int
list.sort(Comparator.comparingLong(Signup::createdAt));       // 对

createdAt 是毫秒时间戳，两条记录相差超过约 24.8 天，差值就超出了 int 的范围，截断后符号可能翻转，「早」和「晚」就颠倒了。实测按提交时间给跨度半年的记录排序：

数据量	结果
1 万条	抛出 `IllegalArgumentException: Comparison method violates its general contract!`
20 条	没有异常，但有 9 处相邻的两条顺序是反的
改用 `Comparator.comparingLong`	顺序正确

大列表会抛异常，是因为 JDK 的对象排序（TimSort）在归并阶段能发现比较结果前后矛盾。少于 32 个元素时只做二分插入排序，不会走到归并，结果错了也不会报错。测试数据少，上线后数据一多就抛异常，这是这类问题的典型表现。int 分数相减同样会溢出，比较数值一律用 Integer.compare、Long.compare 或 Comparator.comparingXxx。

二、同分时谁排前面，要写进比较器

分数只有 1,000 种取值（0—999），100 万条记录里，第 100 名的分数是 999，而分数为 999 的记录有 1,016 条。前 100 名里有多少条是 999 分可以确定，但具体是 1,016 条里的哪几条，比较器没说。

比较器	全排序	堆	快速选择
只比较分数	结果 A	结果 A	结果 B
分数 → 提交时间 → ID	结果 C	结果 C	结果 C

只比较分数时，全排序和堆碰巧一致：List.sort 是稳定排序，同分的保持原来的顺序；堆只在新记录严格更好时才替换堆顶，同分的也是先来的留下。快速选择按划分交换元素，同分的谁留下取决于交换过程。这种「碰巧一致」很危险，换一种实现、调整一下读取顺序，结果就变了。

把规则写完整：分数高的在前，同分时先提交的在前，再同就按 ID。这时三种做法选出的 100 条完全相同。

java

static final Comparator<Signup> RANKING = Comparator.comparingInt(Signup::score).reversed()
        .thenComparingLong(Signup::createdAt)
        .thenComparingLong(Signup::id);          // 最后一级必须唯一，结果才是确定的

发奖、导出名次、分页展示都依赖结果确定：同一份数据查两次，第 100 名不能是两个不同的人。

三、三种做法的代价

图 1 · N = 100 万时实测（5 次中位数）：K=100，全排序 501 ms、堆 34 ms、快速选择 89 ms；K=50 万，堆反而最慢（593 ms），快速选择最快（366 ms）。三者只要比较器相同、同分规则完整，结果就相同

N = 100 万时实测（5 次中位数，三种做法的结果都相同）：

K	全排序	堆	快速选择
100	501 ms	34 ms	89 ms
1 万	472 ms	53 ms	89 ms
50 万	457 ms	593 ms	366 ms

全排序的代价和 K 无关，总是把 N 条都排好。需要完整名次、或者同一份数据要按不同 K 反复取时，排一次最省事。

堆只保留 K 个元素，每条记录和堆顶比一次，比堆顶差就直接丢掉。K 远小于 N 时最快，内存只占 K 个元素，还能处理流式数据：数据一条条到来，堆里始终是当前的前 K 名，适合实时榜单。K 变大时每次替换的代价随 log K 增长，K 等于 50 万时比全排序还慢。

快速选择用快速排序的划分找到第 K 名的位置，左边都不比它差，再只对这 K 个排序。平均是线性时间，K 很大时仍然快；代价是要把数据放进可以随机访问的数组，并且会打乱原数组的顺序。大量同分时，划分要分成「小于、等于、大于」三路，否则会退化。

所以：K 远小于 N、或者数据是流式的，用堆；K 和 N 同一个数量级、数据已经在内存里，用快速选择；需要完整名次，全排序。JDK 没有提供快速选择，要自己写，并且要用大量同分、已排序、逆序的数据测过。

四、数据分在多个地方时

数据在多个分片（分库、多个节点、多个文件）上，常见的做法是每个分片先算本地前 K 名，再把各分片的结果合并，取前 K 名。这样做是否准确，取决于排名的对象。

按记录排名是准确的。 每条记录的分数是确定的，全局前 K 名中的每一条，在它所在的分片里也一定排在前 K。实测 3 个分片各取前 100 再合并，和直接在全部数据上取前 100 的结果相同。

按 key 聚合计数就不准确了。 比如「报名人数最多的城市」，每个分片只知道自己那部分的计数：

图 2 · x 在每个分片都只排第 3（40 次），三片合计 120 次才是全局第一。每个分片只上报本地前 2（虚线以上）时，x 一次都没被报上来，合并结果的第一名是 a=50；每个分片多报一名，x=120 才出现

x 在每个分片都只排第 3，三片加起来却是全局第一。每个分片只上报本地前 2 时，x 一次都没被报上来，合并后的第一名是 a=50，而 x 实际有 120。每个分片多上报一些（这里多报一名），x 才出现。

多报多少才够，没有通用答案，取决于数据分布：分布越均匀、各分片的头部越不一样，需要多报的越多。要精确结果，只能让每个分片上报全部 key 的计数，或者先按 key 重新分区，让同一个 key 只落在一个分片上。Elasticsearch 的 terms 聚合就是「每个分片多报一些」的做法，误差和 shard_size 参数的实测见 ES 聚合为什么不准。

五、怎么选

先定结果契约：要完整名次还是前 K 名；同分怎么排（最后一级必须唯一）；数据是一次性给定还是持续到来。
比较器用 Comparator.comparingXxx 组合，不写减法；用大时间跨度、正负极值的数据测一次。
K 远小于 N 或流式数据，用堆；K 和 N 同一数量级，用快速选择；需要完整名次，全排序。
跨分片时分清排名对象：按记录排名可以先本地 Top K 再合并；按 key 聚合要么多报、接受误差并说明，要么按 key 重新分区。
榜单放在 Redis 等外部存储时，同分规则要编码进分数本身，见典型业务功能设计中的排行榜一节；数据库里的 ORDER BY ... LIMIT 怎样利用索引，见 SQL 调优实战。

配套实验

codesphere-labs/system-design/sorting-selection-topk：减法比较器的溢出、同分规则对三种做法结果的影响、N = 100 万时不同 K 的耗时、分片 Top K 的两个对照（验证记录）

参考资料

JDK 21 API：Arrays.sort(T[], Comparator)（稳定排序；实现改编自 TimSort；比较器违反契约时可能抛出 IllegalArgumentException）
JDK 21 API：Comparator
JDK 21 API：PriorityQueue

只要前 100 名，为什么要把一百万条全排一遍 ​

一、先把比较器写对 ​

二、同分时谁排前面，要写进比较器 ​

三、三种做法的代价 ​

四、数据分在多个地方时 ​

五、怎么选 ​