在Java开发中，数组排序是非常基础且常用的操作，JDK提供的Arrays.sort方法是最便捷的排序工具，它针对不同类型的数组采用了不同的底层实现，其中基本类型数组的排序核心就是双轴快速排序。
Java中数组排序的常用方式
Java中实现数组排序主要有两种方式，一种是手动编写排序逻辑，比如冒泡排序、选择排序等基础算法，另一种是直接使用JDK内置的Arrays.sort方法。手动实现的排序算法通常仅用于学习场景，实际开发中几乎都会优先选择Arrays.sort，因为它的实现经过充分优化，性能更可靠。
我们来看一个最基础的Arrays.sort使用示例，对int类型数组进行排序：
import java.util.Arrays;
public class ArraySortDemo {
public static void main(String[] args) {
int[] numArray = {5, 2, 8, 1, 9, 3};
// 调用Arrays.sort对数组进行升序排序
Arrays.sort(numArray);
// 输出排序后的数组
System.out.println(Arrays.toString(numArray));
}
}
上述代码执行后，输出的结果是[1, 2, 3, 5, 8, 9]，可以看到Arrays.sort默认按照升序对数组完成了排序。
Arrays.sort的底层实现分类
Arrays.sort并不是对所有类型的数组都采用同一种排序算法，JDK根据数组元素类型的不同，做了明确的区分：
- 对于
byte、short、int、long、float、double这些基本类型的数组，底层使用的是双轴快速排序（Dual-Pivot Quicksort）。 - 对于
char类型的数组，底层使用的是计数排序结合的优化方案。 - 对于对象数组（引用类型数组），底层使用的是TimSort，这是一种归并排序和插入排序结合的混合排序算法，并且是稳定的排序。
我们本次重点关注的双轴快速排序，就是基本类型数组排序的核心实现。
双轴快速排序的核心原理
传统的快速排序是单轴快速排序，它每次选择一个基准元素（pivot），将数组分成两部分，左边部分的元素都小于等于基准，右边部分的元素都大于等于基准，然后递归处理左右两部分。而双轴快速排序则选择了两个基准元素pivot1和pivot2，并且要求pivot1 <= pivot2，之后将数组分成三个部分：
- 小于等于
pivot1的元素，放在左区间。 - 大于
pivot1且小于等于pivot2的元素，放在中间区间。 - 大于
pivot2的元素，放在右区间。
之后递归处理这三个区间，相比单轴快速排序，双轴快速排序每次递归可以处理更多的元素，减少了递归的次数，从而提升了整体性能。
双轴快速排序的执行流程
双轴快速排序的大致执行步骤如下：
- 先判断待排序数组的长度，如果长度小于某个阈值（JDK中默认是47），则直接使用插入排序完成排序，因为小数组场景下插入排序的性能更好。
- 如果数组长度达到阈值，选择两个 pivot，通常选择数组最左端和最右端的元素作为
pivot1和pivot2，如果pivot1 > pivot2则交换两者，保证pivot1 <= pivot2。 - 定义三个指针，左指针指向
pivot1的下一个位置，右指针指向pivot2的前一个位置，中间指针从左指针开始向右移动。 - 遍历数组，根据中间指针指向的元素和两个pivot的大小关系，将元素交换到对应的区间。
- 当中间指针超过右指针时，将
pivot1和pivot2放到正确的位置，此时数组被分成三个有序的区间。 - 递归对三个区间分别执行上述双轴快速排序流程。
双轴快速排序的性能优势
双轴快速排序相比传统单轴快速排序的优势主要体现在以下方面：
| 对比维度 | 单轴快速排序 | 双轴快速排序 |
|---|---|---|
| 每次递归分区数 | 2个 | 3个 |
| 递归深度 | 更高 | 更低 |
| 平均比较次数 | 更多 | 更少 |
| 最坏时间复杂度 | O(n²) | O(n²)，但出现概率更低 |
| 平均时间复杂度 | O(n log n) | O(n log n)，常数更小 |
JDK中的双轴快速排序实现还做了很多细节优化，比如针对重复元素多的场景做了特殊处理，避免最坏情况的出现，因此在实际使用中性能表现非常稳定。
双轴快速排序的简单实现示例
为了更直观地理解双轴快速排序的逻辑，我们可以参考其原理实现一个简化版本的双轴快速排序：
public class DualPivotQuickSortDemo {
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
dualPivotQuickSort(arr, 0, arr.length - 1);
}
private static void dualPivotQuickSort(int[] arr, int left, int right) {
// 小数组使用插入排序
if (right - left < 47) {
insertionSort(arr, left, right);
return;
}
// 保证pivot1 <= pivot2
if (arr[left] > arr[right]) {
swap(arr, left, right);
}
int pivot1 = arr[left];
int pivot2 = arr[right];
// 定义三个指针
int less = left + 1;
int great = right - 1;
int k = less;
while (k <= great) {
if (arr[k] < pivot1) {
// 元素小于pivot1，放到左区间
swap(arr, k, less);
less++;
} else if (arr[k] > pivot2) {
// 元素大于pivot2，放到右区间
while (arr[great] > pivot2 && k < great) {
great--;
}
swap(arr, k, great);
great--;
if (arr[k] < pivot1) {
swap(arr, k, less);
less++;
}
}
k++;
}
// 将pivot1和pivot2放到正确位置
less--;
great++;
swap(arr, left, less);
swap(arr, right, great);
// 递归处理三个区间
dualPivotQuickSort(arr, left, less - 1);
dualPivotQuickSort(arr, less + 1, great - 1);
dualPivotQuickSort(arr, great + 1, right);
}
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] testArr = {3, 7, 1, 9, 2, 8, 5, 4, 6};
sort(testArr);
for (int num : testArr) {
System.out.print(num + " ");
}
}
}
上述代码实现了一个简化版的双轴快速排序，运行后会输出排序后的数组1 2 3 4 5 6 7 8 9，可以帮助理解双轴快速排序的核心分区逻辑。
总结
Java中的Arrays.sort方法针对基本类型数组的排序底层采用的是双轴快速排序，这是一种对传统快速排序的优化方案，通过选择两个基准元素将数组分成三个区间递归处理，减少了递归深度和比较次数，在多数场景下都能获得不错的性能表现。了解其底层原理，有助于我们更合理地使用Java的排序工具，也能在需要自定义排序逻辑时提供参考。
JavaArrays.sort双轴快速排序数组排序修改时间：2026-06-23 10:12:43