排序在 Java 开发里算是一个“看起来人人都懂真正讲清楚却很难”的话题。业务系统里的列表页、排行榜、订单流、报表导出几乎处处需要排序。但绝大多数人把它当作一个 API 调用sort 一下完事不去想底层跑了什么算法也不去理解稳定性和比较器这些概念背后的业务意义。直到线上出现排序结果漂移、内存翻倍、或者大数组排序慢到怀疑人生才意识到这潭水比想象中深。这篇内容按从易到难的顺序系统梳理 Java 排序的完整脉络先讲透排序前必须建立的基础认知再手写一遍经典算法建立手感然后深入 JDK 自带的高性能排序实现接着讲自定义比较器的实战细则最后聊多字段排序和并行排序的性能调优。不管你是刚入门的学生还是工作几年的开发都能在这条链路里找到对自己有用的那一段。1. 排序算法的基础认知为什么排序是Java开发绕不开的基本功开门见山说排序这个动作在 Java 里分两个维度一个是“对象怎么比”一个是“容器怎么排”。这两个维度如果没理清楚后面写的排序代码很容易带着隐性 bug 上线。我见过不少团队功能测试全绿一上生产就在数据量大的时候翻车最后定位下来不是业务逻辑错而是排序环节的底层认知出了问题。1.1 从比较器到稳定性排序前的三个核心概念第一个概念是自然排序和比较器排序。自然排序指的是对象自己实现Comparable接口规定“我比另一个对象大还是小”。比如Integer、String这些包装类自带 compareTo 逻辑可以直接用。比较器排序则是单独拎出一个Comparator实现类在外部定义两个对象的比较规则。这两者的选择没有绝对的对错关键看排序规则是不是对象的固有属性。比如订单按金额排序金额大小本身就属于订单数据的一部分实体实现Comparable也说得通但“按用户等级降序再按注册时间升序”这种规则往往只是某个后台页面的临时诉求写在实体会让代码变得非常僵硬。第二个概念是比较器和 equals 的一致性。JDK 排序文档里有一条很容易被忽视的约定compare(a, b) 0的时候最好让a.equals(b)也为 true。如果违反这个约定轻则排序结果诡异重则引发数据丢失。我在一个后台管理系统中就遇到过某个状态枚举写了比较器只比较状态编号而没有比较主键结果用TreeSet去重时两个主键不同的对象被当成同一个元素其中一个直接丢了。这事排查了很久最后才发现是比较器一致性破坏了集合语义。第三个概念是稳定性。稳定排序的意思是如果两个元素的排序键相等它们在排序前的前后相对顺序在排序后保持不变。冒泡排序、插入排序、归并排序是稳定的选择排序、快速排序是不稳定的。如果你只排序一次稳定性看起来无所谓但如果先按时间排序再按类别排序第二次排序时你大概率希望第一次的时间顺序还能保留下来。稳定性不是算法教材里的抽象概念它直接决定了业务排序结果是否可预期。1.2 数组与集合的排序入口Arrays.sort和Collections.sort怎么选说完概念说入口。数组排序用Arrays.sort集合排序用Collections.sort或者直接用list.sort二者内部逻辑一致。真正的坑在于这两个入口背后的实现策略完全不一样。排序入口底层算法稳定性适用场景Arrays.sort(int[])DualPivotQuicksort不稳定基本类型数组、性能敏感Arrays.sort(Object[])TimSort稳定对象数组、业务排序Collections.sort/list.sortTimSort稳定集合排序stream().sorted()TimSort封装稳定流式链式操作为什么基本类型和对象类型要区别对待因为基本类型排序不需要保证稳定性快排原地排序、额外内存开销小、速度还快而对象排序时稳定是有业务价值的所以默认走稳定算法。这个差异很多人不知道也是很多博客没有讲透的地方。从使用角度说我的原则是基本类型数组若做性能敏感排序直接用Arrays.sortListInteger这类包装集合优先list.sort配合方法引用既简洁又不容易错。如果走流式处理stream().sorted()底层同样是排序但要注意它通常会创建新数组数据量大时内存开销比原地排序更大。一个百万级订单列表用sorted()排序和用list.sort排序内存表现差异肉眼可见。2. 手写经典排序算法冒泡、选择、插入在真实业务中的取舍有人会说2025 年了还手写排序库函数不香吗手写排序的本质不是为了替换库函数而是让你拥有判断“某个排序场景该用什么策略”的能力。比如数据量只有几十个元素时插入排序往往比 TimSort 更快再比如你要对超大文件做外部排序内部排序的种子选什么直接决定整体性能。基础算法值得亲手实现一遍并且知道它们在什么场景下依然有生存空间。2.1 冒泡排序的优化思路提前终止与双向冒泡冒泡排序教科书里讲得最多实际生产用得最少因为平均复杂度 O(n²) 是硬伤。但它有两个优化思路值得记住。第一个是提前终止。如果某一趟冒泡过程中没有任何交换说明数组已经整体有序直接跳出循环。最理想情况下数据本身基本有序冒泡可以降到接近 O(n)这个特性让它在“几乎有序”的小数据集里意外地能打。第二个是双向冒泡也叫鸡尾酒排序。每趟不仅把最大值往右冒也把最小值往左冒一趟处理两个边界元素对“中间乱、两边整齐”的数据特别有效。但即便优化过冒泡排序还是不适合几百个元素以上的场景。我对它的定位是理解交换、扫描、有序区扩展的好教材也是面试题常客生产环境则基本用不上。真要说实用价值它帮我们建立了一个重要直觉——提前终止这类“识别已有顺序”的优化思想恰恰是 TimSort 这类现代算法的雏形。2.2 插入排序的适用场景与希尔排序的跳跃感插入排序的平均复杂度同样是 O(n²)但实际表现比冒泡好很多原因在于它对“局部有序”数据特别友好而且它是稳定排序。打牌时理牌就是这个过程把新摸的牌插到手上已经排好序的牌堆里。JDK 的DualPivotQuicksort在排序小数组时也会切到插入排序这就是“小数组阈值”优化。希尔排序是插入排序的“跳跃版”。它先按间隔分组做插入排序再逐步缩小间隔最后一次间隔为 1 就是完整插入排序。它打破了 O(n²) 的限制能到 O(n^1.3) 左右。今天看这个算法有点古董但在嵌入式环境、或者你必须手写且不允许依赖库函数的场景下它仍然比纯插入排序优。我手写排序时常用的经验是少于 50 个元素直接用插入排序逻辑简单、常数极小50 到几千个元素看数据是否基本有序有序继续插入排序乱序则上高级算法。这不是死规矩而是基于“算法常数 数据特征”的组合判断。只要理解了这层判断逻辑你在任何受限环境下都能快速给出合适的排序方案。算法平均复杂度最坏复杂度稳定辅助空间冒泡O(n²)O(n²)是O(1)插入O(n²)O(n²)是O(1)希尔O(n^1.3) 左右O(n²)否O(1)快速O(n log n)O(n²)否O(log n)归并O(n log n)O(n log n)是O(n)3. 进阶排序快速排序与归并排序的工程化实现接下来进入真正有工程意义的两个算法快速排序和归并排序。前者是基本类型排序的底牌后者是对象稳定排序的底牌。这两个算法搞明白你再看 JDK 源码时就不会一头雾水。3.1 快速排序的退化问题与三数取中优化快速排序的思想是分治选一个基准元素把数组分成小于基准和大于基准两部分再分别递归排序。平均 O(n log n)常数很小是极致的速度型选手。但快排有个著名软肋如果基准选得不好比如每次都选到最大或最小复杂度会退化到 O(n²)。对已经有序的数组如果还选第一个元素做基准退化成最坏情况几乎是必然。工程上的对策有几种随机选基准、三数取中、引入插入排序兜底。三数取中就是在待排序区间的头、中、尾三个位置取中位数做基准能大幅降低遇到最坏情况的概率代价只是多几次比较所以被大量工业级实现采用。理解了这个道理你就明白为什么简单的“选第一个元素当基准”不能用于生产——不是算法不行是病态输入太容易碰到。顺带提一个快排的稳定问题。经典快排通过交换分区相同元素的相对位置可能变化所以是不稳定排序。如果业务要求相同 score 的用户保持原有先后顺序请直接放弃手写快排用归并或者 Java 自带排序。判断一个排序方案能不能用稳定性常常比速度更优先。3.2 归并排序的稳定性和外部排序思路归并排序的核心是“先分后合”把数组对半拆到最小单元再两两合并有序数组。复杂度稳定在 O(n log n)不受初始顺序影响而且稳定。代价是需要额外 O(n) 辅助空间。这几乎是“用空间换稳定和稳定性能”的典型代表。归并排序在工程上有两个变体很实用。一是原地归并的尝试能省空间但会让常数变大并不总是划算。二是外部排序对超大文件排序时数据不可能全部装进内存于是先分块读取、在内存里排好写回多个有序文件再做多路归并。这本质上是归并排序向磁盘场景的延伸。数据库的 order by 操作、大规模日志排序底层都有外部归并的影子。所以当你听到“外部排序”时不用觉得高深。它的本质就是内存排小块磁盘做合并空间换不来就用时间换。搞懂归并的这一层延展你对“处理不了海量数据”这个问题的理解会立刻上一个台阶。4. Java自带排序的底层逻辑Timsort和Dual-Pivot Quicksort到了这一章我们把目光彻底转向 JDK 内部。很多人调用Collections.sort一辈子却不知道它到底跑的是什么算法。这里把两个核心实现讲透顺便拆掉一些流传已久的误解。4.1 Collections.sort为什么偏爱TimsortCollections.sort底层调用的是List.sort真正干活的是 TimSort。TimSort 是 Tim Peters 在 2002 年设计的一种混合排序算法在 Python 里成名后来被 Java 7 引入作为对象排序的默认实现。它为什么厉害核心是“识别自然有序片段”。TimSort 会把数组扫描成一系列升序或降序片段长度达到阈值的小片段用二分插入排序变成有序片再按规则两两合并。现实世界的数据很多是局部有序的比如按时间追加的日志、按 id 递增的数据库记录TimSort 能利用这种局部有序性把预期复杂度压到接近 O(n)。最坏复杂度仍然 O(n log n)稳定内存开销 O(n)。这组特性让它在处理半有序数据时格外有优势。稳定性方面TimSort 是稳定的。这解释了为什么 Java 选择它作为对象排序默认算法——对象排序往往意味着业务场景业务场景往往需要稳定。理解了这一层你再看“为什么不用快排排序对象”这个问题答案就自己跳出来了。4.2 Arrays.sort对不同类型数据的差异化策略Arrays.sort更精分。对于int[]、long[]、float[]等基本类型数组底层走的是 DualPivotQuicksort双基准分区能显著减少比较次数和递归深度还包含小数组切换插入排序的优化。基本类型没有对象身份的稳定需求所以怎么快怎么来。对于Object[]JDK 仍然使用 TimSort因为对象排序要稳定性。同一个工具类两套逻辑这是很多 Java 程序员从未注意到的细节。还有个很实用的坑Arrays.sort对对象数组的默认实现要求元素实现Comparable否则直接抛ClassCastException。堆栈上常见报错线索是ComparableTimSort.countRunAndMakeAscending新手看到这一行就懵实际上就是某个对象没实现 Comparable。场景算法是否稳定推荐理由基本类型数组DualPivotQuicksort否速度优先原地排序对象数组 / 集合TimSort是业务排序需要稳定性小数组阈值内插入排序是常数极小避免递归开销海量数据外部排序归并思路可稳定内存受限时唯一选择5. 实战经验自定义排序的Comparator使用细则库函数再好最终还是要通过比较器和自定义逻辑接到业务上。这一章讲讲我踩得最多的 Comparator 使用细节每个都是线上教训换来的。5.1 Comparable与Comparator的选择原则再强调一遍选择原则。实体类有天然业务顺序比如按 id 大小、按时间先后可以实现Comparable如果顺序只是某个页面的展示需求甚至同一个实体在不同页面有不同排序规则就不要实现Comparable应该传Comparator。举个例子订单类在后台列表需要按下单时间排序财务导表需要按金额排序物流需要按状态排序。如果实体里写了 compareTo这个顺序就焊死了后面每个新需求都得改实体。更优雅的做法是定义多个静态比较器比如ORDER_BY_TIME、ORDER_BY_AMOUNT、ORDER_BY_STATUS调用方自己选择。这个习惯能帮你避免大量实体类职责膨胀问题也让排序规则可以被单独测试。5.2 稳定性在业务排序中的实战意义避免排序结果跳动稳定性另一个容易被忽略的业务影响是“排序结果跳动”。举一个真实例子列表页一次展示 100 条记录默认按权重排序。权重相同的记录如果底层是不稳定排序刷新一次页面顺序就变一次用户会觉得很奇怪甚至误以为系统在乱搞。换成稳定排序后权重相同的记录保持第一次查询的相对顺序体验立刻正常。那么“相对顺序”从哪来通常来自数据库主键、自增 id或者插入时的先后顺序。也就是说让权重相同的记录按 id 升序本质上就是利用“先插入的先展示”。写法也不复杂链式比较器先比较权重再比较 idlist.sort(Comparator.comparing(User::getWeight) .thenComparing(User::getId));这行代码背后就是稳定排序在业务层的典型落地方式。5.3 比较器返回值的边界不要迷信“减一减”比较器里最经典的坏习惯是return a.score - b.score。这行代码在数值较小时没问题但一旦 score 是很大的整数减法可能溢出比较器就返回了完全错误的符号排序结果随之混乱。我在代码评审里看到这种写法一律要求改成Integer.compare(a.score, b.score)。排序逻辑是最容易被溢出 bug 波及又最难察觉的地方因为数据量小、数值范围窄的时候它永远不犯错一旦数据范围跨过临界点问题就突然出现排查成本极高。同样的逻辑也适用于字符串比较别用a.name.compareTo(b.name)之外的自己造轮子的写法。官方提供的 compare 方法都处理好了空值和边界自己写的字符串比较逻辑很容易遗漏大小写、空字符串这些细节。6. 多字段排序、并行排序与性能调优的落地细节最后一章聊更落地的东西当单字段排序不够用、数据量又上来时怎么组合应对。这一章的每一条都是在真实压测和线上问题里验证过的经验。6.1 多条件排序的链式写法多条件排序最简单也最不容易出错的写法是 Java 8 之后的Comparator.comparing加thenComparing。比如“先按下单时间倒序再按金额升序再按 id 升序”一句话就能写出来list.sort(Comparator.comparing(Order::getCreateTime, Comparator.reverseOrder()) .thenComparing(Order::getAmount) .thenComparing(Order::getId));注意Comparator.reverseOrder()要作为第二个参数传给comparing而不是在链式后面直接跟reversed()否则会把整个链倒转。这是个高频翻车点。我见过有人把.reversed()加在链尾结果原本升序的金额被整体反转id 也被反转线上排序结果完全不符合预期排查半天才发现是反转范围搞错了。6.2 大数据量下的并行排序与注意事项Java 8 在Arrays里增加了parallelSort它对基本类型数组有真正的并行加速效果。它会把数组拆成多段并行排序最后再归并。实践经验是只有数组真的很大时才值得用我个人的模糊门槛是最少几万元素起步实际要看机器核心数和数据特征。小数组开并行反而因为线程调度开销拖慢速度。对集合排序list.parallelStream().sorted()看似也能并行但它会额外创建集合副本内存开销巨大排序本身也未必能并行化到预期效果。我踩过一次百万级对象列表用并行流排序内存直接涨了两倍多最后换回普通list.sort加链式比较器内存降下来速度也没有变慢。所以并行排序是好工具但不能无脑用。另外parallelSort对对象数组依然是稳定排序因为它底层是并行归并不是快排。基本类型数组的稳定性没意义所以可以用快排思路做并行分区。实际项目中除非压测得到可量化的性能提升否则不建议默认开启并行排序多线程带来的是复杂度和不确定性。6.3 性能调优时的测量方法排序性能调优最忌讳凭感觉。我建议用 JMH 写小测试分别测list.sort、手写排序、并行流排序在 1 万、10 万、100 万数据量下的表现。多测几轮取稳定值再决定。很多时候你会发现真正决定性能的不是排序算法本身而是比较器实现——如果比较器里做了数据库查询或字符串格式化排再快的序也没用。这个经验几乎可以套用所有排序场景先简化比较器再考虑换算法最后才考虑并行。顺序反了往往事倍功半。比如有一次我发现排序特别慢初步怀疑是算法问题结果一查比较器里对每个元素都做了一次远程状态拉取。把远程调用移出去提前算好排序耗时直接降了两个数量级根本没到换算法那一步。优化排序的正确姿势是先让比较器变成纯内存计算去掉一切 IO 和重复计算再看数据量级是否值得换算法最后才引入并行。这套顺序我反复用了很多年几乎没有失手过。最后分享一个我自己摸索出来的小习惯写任何排序代码前先在心里回答三个问题——这个排序需要稳定吗排序规则属于实体本身还是仅属于当前场景比较器参数会不会有溢出风险三个问题回答完代码该怎么写基本已经有了。别小看排序排好序的代码往往比那些花哨的框架特性更能撑住真实业务。
