快速排序是最常用的排序算法之一，但在实际应用中，原始实现可能面临性能瓶颈。本文将深入探讨多种优化技巧，结合原理说明和Java示例代码，帮助您显著提升快速排序的性能。
文章目录
前言：为什么需要优化快速排序？
原始快速排序存在两个主要问题：
- 最坏情况时间复杂度O(n²)：当输入数组有序或所有元素相同时
- 递归开销：深度递归可能导致栈溢出
通过以下优化策略，我们可以大幅降低最坏情况发生的概率，并提升整体性能：
⚙️优化技巧1：随机选择基准
原理：
- 问题：固定选择最右元素作为基准，在有序数组上表现极差。
- 解决方案：随机选择基准元素，确保平均性能。
- 效果：将最坏情况概率降到极低。
private static int randomizedPartition(int[] arr, int low, int high) {
// 生成low到high之间的随机索引
int randomIndex = low + (int)(Math.random() * (high - low + 1));
// 将随机元素交换到最右位置
swap(arr, randomIndex, high);
// 使用标准分区方法
return partition(arr, low, high);
}
使用方式：
private static void sort(int[] arr, int low, int high) {
if (low < high) {
// 使用随机分区替代固定分区
int pivotIndex = randomizedPartition(arr, low, high);
sort(arr, low, pivotIndex - 1);
sort(arr, pivotIndex + 1, high);
}
}
⚙️ 优化技巧2：三数取中法
原理：
- 问题：随机选择可能仍选到极值。
- 解决方案：取首、中、尾三元素的中值作为基准。
- 效果：确保基准接近中位数，分区更平衡。
private static int medianOfThree(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
// 对三个元素进行排序
if (arr[low] > arr[mid]) swap(arr, low, mid);
if (arr[low] > arr[high]) swap(arr, low, high);
if (arr[mid] > arr[high]) swap(arr, mid, high);
// 返回中值索引
return mid;
}
private static int medianPartition(int[] arr, int low, int high) {
int medianIndex = medianOfThree(arr, low, high);
swap(arr, medianIndex, high);
return partition(arr, low, high);
}
⚙️ 优化技巧3：小数组切换插入排序
原理：
- 问题：小数组上递归开销大于排序开销。
- 解决方案：当数组大小小于阈值时，切换为插入排序。
- 效果：减少递归深度，提升小数组排序效率。
private static final int INSERTION_THRESHOLD = 16;
private static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
private static void optimizedSort(int[] arr, int low, int high) {
// 小数组使用插入排序
if (high - low < INSERTION_THRESHOLD) {
insertionSort(arr, low, high);
return;
}
// 大数组使用快速排序
int pivotIndex = medianPartition(arr, low, high);
optimizedSort(arr, low, pivotIndex - 1);
optimizedSort(arr, pivotIndex + 1, high);
}
⚙️ 优化技巧4：尾递归优化
原理：
- 问题：深度递归可能导致栈溢出。
- 解决方案：将递归转换为循环，减少递归深度。
- 效果：栈深度从O(n)降至O(log n)。
private static void tailRecursiveSort(int[] arr, int low, int high) {
while (low < high) {
// 分区操作
int pivotIndex = randomizedPartition(arr, low, high);
// 优先处理较短的子数组
if (pivotIndex - low < high - pivotIndex) {
tailRecursiveSort(arr, low, pivotIndex - 1);
low = pivotIndex + 1; // 更新low，循环处理右侧
} else {
tailRecursiveSort(arr, pivotIndex + 1, high);
high = pivotIndex - 1; // 更新high，循环处理左侧
}
}
}
核心机制：
- 优先处理较小分区：通过比较 (pivotIndex - low) 和 (high - pivotIndex)，总是先递归处理较小的子数组分区，将较大的分区转为迭代处理（通过更新 low 或 high 实现）。
- 栈帧复用(JVM 的一种优化技术)：每次递归调用后，当前栈帧可直接复用，无需保留多层栈帧，下面给出代码示例大家就明白了。
// 尾递归优化：通过复用栈帧，递归调用不再累积栈深度。例如计算 1~n 的和：
// 优化后空间复杂度从 O(n) 降为 O(1)
int tailRecur(int n, int res) {
if (n == 0) return res;
return tailRecur(n - 1, res + n); // 尾调用，复用栈帧
}
尾递归优化示意图：
传统递归：
sort(0, 100)
sort(0, 49)
sort(0, 24)
sort(26, 49)
sort(51, 100)
sort(51, 75)
sort(77, 100)
尾递归优化：
sort(0, 100)
sort(0, 49) // 优先处理较短部分
// 循环处理(51, 100)
⚙️ 优化技巧5：双轴快排（Arrays.sort()）
原理：
- 问题：单轴分区每次只能确定一个元素位置。
- 解决方案：使用两个基准将数组分为三部分。
- 效果：减少递归次数，提升缓存性能。
private static void dualPivotQuickSort(int[] arr, int low, int high) {
// 递归终止条件：子数组长度小于等于1
if (low >= high) return;
// 1. 确保pivot1 <= pivot2
// 如果左边基准大于右边基准，交换它们的位置
if (arr[low] > arr[high]) {
swap(arr, low, high);
}
// 选择两个基准值
int pivot1 = arr[low]; // 较小基准
int pivot2 = arr[high]; // 较大基准
// 2. 初始化指针
int left = low + 1; // 左指针：从low+1开始向右扫描
int right = high - 1; // 右指针：从high-1开始向左扫描
int current = low + 1; // 当前指针：用于遍历数组
// 3. 三向分区操作
while (current <= right) {
if (arr[current] < pivot1) {
// 情况1：当前元素小于较小基准
// 将元素交换到左区域
swap(arr, current, left);
left++;
current++;
} else if (arr[current] > pivot2) {
// 情况2：当前元素大于较大基准
// 将元素交换到右区域
swap(arr, current, right);
right--;
// 注意：这里不增加current，因为交换过来的元素需要重新检查
} else {
// 情况3：当前元素在两个基准之间
// 直接留在中间区域，指针后移
current++;
}
}
// 4. 放置基准到正确位置
// 将较小基准放到左区域末尾
swap(arr, low, left - 1);
// 将较大基准放到右区域开头
swap(arr, high, right + 1);
// 5. 递归排序三个子数组
// 左子数组：[low, left-2] (小于pivot1的元素)
dualPivotQuickSort(arr, low, left - 2);
// 中间子数组：[left, right] (pivot1和pivot2之间的元素)
// 只有当中间区域存在元素时才需要排序
if (pivot1 < pivot2) {
dualPivotQuickSort(arr, left, right);
}
// 右子数组：[right+2, high] (大于pivot2的元素)
dualPivotQuickSort(arr, right + 2, high);
}
分区过程关键点
- 指针作用：
- left：标记小于pivot1区域的末尾。
- right：标记大于pivot2区域的开头。
- current：当前遍历位置。
- 元素处理逻辑：
- 元素 < pivot1 → 交换到左区域，left++，current++。
- 元素 > pivot2 → 交换到右区域，right–，current不变。
- pivot1 ≤ 元素 ≤ pivot2 → 留在中间区域，current++。
- 基准放置：
- 分区完成后，pivot1放在left-1位置。
- pivot2放在right+1位置。
扩展问题：可不可以再分一个轴？三轴？四轴？建议无限制的一直分下去吗？大家感兴趣的话可以深入研究下。
总结
实际应用建议：
- 通用场景：使用随机基准+插入排序优化+尾递归优化。
- 性能关键系统：实现双轴快排（如Java的Arrays.sort()）。
- 特定数据：
- 部分有序数据：三数取中法。
- 大量重复元素：考虑三路快速排序。
- 小数据集：直接使用插入排序。
通过合理应用这些优化技巧，您可以使快速排序在各种场景下保持高效稳定的性能，充分发挥其作为最快通用排序算法的潜力。