arrays.sort()时间复杂度整体为o(n log n)，但底层策略因数组类型而异：基本类型用双轴快排（小数组切插入排序、三向切分、递归深时切归并），对象类型用timsort（识别自然有序段、二分补足、归并合并）。
Arrays.sort() 的时间复杂度不是固定值，而是根据数组类型、长度和数据特征动态选择算法，整体保证 O(n log n)，但不同场景下底层策略差异显著。
基本类型数组：双轴快排为主，带多层兜底
对 int[]、long[] 等基本类型，Java 7 起默认采用双轴快速排序（Dual-Pivot Quicksort）：
- 平均情况下时间复杂度为 O(n log n)，常数因子更小，实际性能优于单轴快排
- 数组长度小于 47 时自动切回插入排序，避免递归开销
- 用五取样法选两个轴（pivot），提升分区均衡性
- 对重复元素多的数组，通过三向切分减少交换次数
- 当递归深度超过阈值（约 2×log₂n）时，切换为归并排序，防止最坏 O(n²) 情况
对象数组：TimSort 自适应混合算法
String[]、Integer[] 等引用类型数组使用 TimSort（Python 也采用），核心是“识别+合并”自然有序段：
- 先扫描数组，提取升序或严格降序的连续片段（run），最小长度为 32
- 对短 run 补齐至最小长度，用二分插入排序优化
- 用归并框架合并有序段，引入 galloping mode 加速比较过程
- 已部分有序时接近 O(n)，完全随机时稳定在 O(n log n)，且保持稳定性
范围排序与自定义比较器不影响复杂度本质
调用 sort(arr, from, to) 或 sort(arr, comparator) 不改变算法选择逻辑：
- 仅作用于指定子区间，时间复杂度按子数组长度计算，仍是 O(k log k)，k = to − from
- Comparator 的 compare() 方法被频繁调用，其内部耗时会叠加到总时间中，需确保实现简洁
- 对基本类型无法直接传 Comparator，必须转为包装类（如 int[] → Integer[]）才能自定义顺序
空间复杂度与稳定性需分情况看待
Arrays.sort() 不返回新数组，原地修改，但并非真正“原地”：
- 基本类型排序：辅助空间 O(log n)，用于递归栈（双轴快排）或临时归并数组
- 对象数组排序：TimSort 需 O(n) 额外空间存储临时合并区
- 稳定性：基本类型排序不保证稳定（快排本质不稳定）；对象数组排序稳定（TimSort 是稳定算法）
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
