Java排序算法与JDK排序策略深度解析：从八大排序到Arrays.sort

在 Java 圈排查过一个挺诡异的现象线上接口偶尔返回一批顺序不对的名单同一个 List 在 JDK 8 下没问题在 JDK 17 下偶发错乱。最后问题不是出在业务代码而是有人对集合做排序时用了不合规范的 Comparator却一直以为 Arrays.sort 和 Collections.sort 在各自版本里的排序策略没什么本质区别。这个认知坑很常见因为很少有人把“全排序算法实现”和“不同版本 JDK 排序策略”放在一起看。这篇文章想聊透两件事第一手写八大排序算法时哪些必须掌握、哪些容易写错第二JDK 从老版本到新版本对基本类型数组和对象数组分别采用什么排序策略为什么这样设计。内容适合准备 Java 面试的开发者也适合在线上排过排序乱序问题的朋友参考。1. 为什么一个“简单的排序”在 Java 里这么讲究1.1 别把 Arrays.sort 当黑盒大多数业务代码只用Arrays.sort和Collections.sort这没毛病。但很多人忽略了一点这两个方法在不同 JDK 版本里底层走的可能是完全不同的算法。如果你只是“调 API”版本差异影响不大一旦遇到排序稳定性、性能瓶颈或者 Comparator 异常就需要把排序策略拆开看。举个真实例子。有人用Collections.sort排序一个订单列表希望按时间升序时间相同保持原来的插入顺序。代码看起来没问题但上线后发现“相同时间的订单偶尔乱序”。原因是他 Comparator 里只用了一个不稳定的排序入口而且对时间字段的精度处理不当。要解释清楚这类问题必须先搞清楚 JDK 对象排序默认是稳定排序还是不稳定排序。1.2 Java 排序能力演进的三个关键节点Java 排序策略不是一夜之间变成现在这样的主要经历了三个阶段。第一个节点是 JDK 7。这个版本开始Arrays.sort(int[])换成了双轴快速排序Dual-Pivot Quicksort对象数组排序换成了 TimSort。很多老程序员当年就是从“快排 归并”的认知一下子被更新成“双轴快排 TimSort”。第二个节点是 JDK 8。这个版本加入了Arrays.parallelSort大数组可以利用 ForkJoin 公共池并行排序这是 JDK 7 没有的能力。注意它不是默认排序方式需要你主动调用。第三个节点是 JDK 9 到 JDK 17 之间的一系列内部优化。对外 API 没什么大变化但源码内部的阈值、排序混合策略一直在微调。比如DualPivotQuicksort.java这个类名保留了很久但实际上内部不只是“双轴快排”还混入了插入排序、堆排序甚至计数排序。所以面试时别一口咬定“JDK 排序就是某一种算法”那通常不够准确。2. 八大排序算法在 Java 里的完整实现与边界2.1 冒泡、选择、插入三个入门级 O(n²) 算法冒泡排序的核心是相邻比较并交换每轮把最大值冒到末尾。工程上直接用的情况很少但面试里常用来考察“是否理解交换次数和提前退出”。写了一个带swapped标记的版本数组已经有序时可以 O(n) 退出。public static T extends ComparableT void bubbleSort(T[] 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].compareTo(arr[j 1]) 0) { T tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) { break; } } }选择排序每轮挑出未排序部分的最小值放到已排序部分的末尾。它不稳定因为相同元素的相对位置可能被交换。这种“不稳定”在对象排序里经常是致命问题当你看到arr[j].compareTo(arr[minIdx]) 0时要注意即使两个对象 key 相同也可能因为后续的交换改变原始顺序。插入排序是这三个 O(n²) 算法里最实用的一个。它像打扑克牌时理牌把新元素插入到前面已经有序的序列中。对“几乎有序”的数据插入排序甚至能接近 O(n)所以 JDK 的 TimSort 内部也大量依赖二分插入排序。public static T extends ComparableT void insertionSort(T[] arr) { for (int i 1; i arr.length; i) { T cur arr[i]; int j i - 1; while (j 0 arr[j].compareTo(cur) 0) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } }2.2 希尔排序与归并排序分治思想的两个样本希尔排序是插入排序的升级版先按间隔分组做插入排序再逐步缩小间隔直到间隔为 1。我最初学的时候总觉得它“不严谨”但实际跑一下会发现它能把中等规模数组的逆序数快速消灭。间隔序列的选择会影响复杂度所以面试里问“希尔排序时间复杂度是多少”标准答案往往是“取决于增量序列”。public static T extends ComparableT void shellSort(T[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { T cur arr[i]; int j i; while (j - gap 0 arr[j - gap].compareTo(cur) 0) { arr[j] arr[j - gap]; j - gap; } arr[j] cur; } } }归并排序是典型的分治算法把数组分成两半分别排序再合并。它稳定、最坏也是 O(n log n)但需要额外 O(n) 空间。JDK 对象排序之所以长期倾向归并排序核心原因就是“稳定”。public static T extends ComparableT void mergeSort(T[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private static T extends ComparableT void merge(T[] arr, int l, int m, int r) { T[] tmp (T[]) new Comparable[r - l 1]; int i l; int j m 1; int k 0; while (i m j r) { if (arr[i].compareTo(arr[j]) 0) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i m) { tmp[k] arr[i]; } while (j r) { tmp[k] arr[j]; } System.arraycopy(tmp, 0, arr, l, tmp.length); }写这段代码时有三个容易踩的坑一是mid计算用(left right) 1避免大数组left right溢出二是arr[i].compareTo(arr[j]) 0必须取小于等于这样能保证稳定性三是临时数组类型只能用Comparable[]强转这是泛型数组无法直接创建的妥协。2.3 快速排序与堆排序生产环境最常见快速排序在平均情况下非常快是 JDK 对基本类型排序的老牌选择。手写快排时最容易出问题的是边界条件和递归深度。我习惯用单轴双边扫描pivot 选择中间值尽量避免有序数组下最坏的 O(n²) 情况。public static T extends ComparableT void quickSort(T[] arr, int left, int right) { if (left right) { return; } T pivot arr[left (right - left) / 2]; int i left; int j right; while (i j) { while (arr[i].compareTo(pivot) 0) { i; } while (arr[j].compareTo(pivot) 0) { j--; } if (i j) { T tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); }这段代码有个细节递归边界是[left, j]和[i, right]不是[left, i-1]和[i, right]。如果分界写错很容易栈溢出或漏排元素。另一个问题是手写快排对大规模逆序数组不友好递归深度可能逼近数组长度我正在后面的“问题排查”部分专门展开。堆排序是“利用完全二叉树结构选择最大值”的排序。它的常数列比不过快排但最坏也是 O(n log n)且空间 O(1)。JDK 的双轴快排实现里也保留了“递归过深时切到堆排序”的兜底策略。public static T extends ComparableT void heapSort(T[] 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--) { T tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } } private static T extends ComparableT void heapify(T[] arr, int n, int i) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n arr[l].compareTo(arr[largest]) 0) { largest l; } if (r n arr[r].compareTo(arr[largest]) 0) { largest r; } if (largest ! i) { T tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); } }2.4 计数、基数、桶排序线性排序家族的适用边界计数排序严格说不是比较排序它把元素作为数组下标来计数所以能做到 O(nk)。它适用于“取值范围有限”的整数场景比如成绩排序、年龄排序。如果取值范围是Integer.MIN_VALUE到MAX_VALUE强行计数排序直接 OOM这是新手最容易踩的坑。public static void countingSort(int[] arr) { int max arr[0]; int min arr[0]; for (int v : arr) { max Math.max(max, v); min Math.min(min, v); } int[] count new int[max - min 1]; for (int v : arr) { count[v - min]; } int k 0; for (int i 0; i count.length; i) { while (count[i]-- 0) { arr[k] i min; } } }基数排序按“位”依次排序常数时间复杂度是 O(d(nk))d 是位数。它适合整数和定长字符串但不适合 double 这类复杂结构。桶排序的思想是把数据均匀分到多个桶桶内再用其他算法排序。注意桶排序不是计数排序别把两者混为一谈。但在某些极限实现里桶内元素比较少时退化为直接插入排序效果也很好。线性排序家族虽然酷炫但实际生产中用得最多的是“对有限枚举值做分组”而不是通用排序。JDK 内部也只在遇到 byte、char 这类小范围数据时才考虑计数排序其余情况还是靠比较排序。3. 不同版本 JDK 排序策略内幕从源码视角逐个拆3.1 基本类型数组的排序双轴快排只是门面在 JDK 6 之前Arrays.sort(int[])底层是一个经过调优的传统单轴快速排序。到了 JDK 7Oracle 引入了 Vladimir Yaroslavskiy 写的双轴快排实现类名就叫DualPivotQuicksort。很多文章说“JDK 7 以后基本类型排序就是双轴快排”这个说法不算错但并不完整。打开 JDK 8 的DualPivotQuicksort.java会发现它内部会根据数组长度走不同分支小于 47 直接插入排序小于 286 走双轴快排更长时还要看数据是否接近有序再决定是继续快排还是改用归并思想。所以准确地说JDK 对基本类型数组的排序是一个“混合排序器”双轴快排只是核心策略之一。为什么基本类型数组不直接沿用归并排序因为基本类型没有“稳定性”需求。int的 3 和另一个int的 3 没有任何区别不需要维持原先相对顺序。相比之下快速排序的常数小、内存占用低在大多数场景下吞吐更高。3.2 对象类型数组的排序为什么一定是稳定排序对象数组排序就完全不同了。假设你先按用户等级排序再按注册时间排序如果第二次排序不是稳定的第一次排序的结果会被打乱最终列表的“等级一致时注册时间升序”就实现不了。所以 Java 对对象排序长期坚持稳定策略。JDK 7 之前用的是普通归并排序JDK 7 开始替换为 TimSort。TimSort 结合了归并排序和插入排序先找出数据中已经有序的“run”片段再把不够长的 run 用二分插入排序扩展最后把多个 run 按照一定规则合并。对随机数组它接近归并排序对部分有序数组它能达到 O(n)。JDK 源码里有两个版本TimSort用于带 Comparator 的对象排序ComparableTimSort用于自然排序。两者核心逻辑几乎一致只是后者直接调用元素的compareTo。面试里说“TimSort run 识别 二分插入 归并”基本能拿到高分。3.3 Collections.sort 与 List.sort同一个结果两条不同的路很多人不知道JDK 8 的Collections.sort其实很薄内部直接调用list.sort(null)。而ArrayList重写了sort直接对elementData数组调用Arrays.sort。LinkedList没重写所以走的是List默认方法先toArray()变成数组排序完成后又逐个写回链表。这就导致一个有意思的结论对LinkedList排序无论如何都要先把元素复制到数组再复制回链表。所以如果你的 List 需要频繁排序ArrayList的隐蔽优势比LinkedList大得多。老版本 JDK 里还有一个“后门”系统属性java.util.Arrays.useLegacyMergeSorttrue设置后可以切回旧版归并排序。这个属性在 JDK 7/8 里还能用后来的版本逐渐把旧实现清理掉了已经没人建议用它因为它一开就失去了 TimSort 针对部分有序数据优化能力。3.4 parallelSort并行排序的阈值没那么简单Arrays.parallelSort从 JDK 8 开始提供它不会自动替代普通排序必须显式调用。它内部使用ForkJoinPool.commonPool()来并行执行排序任务。源码里有个很关键常量MIN_ARRAY_SORT_GRAN 1 13也就是 8192。这个常量的含义是当递归划分出的子数组长度小于 8192 时不再细分任务而是直接调用顺序排序。所以如果数组只有几千个元素parallelSort 实际上就是顺序排序不会并行。数组越大并行拆分带来的收益才越明显。但别以为大数组用 parallelSort 就一定能更快。并行排序需要额外的任务调度和临时空间而且 ForkJoin 公共池是全局共享的如果并行流也在同时大量使用它线程资源会被争抢。我在后面“常见问题”里会专门说这个坑。3.5 不同版本排序策略速查表JDK 版本基本类型数组 Arrays.sort对象数组 Arrays.sortCollections.sort并行排序JDK 6 及以前调优单轴快速排序普通归并排序走数组排序归并思想无JDK 7双轴快速排序混合策略TimSort / ComparableTimSort默认 TimSort无JDK 8双轴快速排序混合策略TimSort / ComparableTimSort调用 List.sort最终 Arrays.sort新增 parallelSortJDK 9-17策略延续内部阈值微调TimSort 延续同 JDK 8parallelSort 延续面试时如果能说出这张表已经领先不少人。更关键的是知道“基本类型无稳定性需求所以走快排对象类型有稳定性需求所以走稳定归并/TimSort”这才是 JDK 排序策略设计的核心逻辑。4. 复杂度、稳定性与选型一张表看清全排序算法4.1 排序算法指标速查表排序算法平均时间最坏时间最好时间空间稳定性冒泡排序O(n²)O(n²)O(n)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(n)O(1)稳定希尔排序O(n log n)O(n²)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(nk)O(nk)O(nk)O(k)稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定桶排序O(nk)O(n²)O(nk)O(n)稳定这张表里最容易记混的是希尔排序。它的最坏情况不是严格 O(n log n)而是取决于增量序列常见的gap n/2实现最坏可能是 O(n²)。面试被问到可以答“复杂度和增量序列强相关工程实现里没有一个统一公式”。4.2 稳定性为什么重要两次排序还原需求的例子稳定性不是说“排序结果稳定”而是“相等元素的相对顺序在排序前后保持一致”。最常见需求是先按订单状态分组再按创建时间排序。如果排序不稳定第一次按状态排好的内部顺序会被第二次按时间排序打乱最终同一状态下的订单时间顺序不对。用代码验证稳定性很方便给每个元素加一个原始序号排序后检查相同 key 的序号是否递增。比如定义一个Item包含key和seq先按key排序再校验seq顺序。插入排序和归并排序能通过这个测试快速排序通常不能因为分区交换过程中可能跨过相等元素。4.3 数据特征决定策略而不是“哪个算法快”“哪个排序最快”本质上是个伪命题因为最快取决于数据分布。随机打乱的十万个整数快速排序通常比归并排序略快但如果数据已经高度有序插入排序和 TimSort 能把时间复杂度降到接近 O(n)如果数据是取值范围很小的整数计数排序几行代码就能碾压所有比较排序。所以选型时我一般先问三个问题数据量多大是否接近有序是否需要保证稳定性数据量小于几千直接用 JDK 自带排序就行手写排序算法更多是为了理解原理生产环境不要轻易造轮子。JDK 的排序实现经过了几十年的调优、阈值优化和 bug 修复自己写一个通用排序想超过它难度远比你想象的大。5. 手写全排序工具类的工程化姿势5.1 统一接口与策略封装如果你想把上面这些算法整理成一个可测试的工具类第一步是定义一个统一接口避免每个算法都暴露不同的参数。接口可以直接用泛型这样既能测Integer[]也能测自定义对象。public interface SortStrategyT extends ComparableT { void sort(T[] arr); }每个算法类实现这个接口。对于归并、快排这种需要左右边界的算法内部可以重载一个私有方法公共接口只接收数组。策略模式的好处是测试代码可以统一写成“传入数组执行 sort再看结果”不需要为每种算法单独写一套调用。还有一点要注意接口的方法名如果用sort(T[] arr)那它和Arrays.sort看起来很像容易混淆。我建议在工具类里明确注释“这是原地排序不是返回新数组”。原地排序和复制排序是两种完全不同的语义面试和项目里经常因为这一点闹出数据被修改的 bug。5.2 测试用例怎么写随机、有序、逆序、重复、大数据测试排序算法不能只用一组随机数。我通常固定跑六类测试数据随机数、升序、降序、大量重复值、少量重复值、超大数组。升序和降序能暴露快排在极端情况下的递归深度问题重复值能暴露不稳定排序。验证算法正确性的标准方法先复制一份数组用Arrays.sort作为基准答案再用手写算法排序排序后逐位比较。这样比自己肉眼判断准确得多。稳定性的验证同样要写一个带序号的对象数组否则你很难发现某个排序悄悄交换了两个“相同”元素的位置。大数组测试还需要关注耗时而不是只跑一次。我建议在同一台机器上至少跑三轮取中位数因为 JIT 预热、GC 时间都会影响毫秒级数据。我之前见过有人拿一次 GC 导致的数据写性能报告结论完全失真。5.3 各算法在不同 JDK 下的表现量级对比与结论我拿随机生成的十万个 Integer 做过简单对比机器不同数字会有浮动但量级关系基本稳定插入排序和冒泡排序在十万数据下是“肉眼可见的慢”归并、快排、堆排序能在一二十毫秒级别完成JDK 的Arrays.sort通常最快因为它混合了插入排序、双轴快排和堆排序的各自优势。这个结果不意外。手写归并排序需要额外申请临时数组手写快排分区也未必能拿到最优枢纽元。JDK 的排序实现针对“随机数据、有序数据、重复数据、超大数组”都做了阈值判断每类数据都能选到合适的策略。所以我的结论是能用 JDK 自带排序就别手动造轮子手写全排序算法主要是为了学习和应对面试。5.4 手写排序中常见的边界错误清单我见过太多排序代码栽在边界上。最典型的是for循环写成i n导致数组越界其次是归并排序mid计算用(left right) / 2当数组很大时溢出再就是快排递归结束条件写错导致无限递归或漏排。另一个隐蔽错误是泛型数组排序代码里使用new T[]这是非法的。Java 的泛型在运行时会被擦除数组创建必须依赖Comparable[]强转或者调用方传入数组类型。写工具类时可以在每个排序方法里不做数组创建只在归并排序临时数组那里用强转问题可控。最后提醒一个工程化习惯排序方法里尽量少做日志打印。compareTo是高频调用排序过程中打日志会把性能拖垮。要排查时应该先把排序前后的数组打出来而不是在比较器里 print。6. 常见报错与实战排查排序里的八宗罪6.1 “Comparison method violates its general contract”这个异常是 JDK 7 引入 TimSort 之后非常著名的一个坑。出现原因很简单你的 Comparator 不满足“可传递性”TimSort 在合并归并片段时发现结果无法解释就抛出这个异常来保护数据。一个常见反例是有人这么写list.sort((a, b) - a.age b.age ? 1 : -1);这个比较器永远不返回 0而且当两个 age 相同时它既可能认为 a 大于 b也可能认为 b 大于 a完全违反对称性。在 JDK 6 的老归并排序里这种代码可能“碰巧”不报错只是结果错乱在 JDK 7 的 TimSort 里会被直接拦截。排查思路很简单先检查比较器是否对相同值返回 0再检查是否满足传递性。不要跟异常较劲比较器写规范才是根治。6.2 Comparator 意外修改被排序对象排序过程不会自动修改被排序对象的属性但如果你的 Comparator 在比较时顺手改了对象的字段、缓存或者延迟加载字段就会让排序行为变得不可预测。比如有人在 compare 方法里调用了student.getScore()而这个 getter 内部做了 lazy compute第一次调用和第二次调用返回不同的值。这种 bug 比 StackOverflow 更隐蔽因为它在小数据量下可能一切正常大数据量下偶发乱序。排查经验是Comparator 必须是无副作用函数不能修改任何对象状态不能依赖外部可变状态。如果需要按多个字段排序应该把这些字段的访问逻辑剥离出来做成独立、稳定的 key 提取函数。6.3 递归快排栈溢出换 pivot 还是换算法手写递归快排在十万级逆序数组上很容易栈溢出因为每次分区只排掉一个元素递归深度变成 O(n)。这时候你可能会想“换个 pivot 随机化就行了”这能缓解但不能根治。最坏情况下随机 pivot 也可能连续选中极端值。更稳妥的方案是在小规模子数组切换到插入排序并限制递归深度一旦超过某个阈值就用堆排序兜底。JDK 的双轴快排就是这么设计的。轮子看起来复杂但正是这些细节才让工业级排序能扛住线上数据。6.4 parallelSort 为什么越排越慢Arrays.parallelSort在数据量不够大时反而更慢。它要先把数组划分成多个子任务通过 ForkJoin 线程池调度排序完还要归并结果。这些额外开销对小数组来说完全抵消不了并行收益。我通常至少到百万级数据才考虑并行排序并且会跟普通Arrays.sort做一个对比测试。还容易忽视的是 ForkJoin 公共池被全局共享。如果应用里同时有多个 parallelStream 在跑这些任务会挤在一起抢线程parallelSort 的耗时就会飙升。线上真要使用并行排序建议先看看公共池的并行度并用独立线程池替代。6.5 面试与线上场景的排序边界排序算法面试题里经常出现“数组长度为零”“数组只有一个元素”“元素全是最大值”“Comparator 返回 0”这些边界。不要觉得这是废话空数组和单元素数组在递归排序里最容易漏判断。还有用计数排序处理包含Integer.MIN_VALUE的数组时直接建数组会 OOM必须先做偏移或者改用其他算法。线上场景我还有一条建议如果排序后需要显示“原始顺序兜底”可以在数据里加一个自增序号字段作为排序的次要 key。这样即使某个业务字段相等结果也有确定性后续排查会省很多力气。我在实际排过很多乱序问题后最大的体会是先搞清楚 JDK 在哪个版本、对哪类数据、用哪种排序策略再回头查业务比较器往往比盲目加日志和优化循环要快得多。手写排序算法可以帮你建立对复杂度、稳定性、递归边界的直觉但真正上线那一刻请对 JDK 的排序实现保持敬畏。