Java内置排序对基本类型采用双轴快排，体现分治思想：分解为三段、递归求解、天然合并；其选快排因原地性优、缓存友好、工程优化成熟；边界处≤47用插入排序，深度超阈值转堆排序，重复元素多时启用三路划分。
Java内置排序算法（如Arrays.sort()）对不同数据类型采用不同策略，但其核心设计大量融入了分治思想——快速排序正是其中关键一环，尤其在基本类型数组排序中起主导作用。
分治如何体现在Java内置排序中
Java的Arrays.sort(int[])等基本类型排序，并非直接调用朴素快排，而是采用“双轴快排”（Dual-Pivot Quicksort），这是对经典分治模型的升级：它选取两个基准值（lowPivot和highPivot），将数组一次划分为三段——小于lowPivot、介于两者之间、大于highPivot。这仍严格遵循分治三步：分解（三路划分）、求解（递归排序三子区间）、合并（天然有序，无需显式操作）。
为什么选快排而非其他分治算法
- 原地性优势：快排仅需O(log n)栈空间（递归深度），不依赖额外数组，比归并排序更省内存，适合JVM堆管理场景；
- 缓存友好：分区过程顺序扫描+局部交换，CPU缓存命中率高，实际运行更快；
- 工程优化成熟：Java 7+中双轴快排结合了插入排序（小数组切换）、随机化pivot、三数取中等策略，有效规避O(n²)最坏情况。
分治边界处理的关键细节
内置实现对分治的终止与降级做了精细控制：
- 当子数组长度 ≤ 47 时，自动切换为插入排序——避免递归开销，利用小规模数据下插入排序的常数优势；
- 递归深度超过阈值（如2·log₂n）时，转为堆排序——防止极端不平衡划分导致栈溢出，保障最坏O(n log n)；
- 对重复元素多的数组，内部会触发“三路快排”逻辑（
counting sort或partitioning into），本质仍是分治的变体。
与归并排序的分治对比
虽然归并排序也是标准分治，但Java对对象数组（Arrays.sort(Object[])）才选用Timsort（混合归并+插入），原因在于：
立即学习“Java免费学习笔记（深入）”；
- 对象比较开销大，归并的稳定性和预判部分有序的能力更实用；
- 基本类型无引用开销，快排的交换效率和内存局部性更胜一筹；
- 分治结构虽同源，但“如何分”（pivot选择 vs mid切分）和“如何治”（原地交换 vs 合并拷贝）决定了适用场景差异。
