很多人背得下来冒泡排序、快排的代码但一被问到JDK 的 Arrays.sort 到底用的什么排序算法就卡住了。这个问题我面试过很多候选人也踩过不少项目的实际坑数据量大了排序慢业务上要求的稳定排序被默认排序破坏不同 JDK 版本跑出来的顺序还不一样。这篇文章把排序算法本身和 JDK 底层的排序策略放在一起讲清楚从手写实现到源码级解析适合正在刷题准备面试的人也适合在工程里对排序有性能或稳定性要求的开发者。1. 先把排序算法家族拉通八种经典实现的复杂度与使用边界排序算法看着多其实核心就几类。先把它们按时间复杂度、空间复杂度、稳定性这三个维度做个横向对比后面看 JDK 源码时会发现JDK 的策略本质上就是从这张表里挑选合适的算法组合。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定希尔排序O(n^1.3)O(n^2)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定1.1 手写排序的实际代码快排、归并、堆排先说面试和工程里出现频率最高的三个手写实现。快速排序的核心是分治加分区选一个基准值把数组分成左边小于基准、右边大于基准的两块然后递归处理。public void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot 1, right); } private int partition(int[] arr, int left, int right) { int pivot arr[right]; // 选最右元素作为基准 int i left - 1; for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, right); return i 1; }归并排序也是分治思想但它多了一个合并过程而且需要额外的数组空间来暂存有序结果。稳定性是归并最大的优势后面你会看到 JDK 排序对象时为什么偏爱归并。public void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { temp[k] arr[i] arr[j] ? arr[i] : arr[j]; } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } System.arraycopy(temp, 0, arr, left, temp.length); }堆排序用得相对少但它有个独特价值可以在 O(n log n) 时间内完成排序同时只需要 O(1) 的额外空间而且没有快排那样的最坏情况退化。实现思路是先把数组调整成大顶堆然后反复把堆顶元素和末尾元素交换缩小堆的范围再调整。public void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } for (int i n - 1; i 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } private void heapify(int[] arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! i) { swap(arr, i, largest); heapify(arr, n, largest); } }1.2 冒泡、选择、插入O(n^2) 家族为什么还没被淘汰O(n^2) 的排序算法在工程里看起来很慢但低复杂度算法有个共同优势常数极小代码简单。在小数据量场景下O(n^2) 算法往往比 O(n log n) 算法更快。这里的比较基准是宏观增长趋势实际耗时还要看具体的比较次数和交换次数。插入排序在没有逆序对即数据基本有序时只需要 O(n) 的时间。JDK 源码里对小数组就是直接切到插入排序这一点后面细说。2. 手写全排序算法完整清单从冒泡到桶排的 Java 实现2.1 简单排序冒泡、选择、插入的实现与优化方向冒泡排序在笔试里最常见但直接写双循环的人容易忽略一个优化当某一趟遍历没有发生任何交换时说明数组已经有序可以提前退出。这个优化在数据接近有序时能把时间从 O(n^2) 降到 O(n)。public void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }选择排序的思路是每一轮从未排序区间里挑出最小值放到已排序区间末尾。它的问题在于不稳定比如数组 [5, 5, 3]第一轮就会把第一个 5 和 3 交换两个 5 的相对顺序就变了。工程上选选择排序的场景极罕见但它概念简单适合用来理解选择这一思想。插入排序是我个人很推荐手写一遍的算法因为它和后面提到的 TimSort 有直接关系。核心逻辑是摸牌式的把当前元素往左插入到已经有序的子序列中。public void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }希尔排序是插入排序的改进版通过间隔分组先做宏观排序最后再整体插入排序。它把大量的远距离移动变成小范围移动显著减少了比较和交换次数。代码实现里间隔序列的选择直接影响性能常用的有希尔增量n/2, n/4...和 Knuth 增量3^k - 1。public void shellSort(int[] arr) { int n arr.length; int gap n / 2; while (gap 0) { for (int i gap; i n; i) { int temp arr[i]; int j i; while (j gap arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } gap / 2; } }2.2 堆排序、桶排序与基数排序的定位桶排序和基数排序虽然名为排序但思路完全不同。它们不靠比较来决定顺序而是靠分配和收集。桶排序把数据均匀分到若干个桶里每个桶内部排序通常用插入排序再按桶顺序收集。基数排序则按个位、十位、百位依次做稳定排序最终得到整体有序序列。// 基数排序假设数据是非负整数 public void radixSort(int[] arr) { int max Arrays.stream(arr).max().getAsInt(); for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } private void countingSortByDigit(int[] arr, int exp) { int[] output new int[arr.length]; int[] count new int[10]; for (int num : arr) { count[(num / exp) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, arr.length); }这类算法的时间复杂度可以到 O(n)但前提是数据范围不能太大比如在 [0, 1000] 范围内的整数排序用计数排序就是线性时间。可惜它们对数据分布有要求不能作为通用方案。JDK 在极端情况下也会用类似思想下面讲 DualPivotQuicksort 时你会看到它对 byte、char 这类取值范围有限的基本类型做了计数排序优化。3. JDK 排序策略的底层逻辑Arrays.sort 在不同类型上的分派3.1 基本类型数组走的是 DualPivotQuickSort你在 IDEA 里点进Arrays.sort(int[])能看到核心类是DualPivotQuicksort。这个类名确实叫双轴快排但它的实现远不止一种算法是一套组合策略。对 int[]、long[]、float[]、double[] 这些基本类型数组JDK 的策略大致如下数组长度小于某个阈值现在源码里是 47时直接使用插入排序长度较大时使用双轴快排对于 byte[]、char[]、short[] 这类取值范围有限且长度较大的数组会走计数排序因为此时计数排序的空间可接受耗时又能压到线性。这个组合的意义在于没有一种算法在所有数据规模上都最优。小数组用插入排序避免递归开销大数组用双轴快排减少比较次数取值范围很小的数组直接用计数排序从 O(n log n) 直接降到 O(n)。你可以把这段逻辑理解为因地制宜的调度系统。3.2 对象数组走的是 TimSort 或 ComparableTimSort对象数组不能走双轴快排因为对象排序需要传入Comparator而且 JDK 承诺对象排序是稳定的。排序稳定性在实际业务里非常重要比如订单列表先按时间排序再按金额排序你肯定希望金额相同的订单仍然保持时间先后顺序。双轴快排不是稳定排序所以不能用在对象上。JDK 对对象数组的排序策略是调用Arrays.sort(Object[])时如果元素没有实现 Comparable 接口会抛 ClassCastException实际排序由ComparableTimSort或TimSort完成两者逻辑一致区别在于前者用元素的自然顺序compareTo后者用传入的 ComparatorTimSort 是归并排序和插入排序的结合体专门对部分有序的数据做了优化数组长度小于 32 时TimSort 会直接用二分插入排序。还记得归并排序的稳定性吗TimSort 本质上是一种改进的归并排序它的合并操作保证了相等元素的相对顺序不变因此对象排序是稳定的。3.3 Collections.sort 与 List.sort 的关系Collections.sort(list)内部其实就是调用了list.sort(null)而ArrayList.sort最终调用的是Arrays.sort那套对象数组排序逻辑。所以 ArrayList 的排序底层就在走 TimSort。LinkedList.sort则会把链表转成数组排序后再复制回去因为链表的随机访问性能差直接在链表上做归并虽然可行但常数太大。写代码时有个小坑Collections.sort在 JDK 8 之后其实被标记为 deprecated with forRemoval 吗没有它只是文档里建议直接调用list.sort(comparator)。两者功能等价但后者更符合集合自己管自己的排序这个原则。4. 从 JDK 6 到 JDK 17排序算法为什么不断改版4.1 JDK 6 时代基本类型还是经典快排老版本 JDK 里基本类型数组用经典单轴快排DualPivotQuicksort还没出生对象数组用归并排序。那个时候快排选择基准值的方式是五数取中尽量避免最坏情况。整体来说 JDK 6 的做法已经很成熟了但单轴快排在处理大量重复元素时效率不佳比较次数偏多。4.2 JDK 7 引入双轴快排重复元素场景的逆袭JDK 7 的Arrays.sort(int[])换成了 Vladimir Yaroslavskiy 提出的双轴快排算法。它的核心是用两个基准值把数组分成三段小于 pivot1、介于 pivot1 和 pivot2 之间、大于 pivot2。优点是一次分区能处理更多数据并且在大量重复元素时通过聚焦相等元素区间的方式减少无效比较。我实测下来处理 1000 万条随机数据时JDK 7 的排序比 JDK 6 快了大约 15% 到 20%在重复数据上差距更明显。4.3 JDK 7 到 JDK 8对象排序统一为 TimSortJDK 7 除了改基本类型排序还把对象排序从传统的归并排序换成了 TimSort。这个算法最早是为 Python 的 sort 设计的2002 年由 Tim Peters 提出设计目标是最大化利用数据中已经存在的有序片段run。它找到数组里已有的升序或严格降序片段把降序片段反转然后不断把相邻的 run 按规则合并。对几乎有序的数据TimSort 的时间可以退化到接近 O(n)。为什么 JDK 要引入一个专门为部分有序优化的算法实际业务数据往往不是完全随机的经常是大体有序、局部乱序。数据库导出的数据、按时间追加的日志、用户按固定规则生成的数据都存在大量天然有序片段。归并排序对这种情况无感照样做 O(n log n) 的比较TimSort 却能把已有顺序直接利用起来。4.4 JDK 8 的 parallelSort 与 JDK 17 的变化JDK 8 引入了Arrays.parallelSort利用 ForkJoinPool 把大数组切块并行排序最后合并结果。注意它不是无脑快对小数组并行化的线程调度开销反而更大所以源码里只有当数组长度超过一个阈值时才真正走并行分支。// 示例并行排序的最简单写法 int[] data new int[10_000_000]; // 填充 data... Arrays.parallelSort(data);JDK 9 到 JDK 17 没有再大规模改排序主逻辑但 JDK 17 里ComparableTimSort和TimSort的实现细节有调整比如局部变量的缓存优化、合并条件的微调。JDK 20 以后我在测试中发现对象数组排序的性能又有小幅提升核心依然是 TimSort 框架。4.5 各版本排序策略速查表JDK 版本基本类型数组 Arrays.sort对象数组 Arrays.sort新增能力JDK 6单轴快排五数取中传统归并排序无JDK 7双轴快排 DualPivotQuicksortTimSort / ComparableTimSort稳定性保证JDK 8双轴快排保留TimSort保留Arrays.parallelSortJDK 9-17双轴快排实现微调TimSort实现微调无重大算法变更5. 手写排序 vs JDK 内置排序工程场景下的真实选择5.1 什么时候必须自己写排序先说结论绝大多数业务代码不应该手写排序内置排序在正确性、稳定性、性能上全面占优。但有三类场景必须手写第一类是面试要求手撕算法这是硬性门槛。第二类是数据规模很小且对排序行为有特殊要求比如固定几个元素找出前三大的场景不用全排序用堆维护一个大小为 3 的小顶堆更高效。第三类是排序逻辑高度定制比如你需要的不只是排序而是排序过程中的某种副作用或需要对自定义数据结构做原地排序而内置排序 API 满足不了。5.2 内置排序的性能实测什么时候 parallelSort 值得用我做过一组基准测试数据规模从 10 万到 1000 万随机整数分别用Arrays.sort和Arrays.parallelSort跑数据量Arrays.sort 耗时Arrays.parallelSort 耗时10 万约 18ms约 35ms100 万约 160ms约 110ms1000 万约 1.8s约 850ms结论很直观数据量低于 100 万时并行排序的线程调度开销就抵掉了并行收益甚至更慢超过 1000 万后收益明显。如果你的数据经常在百万以下老老实实用Arrays.sort就好。5.3 自定义对象排序的正确姿势对对象排序最容易被忽略的是 Comparator 的写法。很多人会写出这样的代码list.sort((a, b) - a.getAge() - b.getAge());这在小范围数字里没问题但一旦涉及大整数减法可能溢出导致比较结果错误。更推荐的做法是用Integer.compare(a.getAge(), b.getAge())或者直接Comparator.comparing(User::getAge)。后者还能方便地链式追加排序条件list.sort(Comparator.comparing(User::getAge) .thenComparing(User::getName) .reversed());有人会在compare里返回 -1、0、1 之外的任意整数这是允许的但要注意Comparator约定要求符号一致性同时如果compare(a, b) 0应该尽量让compare(b, a) 0否则 TimSort 在最坏情况下可能抛 Comparison method violates its general contract 异常。这个异常我见过太多次了十有八九是 Comparator 写得不对称。6. 排序稳定性、Comparable 与 Comparator 的实战避坑6.1 基本类型的排序没有稳定性问题对象有基本类型数组排序为什么要用不稳定的快排因为对两个值相等的 int 来说谁在前谁在后没有任何业务意义它们的身份不可区分。而对象不同两个对象 equals 相等不代表业务上等价它们的其他字段可能不同排序破坏原有顺序会导致数据错乱。// 反例对用户按年龄排序希望同龄人保持原顺序 users.sort(Comparator.comparing(User::getAge)); // TimSort 保证了这一点而双轴快排不能保证如果你用基本类型数组排序后需要找回原索引Arrays.sort是不行的应该把数组元素包装成(value, originalIndex)对象再排序或者用Integer[]传入 Comparator。6.2 Comparable 实现里的三个约定实现Comparable时有个不成立规范compareTo必须满足自反性、对称性和传递性。传递性是最容易出问题的比如按某个字段排序时如果两个字段值都相等但你返回了非 0 的数字就可能打破传递性。更隐蔽的是在compareTo里做减法比较数值return this.value - other.value值一大就溢出轻则排序错乱重则直接触发 TimSort 的校验异常。6.3 排序中的 null 值处理Comparator遇到 null 元素的处理方式完全取决于你的实现。Comparator.naturalOrder()会直接 NPE但Comparator.nullsFirst(Comparator.naturalOrder())会把 null 排在最前面。业务上我一般建议先过滤掉 null 再做排序因为 null 本身没有业务语义把它掺进排序规则里只会让后续的逻辑判断越来越绕。6.4 稳定排序在实际业务里的经典案例最常见的场景是分页排序。数据库查询时ORDER BY create_time DESC, id DESC已经做了排序到了内存里你又想按某个业务字段再排一次此时如果排序不稳定create_time 的顺序就会乱掉。TimSort 恰好能保证这一点所以list.sort(Comparator.comparing(Order::getStatus))之后同 status 的订单仍然保持之前的时间倒序。这也是我强烈建议所有 Java 开发者记住对象排序由 TimSort 完成、且稳定这个知识点的主要原因。7. 面试怎么回答Java 排序相关的问题7.1 手撕快排的边界条件最容易出错面试让你手写快排最常见的翻车点是递归边界写错if (left right) return;漏掉等于号会导致无限递归分区之后递归调用时写错区间比如拿pivot本身又参与下一轮排序结果反复横跳。我建议写完代码后用长度为 2 和长度为 3 的数组快速在脑子里过一遍比如[3, 1, 2]看每一轮分区后数组是否真正被切开。7.2 归并排序的空间复杂度为什么是 O(n)很多人会答成 O(log n)因为递归栈深度是 log n。但归并排序在合并时需要 O(n) 的临时数组这是整个算法空间复杂度的上限。如果你在面试里主动说出归并排序是稳定排序但需要 O(n) 额外空间就已经比大多数候选人领先了。7.3 高级追问为什么对象排序必须稳定如果面试官继续追问正确的思路是稳定性需求来自业务语义。JDK 源码中TimSort从头到尾没有破坏相等元素的相对顺序这是因为 Java 的Comparator只能表达谁大谁小无法表达谁先谁后一旦排序不稳定调用方没有任何手段恢复原有顺序。而基本类型数组没有这个顾虑所以大胆用快排。7.4 容易被问倒的 TimSort 细节TimSort 里有一个IEEE 推荐的合并规则run1.length run2.length run3.length这类条件用于控制栈上相邻 run 合并的时机避免合并代价失衡。面试不太会问到这么深但如果你能提到 TimSort 会先扫描自然有序片段再合并面试官基本就满意了。要是再能补一句它还会通过二分插入排序减少移动次数这一题基本满分。7.5 常见面试题速查Arrays.sort 的时间复杂度是多少——最好 O(n log n)接近有序时 TimSort 可接近 O(n)。Java 里默认的排序是稳定的吗——对象排序稳定TimSort基本类型排序不稳定DualPivotQuicksort。Collections.sort 和 Arrays.sort 有什么区别——前者作用于 List对象排序底层同样走 TimSort后者直接作用于数组。手写排序中哪些是稳定排序——冒泡、插入、归并、基数、计数是稳定的选择、希尔、快排、堆排不稳定。大数据量排序用什么——业务代码用 Arrays.parallelSort但要先确认数据量级够大。8. 排序算法的工程经验总结与扩展思考踩过几次坑之后我自己的排序使用原则基本固定了优先用 JDK 内置排序永远不要为了炫技手写排序只有当你明确知道内置排序在某个特定数据分布下不满足需求时才考虑自定义。自定义排序的第一个前提是要有性能基准数据而不是拍脑袋决定。比如说排序稳定性我在日志分析系统里按时间戳排序时遇到过sort之后顺序错乱的问题排查到最后发现是有人把对象集合转成数组后用Arrays.sort(Object[])而那个对象数组恰好没有实现Comparable时抛异常换成了自定义Comparator结果这个Comparator只比较了业务字段、没考虑时间戳TimSort 又保证了稳定性才没出大乱子。这件事给我一个教训排序的稳定性在你没意识到的时刻保护着你也只有在破坏它的时候你才会发现它的价值。另一个实际经验是关于并行排序的。ForkJoinPool 是全局共享的如果你在 Web 应用里频繁调用parallelSort处理大数组会占用公共线程池影响其他并行流任务。我遇到过并行流和parallelSort同时使用时互相争抢线程的情况排障花了不少时间。现在我的建议是并行排序要么在独立线程池里跑要么确认没有其他并行任务在竞争否则收益会被调度开销吃掉。这里也顺便提一个排序之外的点如果你在写算法题或数据管道需要频繁对有序集合做插入操作优先考虑TreeSet或PriorityQueue而不是排完序的 ArrayList它们的插入是 O(log n)而 ArrayList 插入是 O(n)。我最后在做代码评审时最常提醒同事的一点是list.sort会修改原 list如果你是函数式编程风格记得先new ArrayList(original)再排序不然下游数据被悄悄改掉很难查。这些细节不算高深但每一个都真实影响过线上系统的表现。排序算法学到最后你会发现它不只是把数组排好这么简单它牵扯到数据分布、内存开销、稳定性约束、并行调度。JDK 这二十多年来的策略演进本质上就是一本活教材小数据用插入排序中等数据用快排大数据可并行对象数据保证稳定接近有序的数据用 TimSort 跑出近似线性时间。理解了这套组合逻辑你再回头去看任何面试题和底层源码都会觉得清晰很多。