问题

Arrays.sort是使用什么排序算法实现的？

答案

核心结论

Arrays.sort 根据数据类型使用不同的排序算法：

数据类型	排序算法	时间复杂度	稳定性
基本类型（int、long等）	双轴快排（Dual-Pivot Quicksort）	O(n log n)	❌ 不稳定
对象类型（Object[]）	TimSort	O(n log n)	✅ 稳定

1. 基本类型：双轴快排

算法特点

传统快排使用单个pivot分区，双轴快排使用两个pivot：

// 传统快排（单pivot）
[...小于pivot...] [pivot] [...大于pivot...]

// 双轴快排（双pivot）
[...小于pivot1...] [pivot1] [...介于中间...] [pivot2] [...大于pivot2...]

源码分析

// java.util.DualPivotQuicksort
public static void sort(int[] a, int left, int right) {
    // 1. 小数组优化：长度<47使用插入排序
    if (right - left < INSERTION_SORT_THRESHOLD) {
        insertionSort(a, left, right);
        return;
    }

    // 2. 选择两个pivot
    int third = (right - left) / 3;
    int pivot1 = a[left + third];
    int pivot2 = a[right - third];

    // 确保pivot1 <= pivot2
    if (pivot1 > pivot2) {
        swap(a, left + third, right - third);
        pivot1 = a[left + third];
        pivot2 = a[right - third];
    }

    // 3. 三路分区
    int less = left;
    int great = right;

    // 分区过程（简化）
    for (int k = left; k <= great; k++) {
        if (a[k] < pivot1) {
            swap(a, k, less++);
        } else if (a[k] > pivot2) {
            swap(a, k, great--);
        }
    }

    // 4. 递归排序三个区间
    sort(a, left, less - 1);
    sort(a, less, great);
    sort(a, great + 1, right);
}

优化策略

1. 小数组优化

// 长度 < 47：插入排序
if (length < 47) {
    insertionSort(a, left, right);
    return;
}

原因：插入排序在小数组上更快（无递归开销、缓存友好）。

2. 递归深度限制

// 递归过深时切换为堆排序
if (depth > MAX_DEPTH) {
    heapSort(a, left, right);
    return;
}

原因：避免最坏情况O(n²)，保证O(n log n)。

3. pivot选择策略

// 使用"三分之一"位置选择pivot
int third = (right - left) / 3;
int pivot1 = a[left + third];
int pivot2 = a[right - third];

原因：比选择首尾元素更抗退化。

性能对比

// JMH基准测试（排序100万个随机整数）

@Benchmark
public void testDualPivotQuicksort() {
    int[] arr = generateRandomArray(1_000_000);
    Arrays.sort(arr);
}

@Benchmark
public void testSinglePivotQuicksort() {
    int[] arr = generateRandomArray(1_000_000);
    quicksort(arr, 0, arr.length - 1); // 传统快排
}

// 结果
// testDualPivotQuicksort:  40 ms/op
// testSinglePivotQuicksort: 55 ms/op  ← 慢38%

2. 对象类型：TimSort

算法特点

TimSort是归并排序和插入排序的混合算法，专门优化部分有序数据。

// 对象数组排序
String[] arr = {"banana", "apple", "orange"};
Arrays.sort(arr); // 使用TimSort

核心思想

1. 识别已排序的连续子序列（run）
2. 如果run太短，使用插入排序扩展
3. 将run存入栈中
4. 按特定规则合并相邻的run

源码分析

// java.util.TimSort
public static <T> void sort(T[] a, Comparator<? super T> c) {
    int lo = 0;
    int hi = a.length;
    int nRemaining = hi - lo;

    // 1. 小数组优化：长度<32使用二分插入排序
    if (nRemaining < MIN_MERGE) {
        binarySort(a, lo, hi, c);
        return;
    }

    // 2. 计算最小run长度
    int minRun = minRunLength(nRemaining);

    // 3. 识别并合并run
    do {
        // 找到升序或降序的run
        int runLen = countRunAndMakeAscending(a, lo, hi, c);

        // run太短则用插入排序扩展到minRun
        if (runLen < minRun) {
            int force = Math.min(minRun, nRemaining);
            binarySort(a, lo, lo + force, c);
            runLen = force;
        }

        // 将run压入栈
        ts.pushRun(lo, runLen);

        // 合并run（保持栈的平衡）
        ts.mergeCollapse();

        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);

    // 4. 最终合并
    ts.mergeForceCollapse();
}

为什么对象用TimSort？

1. 稳定性要求：对象排序需要保持相等元素的原始顺序
2. 部分有序优化：实际业务数据常常部分有序
3. 比较开销大：对象比较涉及方法调用，减少比较次数更重要

性能特性

// 最好情况：O(n) - 完全有序
Integer[] sorted = {1, 2, 3, 4, 5, ..., 1000000};
Arrays.sort(sorted); // 极快，只需遍历一遍

// 最坏情况：O(n log n) - 完全随机
Integer[] random = generateRandomArray(1000000);
Arrays.sort(random); // 仍然高效

// 实际场景：部分有序
Integer[] partialSorted = {1, 2, 3, ..., 1000, 999, 998, ..., 500};
Arrays.sort(partialSorted); // 比完全随机快很多

3. 并行排序：parallelSort

使用方式

int[] arr = new int[10_000_000];
// 填充数据...

// 单线程排序
Arrays.sort(arr);

// 多线程并行排序
Arrays.parallelSort(arr);

实现原理

// 基于ForkJoinPool的分治排序
public static void parallelSort(int[] a) {
    int n = a.length;

    // 数据量小时用串行排序
    if (n <= MIN_ARRAY_SORT_GRAN) {
        DualPivotQuicksort.sort(a, 0, n - 1);
        return;
    }

    // 分解任务
    ForkJoinPool.commonPool().invoke(
        new SortTask(a, 0, n)
    );
}

static final class SortTask extends RecursiveAction {
    public void compute() {
        if (right - left < THRESHOLD) {
            // 小任务直接排序
            DualPivotQuicksort.sort(a, left, right);
        } else {
            // 分割任务
            int mid = (left + right) >>> 1;
            invokeAll(
                new SortTask(a, left, mid),
                new SortTask(a, mid, right)
            );
            // 合并结果
            merge(a, left, mid, right);
        }
    }
}

性能对比

// JMH测试（1000万整数，8核CPU）

@Benchmark
public void testSort() {
    int[] arr = generateRandomArray(10_000_000);
    Arrays.sort(arr);
}

@Benchmark
public void testParallelSort() {
    int[] arr = generateRandomArray(10_000_000);
    Arrays.parallelSort(arr);
}

// 结果
// testSort:          650 ms/op
// testParallelSort:  180 ms/op  ← 快3.6倍

注意：数据量小时（<10000），并行排序反而更慢。

4. 版本演进

Java版本	基本类型	对象类型
Java 6及之前	快速排序	归并排序
Java 7+	双轴快排	TimSort
Java 8+	双轴快排 + parallelSort	TimSort + parallelSort

5. 自定义排序

Comparator排序

// 对象数组 + 自定义比较器
String[] arr = {"banana", "apple", "orange"};

// 按长度排序
Arrays.sort(arr, Comparator.comparingInt(String::length));

// 多条件排序
Arrays.sort(arr,
    Comparator.comparingInt(String::length)
              .thenComparing(String::compareTo)
);

Comparable接口

public class Student implements Comparable<Student> {
    private String name;
    private int score;

    @Override
    public int compareTo(Student other) {
        // 按分数降序
        return Integer.compare(other.score, this.score);
    }
}

Student[] students = {...};
Arrays.sort(students); // 使用compareTo

6. 稳定性问题

// 基本类型：不稳定
int[] arr = {3, 2, 3, 1};
Arrays.sort(arr); // [1, 2, 3, 3] ← 两个3的相对顺序可能改变

// 对象类型：稳定
class Item {
    int value;
    int index; // 原始索引
}

Item[] items = {
    new Item(3, 0),
    new Item(2, 1),
    new Item(3, 2)
};

Arrays.sort(items, Comparator.comparingInt(i -> i.value));
// [Item(2,1), Item(3,0), Item(3,2)] ← 相等元素保持原顺序

7. 性能建议

// ✅ 优化1：基本类型数组优于包装类型
int[] arr1 = new int[1000000]; // 快
Integer[] arr2 = new Integer[1000000]; // 慢（装箱、比较开销）

// ✅ 优化2：大数据量使用parallelSort
if (arr.length > 10000) {
    Arrays.parallelSort(arr);
} else {
    Arrays.sort(arr);
}

// ✅ 优化3：避免重复排序
Arrays.sort(arr); // 第一次排序
// ... 不修改arr
Arrays.sort(arr); // ❌ 浪费，已经有序

// ✅ 优化4：部分排序使用PriorityQueue
// 只需要Top K个元素时
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int num : arr) {
    pq.offer(num);
    if (pq.size() > k) pq.poll();
}

8. 实战案例

// 场景：对用户列表排序
List<User> users = userService.getAllUsers();

// ❌ 错误：转数组排序再转回List（多次复制）
User[] arr = users.toArray(new User[0]);
Arrays.sort(arr, Comparator.comparing(User::getAge));
users = Arrays.asList(arr);

// ✅ 正确：直接用List.sort
users.sort(Comparator.comparing(User::getAge)
                     .thenComparing(User::getName));

// ✅ 或使用Stream（Java 8+）
List<User> sorted = users.stream()
    .sorted(Comparator.comparing(User::getAge))
    .collect(Collectors.toList());

答题总结

Arrays.sort 针对不同数据类型使用不同算法：

• 基本类型：双轴快排（DualPivotQuicksort），不稳定，平均O(n log n)，针对小数组、递归深度等有多重优化
• 对象类型：TimSort（归并+插入混合），稳定，特别适合部分有序数据
• 并行排序：parallelSort 基于ForkJoinPool，大数据量下性能提升明显

Java 7开始引入双轴快排和TimSort，相比传统算法性能提升30-50%。实际使用中，优先选择基本类型数组，大数据量考虑并行排序。