双轴快排因分区更均衡、比较与交换次数更少、缓存局部性更好而优于单轴快排；它将数组分为三段（p2），减少递归深度并抑制最坏情况。
Java 中 Arrays.sort() 对基本类型（如 int[]、double[] 等）默认采用的是 Dual-Pivot Quicksort（双轴快排），这是由 Vladimir Yaroslavskiy 在 2009 年提出并被 JDK 7 引入的优化算法。它并非传统单轴快排的简单变种，而是在分区逻辑、递归策略和边界处理上做了系统性改进，兼顾了平均性能、最坏情况抑制和实际运行效率。
为什么用双轴而不是单轴？
传统快排每次选一个基准（pivot），将数组划分为“小于 pivot”和“大于 pivot”两部分。Dual-Pivot 则同时选两个基准——通常记为 p1 和 p2（且保证 p1 ），然后把待排序区间一次性划分为三段：
- 小于
p1的元素 - 介于
p1和p2之间的元素（含等于） - 大于
p2的元素
这种三分区减少了比较次数（理论上比单轴快排节省约 5% 的比较操作），也更利于 CPU 分支预测和缓存局部性。实测表明，在随机数据、部分有序或含大量重复值的场景下，双轴划分的整体交换和比较开销更低。
核心实现策略
JDK 中的 Dual-Pivot Quicksort 不是纯递归实现，而是融合了多种优化手段：
-
自适应 pivot 选择：从首、中、尾等 5 个位置取样，选出第 2 小和第 4 小作为
p1、p2，避免极端偏斜 - 小数组切换插入排序：当子数组长度 ≤ 47（JDK 8 中的阈值）时，直接使用插入排序——因小规模下其常数项更优
-
递归深度控制：若递归过深（可能预示退化），自动切换为堆排序（
Arrays.sort()整体保证 O(n log n) 最坏时间复杂度） - 重复元素优化：对连续相等元素做快速跳过，减少无谓比较
与其它排序的对比
在 JDK 实现中，不同数据类型使用不同算法：
-
int[]、long[]等基本类型 → Dual-Pivot Quicksort -
Object[]（实现了Comparable或传入Comparator）→ Timsort（稳定、适合部分有序） -
Arrays.parallelSort()→ 对大数组分段后并行调用 Dual-Pivot 或 ForkJoin
这意味着：不要假设所有 sort 方法行为一致；基本类型排序快但不稳定，对象排序稳定但稍慢；若需稳定性且操作基本类型，需自行包装为对象或使用其他工具类。
你需要注意的实际细节
尽管 Dual-Pivot Quicksort 表现优秀，但在使用中仍有几点值得注意：
- 它不保证稳定性（相同值的相对顺序可能改变），对基本类型无法规避
- 最坏时间复杂度仍是 O(n²)，但 JDK 的防护机制（如递归深度检测+堆排序兜底）使其极少发生
- 对极小数组（如长度
- 如果发现排序异常慢，优先检查是否触发了降级（如大量重复值 + 不良 pivot 选择），而非算法本身缺陷
它不是银弹，但确实是针对 JVM 实际运行环境（内存访问模式、分支预测、JIT 优化倾向）深度调优的结果。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
