Java中Arrays.sort()对基本类型默认采用双轴快速排序，它以两个基准实现三段分区，通过三指针遍历、小数组插入排序、三数取中及递归深度限制等策略提升性能与稳定性。
Java 中 Arrays.sort() 对基本类型（如 int[]、double[]）默认采用的就是双轴快速排序（Dual-Pivot Quicksort），它不是单轴快排的简单升级，而是从分区逻辑、递归策略到边界处理都重新设计的高效实现。理解其原理并掌握调优要点，能帮你写出更稳定、更贴近 JDK 内部行为的排序逻辑。
双轴快排的核心原理：两个基准，三段分区
传统快排选一个 pivot，把数组分成“小于”和“大于”两部分；双轴快排则同时选两个基准 p1 和 p2（通常取首尾元素），并确保 p1 ≤ p2。接着一次性将数组划分为三个区域：
- 左段：所有元素
- 中段：所有元素 ∈ [p1, p2]（含等于）
- 右段：所有元素 > p2
这种三分区减少了比较次数（理论节省约 5%），也更利于 CPU 分支预测和缓存预取。比如数组 [3,5,2,7,1,4,6]，若选 p1=3、p2=6，一次划分后自然形成 [2,1]｜[3,4,5,6]｜[7]，中间段已局部有序，递归负担显著降低。
关键实现细节：三指针遍历与边界处理
标准实现中使用三个指针协同完成一次划分：
立即学习“Java免费学习笔记（深入）”；
- lt：指向左段末尾（
- gt：指向右段开头（> p2 区域的左边界）
-
i：当前扫描位置（从
lt+1开始，到gt-1结束）
遍历时按规则交换：
- 若
a[i] < p1，与a[lt]交换，lt++、i++ - 若
a[i] > p2，与a[gt]交换，gt--（i不增，因换入元素未检查） - 若
p1 ≤ a[i] ≤ p2，仅i++
最后把 p1 放到 lt-1，p2 放到 gt，再递归处理三段。这个过程避免了单轴快排中重复元素扎堆导致的不平衡问题。
性能调优的实用策略
双轴快排虽强，但在极端数据下仍可能退化。实际编码中可结合以下方式提升鲁棒性：
- 小数组改用插入排序：长度 ≤ 47 时直接插入，JDK 就是这么做的，减少递归开销
- 避免最坏输入：对首、中、尾三元素取中位数作为
p1和p2的初始值，抑制已序/逆序场景 - 限制递归深度：当子数组过大且递归过深时，切换为堆排序（JDK 的 “混合排序” 策略）
- 原地操作优先：不额外分配空间，所有交换在原数组完成，降低 GC 压力
与双路快排的区别要分清
别把双轴快排（Dual-Pivot）和双路快排（Two-Way）混淆：
- 双轴：核心是两个基准 + 三段分区，目标是提升平均性能与重复值容忍度，用于 JDK 基本类型排序
-
双路：仍是单基准，但用左右双指针分别收集 ≤pivot 和 ≥pivot 元素，专为大量重复值优化，常用于对象数组（
Comparable[]）
二者解决的问题不同，适用场景也不重叠。写工具类时，若处理 int[] 且关注吞吐量，优先参考双轴逻辑；若排序含大量重复字符串或自定义对象，双路结构更稳妥。
