java面试重在理解排序算法机制与实际应用：arrays.sort(int[])用双轴快排（缓存友好），object[]用稳定timsort；快排最坏o(n²)源于劣质pivot选择，jdk已优化；堆排序因性能差未被arrays.sort采用。
Java面试中问排序算法时间复杂度，不是考你背诵，而是看你是否真理解每种算法的运行机制和边界表现。光说“快排平均 O(n log n)”但讲不清为什么最坏是 O(n²)，或混淆 Arrays.sort() 在不同数据类型下的底层实现，很容易被追问住。
为什么 Arrays.sort(int[]) 是双轴快排，而 Arrays.sort(Object[]) 是 TimSort
这是 Java 7+ 的实际行为，不是理论假设。JDK 对基本类型数组用 DualPivotQuicksort（双轴快排），对引用类型用 Timsort（归并+插入混合），原因很实际：
-
int[]没有对象开销，比较成本低，双轴快排常数小、缓存友好，实测更快 -
Object[]比较可能很重（比如String或自定义类），且需稳定排序（Arrays.sort()对对象必须稳定），Timsort是稳定算法，且对部分有序数据接近 O(n) - 注意：即使你传
Integer[]，也走Timsort，因为它是引用类型，不是int[]
快排最坏 O(n²) 的真实触发条件
不是“数组逆序”就一定最坏，关键看分区策略和 pivot 选择。Java 的 DualPivotQuicksort 做了大量优化：
- 小数组（长度 ≤ 47）直接切进
InsertionSort - 中等数组用双轴 + 随机采样选 pivot，大幅降低退化概率
- 真正触发 O(n²) 的典型场景是：数组含大量重复元素 + 极端 pivot（如每次都选最小值），但 JDK 实现会检测重复并切换到
CountingSort或三路划分 - 手写快排若只取
arr[0]作 pivot，且输入是已排序数组，就会稳定 O(n²)
堆排序在 Java 中几乎不被直接使用
虽然堆排序理论稳定 O(n log n) 且原地，但 JDK 没把它作为任何 Arrays.sort() 的默认实现，原因很实在：
- 实际性能比优化后的快排或 Timsort 差（常数大、缓存不友好）
- 不稳定 —— 不满足
Object[]排序的稳定性要求 - 仅在
PriorityQueue内部用堆逻辑，但那是数据结构需求，不是排序 API - 如果你在面试中写堆排序代码，务必说明建堆 O(n) 和下沉调整 O(log n) 的细节，否则容易被质疑“为什么不说建堆不是 O(n log n)”
public static void heapSort(int[] arr) {
int n = arr.length;
// 建堆：从最后一个非叶子节点开始下沉，O(n)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个取出最大值
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0); // 注意：堆大小变为 i
}
}
真正容易被忽略的是：面试官不关心你能否默写出所有排序代码，而关注你能否根据场景做技术选型——比如“日志按时间戳排序，但 95% 数据已是按天分片有序”，这时候提一句 Timsort 的优势，比背十遍快排复杂度更有说服力。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
