前几天帮一个朋友看面试复盘他说被问到一个很朴素的问题让你手写一个Java排序算法你会写什么他脱口而出冒泡排序然后对面追问了一句那Arrays.sort在你现在的JDK里底层用的是哪种排序朋友当场卡壳。这个问题其实很有意思它从一道“背板题”直接跳到了“你有没有读过JDK源码”的维度。今天这篇就围绕Java全排序算法实现和不同版本JDK排序策略展开把两件事一次性讲透第一手写八大排序时哪些细节决定性能第二Arrays.sort和Collections.sort在JDK各个版本里分别经历过什么变化这些变化又给咱们留下哪些坑。写这篇文章的另一个出发点是我发现很多人在网上搜“八大排序算法总结”但搜出来的大多是背诵清单真正能把JDK内置排序的源码行为对应起来的很少。如果你正在准备Java面试、想理解排序源码或者维护着老项目准备升级JDK这篇都值得看完。1. 手写八大排序先搞清楚每一种的适用边界1.1 先分个类比较排序与非比较排序怎么选很多人背八大排序是从“冒泡、选择、插入、希尔、快排、归并、堆排、计数/基数”这个名单开始的。但我的建议是不要按名单记按“家族”记。八大排序本质上只有两条路子比较排序和非比较排序。比较排序靠元素之间的“大小关系”来排包括交换类的冒泡、快排插入类的直接插入、希尔选择类的简单选择、堆排以及归并类。它们有一个共同的理论下限平均时间复杂度不可能低于O(n log n)原因很简单n个元素的排列方式是n!种每次比较最多得到两种结果那至少需要log2(n!)次才能区分所有情况。这个“比较排序的下界”是理解排序算法的一把钥匙你一旦想通它就知道为什么JDK在int数组很大的时候也没法搞出O(n)的比较排序。非比较排序则绕开“两两比较”直接利用数据分布特征来定位。计数排序把元素值当作数组下标基数排序按位桶排它们可以在特定条件下做到O(n)但代价是空间换时间而且对数据范围有严格要求。有意思的是JDK源码里对byte[]、char[]这类限定范围的数组排序恰恰用的就是计数排序思路这个彩蛋很多人完全不知道。算法平均最好最坏空间稳定性直接插入O(n²)O(n)O(n²)O(1)稳定希尔O(n^1.3)O(n)O(n²)O(1)不稳定冒泡O(n²)O(n)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并O(n log n)O(n log n)O(n log n)O(n)稳定计数/基数O(nk)O(nk)O(nk)O(k)稳定这张表里我最想让你盯住的是“稳定性”这一列。排序算法为什么有稳定不稳定之分稳定指的是两个相等元素排序后先后顺序保持原样。这在很多真实场景里极其重要。举个例子学生列表先按成绩排好再按班级分组你希望每个班级内部的人仍然按成绩从高到低排列。如果第二次排序用不稳定算法班级内部顺序就被打乱了。这就是稳定性的价值。而JDK排序策略的版本变迁很大程度上就是围绕“稳定”这两个字展开的后面会细说。1.2 快排、归并、堆排的代码实现重点八大排序里冒泡、选择、插入是热身级别的希尔是插入的改进型代码都不难。真正值得反复手写的是快排、归并、堆排这三件套因为面试高频、工程常用且实现细节里坑最多。先写快排。我见过太多人写快排只会固定取最左边当枢轴然后一遇到接近有序的数组就退化到O(n²)。工程上至少要加三数取中以及小数组切插入排序。public static void quickSort(int[] arr, int l, int r) { if (l r) return; // 小数组直接插排递归开销远大于直接插入 if (r - l 1 10) { insertionSort(arr, l, r); return; } int p partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p 1, r); } private static int partition(int[] arr, int l, int r) { int mid l ((r - l) 1); // 三数取中让 arr[l] arr[mid] arr[r] if (arr[l] arr[mid]) swap(arr, l, mid); if (arr[l] arr[r]) swap(arr, l, r); if (arr[mid] arr[r]) swap(arr, mid, r); swap(arr, mid, r); int pivot arr[r]; int i l - 1; for (int j l; j r; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, r); return i 1; }这里的几个细节都是有讲究的。三数取中的目的是让枢轴不要落在两端避免最坏情况小数组切换插入排序是因为快排的递归调用、栈帧分配产生的常数很大而插入排序对于十几二十个元素几乎是最快的JDK源码里也一直在用类似的“小数组插排”策略。你甚至可以试一下把阈值从10调到20、30性能还会有一点变化这就是工程调优的味道。归并排序的精髓是分治但它有两个容易被忽视的点。一是它需要一个额外数组所以空间复杂度是O(n)二是当左右两半已经天然有序时可以直接跳过合并这在小数组或接近有序的输入里能省掉大量比较。public static void mergeSort(int[] arr, int l, int r, int[] tmp) { if (l r) return; int m l ((r - l) 1); mergeSort(arr, l, m, tmp); mergeSort(arr, m 1, r, tmp); // 如果左半边最大值 右半边最小值已经有序跳过合并 if (arr[m] arr[m 1]) return; merge(arr, l, m, r, tmp); } private static void merge(int[] arr, int l, int m, int r, int[] tmp) { System.arraycopy(arr, l, tmp, l, r - l 1); int i l, j m 1, k l; while (i m j r) { // 这里用 就是稳定排序的关键 arr[k] tmp[i] tmp[j] ? tmp[i] : tmp[j]; } while (i m) arr[k] tmp[i]; while (j r) arr[k] tmp[j]; }注意归并里那个“”那是保持稳定性的命门。如果写成“”相等元素会从右半边先出来顺序就反了。这个小细节面试官问“归并怎么保证稳定”时大部分人是答不出这一步的。堆排的核心不是排序过程而是堆化过程。用自顶向下的siftDown操作可以在O(n)时间内完成建堆这个叫Floyd建堆法。如果你用逐个插入的方式建堆复杂度是O(n log n)表面上差不多但实测差距很明显。public static void heapSort(int[] arr) { int n arr.length; for (int i (n 1) - 1; i 0; i--) { siftDown(arr, i, n); } for (int i n - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int len) { int v arr[i]; while ((i 1) 1 len) { int child (i 1) 1; if (child 1 len arr[child 1] arr[child]) child; if (arr[child] v) { arr[i] arr[child]; i child; } else { break; } } arr[i] v; }堆排是不稳定排序的典型代表因为交换父子和堆顶末尾元素时会大幅跨越位置把相等元素的相对顺序打乱。所以在需要稳定性的场景里它压根不在候选名单上。1.3 排序稳定性为什么只有引用类型才被重视这里接上前面的话题。稳定性这东西对基本类型数组来说毫无意义因为两个值为7的int完全不可区分谁先谁后没有语义。但对对象数组情况完全不一样两个对象的“排序键”相同不代表它们应该被视为同一个东西。比如一个订单列表先按金额排再按时间排如果金额相同的时间顺序被打乱用户看到的感觉就不对。这也是JDK排序策略里最内核的分野对int[]、long[]这类基本类型数组JDK用不稳定的双轴快排对Object[]、List 这类引用类型JDK坚持用稳定排序。你手写排序时永远要记得先问自己一句这个场景需要稳定吗不需要快排或堆排需要归并或插入。这个判断能力比背十种算法模板都重要。2. Arrays.sort与Collections.sort不同JDK版本里的排序策略2.1 JDK 7那次“悄悄”的重写双轴快排是怎么来的你在JDK 8、11、17里调用Arrays.sort(int[])底层走的都是Dual-Pivot QuickSort双轴快排。这个算法听名字挺玄乎核心思想并不复杂普通快排选一个枢轴把数据分到左右两段双轴快排选两个枢轴把数据分成三段左侧小于pivot1、中间介于两者之间、右侧大于pivot2。段数多了每次递归处理的数据量分布更均匀比较次数整体下降在大量数据下比单轴快排更稳。但双轴快排并不是JDK一开始就有的。JDK 6及更早版本Arrays.sort(int[])用的是经过大量调优的经典快排那时候大家写代码参考书上还会说“Java排序是快速排序”。到了JDK 7Java悄悄把基本类型排序换成了双轴快排同时把排序策略细化成了几条分支数组长度小于47时直接插入排序就不递归了长度在47到286之间走双轴快排长度超过286会先检测数组是否接近有序如果有序段很多、整体比较规整就改用归并排序因为这比继续双轴快排更快。这些分支不是玄学都是从大量真实数据分布里统计出来的经验阈值。这个版本变化给老程序员留下的一个直觉是JDK 7之前int数组的排序是快排系JDK 7之后它变成了一套“看数据下菜”的混合策略。你别小看这个变化它直接导致同一个程序在不同JDK版本下运行排序内部走的路子完全不同性能表现也会不一样。2.2 引用类型走TimSort为什么有归并还要换相比基本类型引用类型数组的排序策略变化更加经典。JDK 6及以前Arrays.sort(Object[])和Collections.sort用的都是经过优化的归并排序。理由是对象排序必须稳定那时归并排序是主流稳定排序里最均衡的。JDK 7开始它们被替换成了TimSort。这个名字来源于Tim Peters他在2002年给Python的list排序设计了这套算法后来被多个语言引入。TimSort本质上“检测天然有序段”加“归并”的组合它会扫描数组把连续升序或降序的片段标记为一个run有序段然后用归并的方式把这些run合并起来。如果输入数据本身大部分是有序的run的数量极少排序几乎退化成一次线性扫描甚至直接完成即使输入完全随机它也能通过控制run的栈和合并时机把最坏复杂度维持在O(n log n)。那为什么有了归并排序还要换成TimSort很简单现实世界里的数据往往不是纯随机数而是“局部有序”的数据库里查出来的记录常常按主键排过一次用户点列表可能就改了两处顺序。归并排序无论数据多有序都要老老实实切分、递归、归并TimSort却能一眼认出“这玩意儿已经快排好了”于是疯狂偷懒。实测在有序或接近有序的数据集上TimSort的优势是碾压级的。后来Android的Collections.sort也换成了TimSort因为移动端很多时候排序的就是用户已经见过的列表。顺带一提因为TimSort连相等元素之间的“反悔”都要严格检查所以JDK 7之后出现了一个经典异常Comparison method violates its general contract。低版本JDK的归并排序面对这个坑往往睁一只眼闭一只眼同一个程序升级JDK后突然就抛异常了。这个坑值得单独开一节细说后面第3.1节会展开这里先记住结论JDK 7是排序策略的分水岭。2.3 JDK 8后的parallelSort和Stream.sorted排序也可以并行JDK 8除了带来Lambda和Stream还给Arrays类加了一个parallelSort方法。它的思路很简单数组足够大时把数组切成若干段丢到ForkJoinPool里并行排序最后再归并。对于int[]数组并行段内仍然用双轴快排合并用归并逻辑对于Object[]数组并行段内用TimSort路径整体保持稳定。parallelSort不是在所有场景下都更快。它有一个内部阈值判断数据量小的时候并行任务调度的开销远大于并行收益跑得反而比普通sort慢。我见过不少同学一看到“并行”两个字就盲目调用结果排序几千个元素反而慢了一倍。经验是数组至少几万以上、机器多核才值得考虑parallelSort否则就用普通sort。另一个和JDK 8相关的变化是List接口多了默认方法sort而Collections.sort内部也改成委托给list.sort。你用list.sort(cmp)和用Collections.sort(list, cmp)最终走的都是同一套逻辑把List转成数组用TimSort排序再写回List。Stream.sorted在串行流下也是走同样的内置排序。换句话说你调用的“排序入口”五花八门但底层大几十行代码都在java.util.TimSort和java.util.DualPivotQuickSort里。下面这张表把不同JDK版本的核心策略变化整理在一起你可以存下来当速查卡版本Arrays.sort(基本类型[])Arrays.sort(Object[]) / Collections.sort说明JDK 6及以前调优经典快排归并排序对象排序稳定但面对“近乎有序”数据没有特殊优化JDK 7双轴快排TimSort分水岭策略变成“按数据形态动态选择”JDK 8双轴快排 平行parallelSortTimSort parallelSort新增并行排序入口串行逻辑与JDK 7一致JDK 11 / 17双轴快排含近有序归并分支TimSort策略稳定官方没有再推翻重来3. 排序策略差异带来的实战坑升级JDK把我代码改崩了3.1 IllegalArgumentExcetion: Comparison method violates its general contract这个异常怕是很多老Java开发者的噩梦。我第一次遇上是在一个老项目从JDK 6升到JDK 8的时候一个跑了好几年的报表模块突然在排序时抛异常日志里就这一句话完全没有错行信息排查难度极高。它的本质是TimSort在归并过程中发现比较器的结果“前言不搭后语”。TimSort要求Comparator严格满足三个规则自反性compare(a,a)0、反对称性compare(a,b)和compare(b,a)符号相反、传递性ab且bc则ac。一旦你的Comparator违反其中任意一条TimSort在merge阶段就会检测到方向反转然后果断抛异常。标准的归并排序不会做这种严格检查所以JDK 6时代它根本不会暴露问题JDK 7换上TimSort后存量代码里的脏比较器全部现出原形。最常见的触发原因有两个。第一个是减法溢出list.sort((a, b) - a - b);这段代码看起来人畜无害但Integer.MAX_VALUE减去一个负数会直接溢出成负数导致比较结果反号。正确写法是用Integer.comparelist.sort(Integer::compareTo);第二个原因是比较器依赖了会变化的字段。比如对象里有个状态字段排序过程中别的地方把它改了导致compare(a,b)先返回a比b大等到下一次再比的时候又返回a比b小。TimSort哪受得了这个。这个坑尤其隐蔽因为现场日志根本看不出排序逻辑哪错了。修复这类问题没有银弹但我给你一个排查路径先看比较器里有没有用减法处理整数差值改成Integer.compare或Long.compare再看多字段比较是不是手工堆了一长串if-else这种情况直接用Comparator.comparing(...).thenComparing(...)链式写法它天然满足契约最后检查比较器依赖的字段是否真的“只读”排序过程中有没有并发或后续操作在改这些字段。这里我强烈建议写Comparator时不要自己拍脑袋实现能链式组合就用链式组合它帮你把99%的契约错误挡在门外。别觉得这是小题大做真实线上能因为这个异常把整个定时任务干翻。3.2 JDK 17选型与部署环境那些事说到JDK版本2025年这个时间点基本就是8和17的拉锯战。JDK 8是很多老公司的“养老版本”但新项目我一般建议直接上17因为Spring Boot 3、Spring 6已经全面要求JDK 17作为基础版本你迟早要面对迁移。从排序策略角度看JDK 17的Arrays.sort和Collections.sort与JDK 8没有本质变化还是双轴快排加TimSort的组合拳所以你不必担心升级到17后排序结果“突然不正常”。真正的升级风险不在这里而在依赖兼容性上。JDK 9开始引入模块系统JDK 17又进一步收紧反射访问一些老框架依赖的setAccessible强行访问内部类会直接报错。另一个高频坑是加密库BouncyCastle很多项目在JDK 8用的bcprov-jdk15on旧版本升到17后因为jar签名和模块化问题加载失败我遇到过的方案是升级到与17兼容的bcprov-jdk15on 1.70及以上版本同时老代码里如果是按JCE Provider方式注册的还需要检查provider注册逻辑是否适配新机制。环境配置也是重灾区。我见过太多人卡在“JDK装好了但java -version不是自己装的版本”这种问题上。Windows配置环境变量时JAVA_HOME千万不要写到bin目录外层PATH里要用%JAVA_HOME%\bin这种形式配置完记得重开命令行因为cmd窗口不会自动加载新环境变量如果机器上有多个JDKPATH里排在前面的会先生效别盯着JAVA_HOME改了却忘了PATH里还塞着老版本。Linux则建议用update-alternatives管理多版本JDK同时检查/etc/profile和~/.bashrc里有没有互相冲突的export。排查命令很简单echo %JAVA_HOME%Windows或echo $JAVA_HOMELinux再用which java看实际解析路径。90%的“配置失败”都能靠这两条命令定位。3.3 排序结果在不同JDK下不一样要不要慌如果你维护老项目从JDK 6升级到JDK 8哪怕比较器完全符合契约也可能发现同样的数据排序后的输出顺序不一样。这不是bug是排序策略变了。JDK 6用经典快排相等元素之间的顺序没人保证JDK 7以后引用类型走TimSort是稳定的基本类型走双轴快排又是不稳定的同一个int数组在两个版本的输出可能有细微差别。什么时候该慌如果业务逻辑依赖“排序后的元素顺序”尤其是相等元素之间的相对顺序你就得明确给它定义。我的做法是加一个次级排序键比如对象自带一个自增id比较器先比主键主键相同再比id这样无论JDK怎么换版本顺序都铁板钉钉。反过来说如果你只是排序后做二分查找或者取前N个那顺序细节不构成问题正常升级即可。4. 手写排序 vs 内置排序用一组压测数据验证策略差异4.1 测试方案随机、有序、近似有序三种输入讲再多源码分析不如跑一组数据来得直观。我搭了一个极简的测试环境JDK 17、Windows 11、i7-12700、默认内存参数没用JMH直接用System.nanoTime取多次运行的中位数。毕竟这里比的只是量级不是基准测试精度。测试输入分三类完全随机的10万个整数已经按升序排好的10万个整数近似有序的10万个整数先排好序再把其中2000个随机打乱。前者代表最常规的乱序数据中者代表最极端的“排序白给”场景最后一个模拟真实世界里最常见的“数据基本有序但有点脏”的情况。参与对比的选手有Arrays.sort(int[])、我自己手写的双轴快排三数取中加插排阈值、Arrays.sort(Integer[])走TimSort、手写归并排序再加上一个手写冒泡排序当“显眼包”参照。测试代码很朴素核心就是记录耗时long start System.nanoTime(); Arrays.sort(randomArray); long cost System.nanoTime() - start; System.out.println(Arrays.sort(int[]) cost: cost / 1000_000 ms);每种情况先预热一轮再跑5次取中间值避免JIT波动影响结论。4.2 结果解读内置排序的“工程化”到底赢在哪我在这台机器上跑出来的量级如下不是精确保准值但能反映倍数关系输入类型Arrays.sort(int[])手写快排Arrays.sort(Integer[])手写归并冒泡10万随机约12ms约25ms约60ms约45ms约13s10万正序约2ms约7ms约2ms约14ms约0.02s10万近似有序约4ms约16ms约5ms约22ms约8s几个有趣的结论。随机场景下Arrays.sort(int[])比手写快排快了将近一倍。这一定程度上来自双轴快排本身的优化但更关键的是JDK里面大量用了系统级内存复制、缓存友好的访问模式以及针对不同数据规模的动态切换。手写的算法逻辑再正确也很难在微优化上追上JDK团队几十年的打磨。正序场景直接暴露了策略差异。手写归并老老实实跑完整个分治流程花了14msArrays.sort(int[])走了近有序检测逻辑很快判断出数据已经有序只花了2msInteger[]走TimSort直接识别出整个数组就是一个run算完一遍就完事也只要2ms。而手写快排即便用了三数取中也得递归到底毕竟它不像TimSort那样能“看”出数据已经有序。近似有序场景更贴近生产现实。JDK内置sort依然游刃有余手写快排接近随机场景的耗时因为随机打乱的那2000个元素让快排无法提前退出仍然要做大量的分区操作。这个例子说明一个道理在已知数据接近有序的业务场景里直接用内置TimSort路径是极优选择。我自己写完这组测试之后最大的体会是不要在生产代码里手写排序。手写排序的价值在于理解原理在于面试在于你被逼到必须实现特殊数据结构的时候而工程场景里JDK内置排序经过多年版本迭代对随机数据、有序数据、近似有序数据、超大数据、并行场景都有了成熟的应对策略你很难写出比它更强的通用排序。5. 常见问题与排查技巧速查5.1 排序实现的六个高频问题把我在实际工作中遇到过、以及被问过最多的问题整理成一张速查表希望能帮你快速定位现象原因解决方案Comparison method violates its general contract比较器违反自反/反对称/传递性TimSort严格检测后抛异常用Integer.compare替换减法用Comparator.comparing链式组合去掉并发字段依赖同样数据升级JDK后排序顺序变了JDK 7从快排换双轴快排、归并换TimSort相等元素顺序策略不同给比较器加次级排序键强制定义相等元素的先后关系基本类型排序结果不稳定int[]底层是双轴快排本身就不保证稳定需要稳定排序时改为Integer[]走TimSort或给对象加id次级键小数组排序性能反而差递归或并行调度开销大于插入排序常数自定义排序时也学JDK长度小于阈值切插入排序parallelSort比sort慢数据量太小并行任务调度开销掩盖了并行收益数据几万以下别用parallelSort优先普通sortjava -version显示的版本不对多JDK环境里PATH顺序问题或JAVA_HOME指错到bin目录检查JAVA_HOME和PATH用which java或echo解析路径确认这里我想再补充一句关于“稳定”的实操细节。你写单元测试时可以快速验证某个排序实现是否稳定构造一堆(key相同但id不同的记录)排序后检查id顺序是否保持原样。这个办法不用查算法定义直接看行为我每次读别人的排序代码都用这招验证比背源码高效得多。5.2 JDK环境与版本升级的避坑清单版本升级和安装配置这块单独拎出来列几条经验Windows配置JDK时JAVA_HOME和PATH是两个不同层级的东西。JAVA_HOME是给构建工具和IDE看的PATH是给命令行直接执行java用的。你要确保PATH里用的是%JAVA_HOME%\bin而不是写死一个绝对路径否则以后换JDK版本又得改一遍。多版本JDK管理用IDEA或者Maven的toolchain基本能解决开发期切换但命令行下还是Linux的update-alternatives最顺手Windows则建议直接用不同版本的完整路径调用比如C:\Program Files\Java\jdk-17\bin\java.exe避免在PATH层面来回调整。从JDK 8升17除了排序策略会从“老版本路径”切到“新版本路径”实际影响不大重点检查三件事第一框架版本是否兼容17尤其Spring Boot 2.x老版本、Lombok旧版本都有兼容问题第二反射访问是否被JPMS拦住第三加密类库如BouncyCastle是否选了兼容17的版本。排序行为反而是最不用担心的环节。最后说一个私人心得与其执着于“用哪个JDK版本”不如把更多的精力花在读JDK源码上。我在读java.util.TimSort和DualPivotQuickSort之后才真正理解为什么JDK团队要设计那么多分支为什么“近乎有序的数据”是常态为什么稳定性在不同类型上有不同优先级。这些东西书本上不会直接告诉你但会让你的排序代码水平原地拔高一截。面试的时候能把手写排序和JDK策略演进讲清楚基本就证明了你对Java底层是“真下了功夫”的而不是只会背模板。