Java的Arrays.sort()：排序算法与优化分析

前言

在Java中，Arrays.sort()是开发者最常用的排序方法之一。但你是否思考过它的底层实现？本文将基于OpenJDK 17源码，深入分析其使用的排序算法和优化策略，涵盖基本类型与对象数组的不同实现。

一、基本类型数组：双轴快速排序

源码路径：java.util.DualPivotQuicksort

核心算法：
对于int[]、long[]等基本类型，Java使用双轴快速排序（自Java 7引入），其核心思想是：

1. 选择两个轴（Pivot）将数组分为三部分：
   • 左段：< P1
   • 中段：P1 ≤ & ≤ P2
   • 右段：> P2
2. 递归排序三个子段

关键优化策略

1. 小数组插入排序：当数组长度 < 47 时，切换为插入排序

if (length < INSERTION_SORT_THRESHOLD) {
    insertionSort(a, low, high);
    return;
}

2. 五取样法选择轴元素：通过取5个等距位置的元素，用中位数法确定双轴

int e1 = a[k], e5 = a[n]; // 等距取5个点
// ... 中位数计算确保P1<P2

3. 三向切分处理重复元素：分区时采用三向切分，高效处理重复值

while (k <= great) {
    if (ak < pivot1) { // 左段
        swap(a, k, left++);
    } else if (ak > pivot2) { // 右段
        while (a[great] > pivot2 && k < great) great--;
        swap(a, k, great--);
    }
    // 中段无需交换
}

4. 大数组归并排序兜底：当递归深度超过log2(n) × 2时，切换为归并排序避免最坏情况

if (depth == 0) {
    heapSort(a, low, high); // 实际是归并排序
    return;
}

二、对象数组：TimSort

TimSort 是一种自适应的混合排序算法，通过智能识别和扩展数组中的自然有序片段（Run），结合二分插入排序优化小段数据、归并排序平衡合并有序段，并利用Galloping Mode加速归并过程，从而在各类现实数据（尤其是部分有序或包含重复值的数据集）上实现高效稳定的排序，其时间复杂度为O(n log n)，在最佳情况下可接近O(n)。

源码路径：java.util.TimSort
核心算法：
对象数组（如String[]）使用TimSort，这是一种混合排序：

• 归并排序为框架
• 插入排序处理小片段

关键优化策略

1. 分段（Run）检测：扫描数组，将自然有序片段（升序或严格降序）作为基础单元

int runLen = countRunAndMakeAscending(a, lo, hi);

2. 动态最小Run长度：根据数组大小动态计算最小Run长度（16~32），确保后续归并效率。

int minRun = minRunLength(nRemaining);

3. 二分插入排序扩展Run：若自然Run长度不足，用二分插入排序扩展到minRun。

binarySort(a, lo, hi, lo + initRunLen);

4. 归并栈（Stack）管理：维护待归并Run的栈，确保栈内Run长度满足。
   stack[n-2] > stack[n-1] + stack[n]
   stack[n-1] > stack[n]

while (stackSize > 1) {
    int n = stackSize - 2;
    if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
        mergeAt(n); // 归并相邻Run
    }
}

5. 高效内存利用
   • 归并时复制小Run到临时数组（避免大数组复制）
   • Galloping Mode：当一方连续胜出时，指数搜索加速归并

三、性能对比总结

总结

Java的Arrays.sort()通过精妙的算法选择和工程优化，实现了：

• 基本类型：双轴快排为主，插入/归并兜底
• 对象数组：TimSort最大化利用数据特性

这些设计使其在各类场景下保持高性能，成为Java集合框架的基石。