快速排序（Quick Sort）由 Tony Hoare 于 1959 年提出，是计算机科学史上最具影响力的算法之一。它以平均 O(n log n) 的时间复杂度、原地排序的空间优势，成为工业界和竞赛中最常用的排序算法。本文将用 Java 完整实现快速排序，深入讲解其核心——双指针分区算法，并对比 Lomuto 与 Hoare 两种经典分区方案，同时给出三数取中优化和荷兰国旗优化的工程实践。
一、算法思想：分而治之
快速排序的核心思想可以概括为三步：
- 选择基准（Pivot）：从数组中选取一个元素作为分界点。
- 分区（Partition）：将数组重新排列，使小于基准的元素都在左侧，大于基准的元素都在右侧。
- 递归排序：对左右两个子数组递归执行上述过程，直到子数组长度为 1 或 0。
初始数组: [3, 6, 8, 10, 1, 2, 1]
选择 pivot = 3 (首元素)
分区后 : [1, 2, 1] [3] [6, 8, 10]
↑左子数组 基准 右子数组↑
递归排序左: [1, 1, 2]
递归排序右: [6, 8, 10]
最终结果 : [1, 1, 2, 3, 6, 8, 10]
二、核心数据结构
/**
* 排序结果封装，用于分析比较次数和交换次数
*/
public class SortResult {
public final int[] sortedArray;
public final long comparisons; // 比较次数
public final long swaps; // 交换次数
public final int recursionDepth; // 最大递归深度
public SortResult(int[] sortedArray, long comparisons, long swaps, int recursionDepth) {
this.sortedArray = sortedArray;
this.comparisons = comparisons;
this.swaps = swaps;
this.recursionDepth = recursionDepth;
}
@Override
public String toString() {
return String.format("QuickSort{comparisons=%d, swaps=%d, depth=%d}",
comparisons, swaps, recursionDepth);
}
}
三、Lomuto 分区方案：简洁直观
Lomuto 分区是最易于理解的分区方案，使用单向扫描。
3.1 算法原理
- 选择最后一个元素作为 pivot。
- 维护一个指针
i，指向小于 pivot 的区域的最后一个位置。 - 遍历数组，当发现
arr[j] < pivot时，将i右移，并交换arr[i]与arr[j]。 - 最后将 pivot 放到
i+1的位置。
/**
* Lomuto 分区方案
* 选择最后一个元素作为 pivot
* 返回 pivot 的最终位置
*/
public class LomutoPartition {
/**
* 对 arr[low..high] 进行 Lomuto 分区
* @return pivot 的最终索引
*/
public static int partition(int[] arr, int low, int high, Counter counter) {
int pivot = arr[high]; // 选择末尾元素作为 pivot
int i = low - 1; // i 指向小于 pivot 区域的末尾
for (int j = low; j < high; j++) {
counter.comparisons++;
if (arr[j] < pivot) {
i++;
swap(arr, i, j, counter);
}
}
// 将 pivot 放到正确位置
swap(arr, i + 1, high, counter);
return i + 1;
}
private static void swap(int[] arr, int i, int j, Counter counter) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
counter.swaps++;
}
}
/**
* 计数器，用于统计算法执行过程中的操作次数
*/
public static class Counter {
public long comparisons = 0;
public long swaps = 0;
}
}
3.2 Lomuto 快速排序完整实现
/**
* 基于 Lomuto 分区的快速排序
*/
public class QuickSortLomuto {
public static SortResult sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return new SortResult(arr != null ? arr.clone() : null, 0, 0, 0);
}
int[] copy = arr.clone();
LomutoPartition.Counter counter = new LomutoPartition.Counter();
int[] maxDepth = new int[]{0};
quickSort(copy, 0, copy.length - 1, counter, 1, maxDepth);
return new SortResult(copy, counter.comparisons, counter.swaps, maxDepth[0]);
}
private static void quickSort(int[] arr, int low, int high,
LomutoPartition.Counter counter, int depth, int[] maxDepth) {
maxDepth[0] = Math.max(maxDepth[0], depth);
if (low < high) {
int pi = LomutoPartition.partition(arr, low, high, counter);
// 递归排序左右两部分
quickSort(arr, low, pi - 1, counter, depth + 1, maxDepth);
quickSort(arr, pi + 1, high, counter, depth + 1, maxDepth);
}
}
}
四、Hoare 分区方案：效率更优
Hoare 分区是 Tony Hoare 的原始设计，使用双向扫描，交换次数更少。
4.1 算法原理
- 选择第一个元素作为 pivot（或中间元素）。
- 左指针
i从左向右扫描，找到第一个>= pivot的元素。 - 右指针
j从右向左扫描，找到第一个<= pivot的元素。 - 如果
i < j，交换这两个元素；否则分区结束，返回j。
/**
* Hoare 分区方案
* 双向扫描，通常比 Lomuto 效率更高，交换次数更少
*/
public class HoarePartition {
/**
* 对 arr[low..high] 进行 Hoare 分区
* @return 分区边界索引 j，arr[low..j] <= pivot <= arr[j+1..high]
*/
public static int partition(int[] arr, int low, int high, Counter counter) {
int pivot = arr[low + (high - low) / 2]; // 选择中间元素作为 pivot
int i = low - 1;
int j = high + 1;
while (true) {
// 左指针右移：找到 >= pivot 的元素
do {
i++;
counter.comparisons++;
} while (arr[i] < pivot);
// 右指针左移：找到 <= pivot 的元素
do {
j--;
counter.comparisons++;
} while (arr[j] > pivot);
if (i >= j) {
return j; // 分区完成
}
// 交换左右指针指向的元素
swap(arr, i, j, counter);
}
}
private static void swap(int[] arr, int i, int j, Counter counter) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
counter.swaps++;
}
}
public static class Counter {
public long comparisons = 0;
public long swaps = 0;
}
}
4.2 Hoare 快速排序完整实现
/**
* 基于 Hoare 分区的快速排序
* 实际运行中通常比 Lomuto 版本快 3-5 倍
*/
public class QuickSortHoare {
public static SortResult sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return new SortResult(arr != null ? arr.clone() : null, 0, 0, 0);
}
int[] copy = arr.clone();
HoarePartition.Counter counter = new HoarePartition.Counter();
int[] maxDepth = new int[]{0};
quickSort(copy, 0, copy.length - 1, counter, 1, maxDepth);
return new SortResult(copy, counter.comparisons, counter.swaps, maxDepth[0]);
}
private static void quickSort(int[] arr, int low, int high,
HoarePartition.Counter counter, int depth, int[] maxDepth) {
maxDepth[0] = Math.max(maxDepth[0], depth);
if (low < high) {
int pi = HoarePartition.partition(arr, low, high, counter);
// 注意：Hoare 分区后，pi 位置本身可能不需要再排序
quickSort(arr, low, pi, counter, depth + 1, maxDepth);
quickSort(arr, pi + 1, high, counter, depth + 1, maxDepth);
}
}
}
五、工程优化：三数取中法
当数组已经有序或接近有序时，固定选择首/尾元素作为 pivot 会导致递归深度达到 O(n)，退化为最坏情况。三数取中法选择首、中、尾三个元素的中位数作为 pivot，有效避免这一问题。
/**
* 三数取中优化：选择 low, mid, high 三个位置的中位数作为 pivot
* 大幅降低对有序/逆序数组的敏感性
*/
public class MedianOfThree {
/**
* 将中位数放到 arr[high] 位置（配合 Lomuto 分区）
* 返回中位数的值
*/
public static int medianToHigh(int[] arr, int low, int high, Counter counter) {
int mid = low + (high - low) / 2;
// 确保 arr[low] <= arr[mid] <= arr[high]
if (arr[low] > arr[mid]) {
swap(arr, low, mid, counter);
}
if (arr[low] > arr[high]) {
swap(arr, low, high, counter);
}
if (arr[mid] > arr[high]) {
swap(arr, mid, high, counter);
}
// 将中位数交换到倒数第二个位置，pivot 放到 high
swap(arr, mid, high, counter);
return arr[high];
}
private static void swap(int[] arr, int i, int j, Counter counter) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
counter.swaps++;
}
public static class Counter {
public long swaps = 0;
}
}
六、工程优化：荷兰国旗问题（处理重复元素）
当数组中存在大量重复元素时，标准快速排序会产生大量不必要的递归调用。荷兰国旗算法将数组分为 < pivot、== pivot、> pivot 三个区域，将相等的元素一次性归位。
/**
* 三向切分快速排序（Dutch National Flag）
* 针对大量重复元素的最优方案，时间复杂度退化为 O(n)
*/
public class QuickSort3Way {
public static SortResult sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return new SortResult(arr != null ? arr.clone() : null, 0, 0, 0);
}
int[] copy = arr.clone();
Counter counter = new Counter();
int[] maxDepth = new int[]{0};
quickSort(copy, 0, copy.length - 1, counter, 1, maxDepth);
return new SortResult(copy, counter.comparisons, counter.swaps, maxDepth[0]);
}
private static void quickSort(int[] arr, int low, int high, Counter counter, int depth, int[] maxDepth) {
maxDepth[0] = Math.max(maxDepth[0], depth);
if (low >= high) return;
// 三数取中选择 pivot
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) swap(arr, low, mid, counter);
if (arr[low] > arr[high]) swap(arr, low, high, counter);
if (arr[mid] > arr[high]) swap(arr, mid, high, counter);
swap(arr, mid, high - 1, counter);
int pivot = arr[high - 1];
// 三向切分
int lt = low; // arr[low..lt-1] < pivot
int gt = high - 1; // arr[gt+1..high] > pivot
int i = low; // 当前扫描指针
while (i <= gt) {
counter.comparisons++;
if (arr[i] < pivot) {
swap(arr, lt, i, counter);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(arr, i, gt, counter);
gt--;
} else {
i++; // arr[i] == pivot
}
}
// 递归处理 < pivot 和 > pivot 的区域
quickSort(arr, low, lt - 1, counter, depth + 1, maxDepth);
quickSort(arr, gt + 1, high, counter, depth + 1, maxDepth);
}
private static void swap(int[] arr, int i, int j, Counter counter) {
if (i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
counter.swaps++;
}
}
public static class Counter {
public long comparisons = 0;
public long swaps = 0;
}
}
七、主程序：对比测试与可视化输出
import java.util.Arrays;
import java.util.Random;
/**
* 快速排序主程序：对比三种实现的性能
*/
public class QuickSortDemo {
public static void main(String[] args) {
System.out.println("=== 快速排序算法对比测试 ===\n");
// 测试用例 1：随机数组
int[] randomArr = generateRandomArray(10000, 100000);
System.out.println("【测试1】随机数组 (n=10000, 范围0-100000)");
runComparison(randomArr);
// 测试用例 2：已排序数组（最坏情况）
int[] sortedArr = generateSortedArray(10000);
System.out.println("\n【测试2】已排序数组 (n=10000, 最坏情况)");
runComparison(sortedArr);
// 测试用例 3：大量重复元素
int[] duplicateArr = generateDuplicateArray(10000, 10);
System.out.println("\n【测试3】大量重复元素 (n=10000, 仅10个不同值)");
runComparison(duplicateArr);
// 可视化演示：小规模数组排序过程
System.out.println("\n=== 排序过程可视化 ===");
int[] demoArr = {3, 6, 8, 10, 1, 2, 1, 5, 9, 4};
System.out.println("原始数组: " + Arrays.toString(demoArr));
int[] sorted = QuickSortHoare.sort(demoArr).sortedArray;
System.out.println("排序结果: " + Arrays.toString(sorted));
}
private static void runComparison(int[] arr) {
// Lomuto 版本
SortResult r1 = QuickSortLomuto.sort(arr);
System.out.printf(" Lomuto : %s | 结果验证: %s%n",
r1, isSorted(r1.sortedArray) ? "✓" : "✗");
// Hoare 版本
SortResult r2 = QuickSortHoare.sort(arr);
System.out.printf(" Hoare : %s | 结果验证: %s%n",
r2, isSorted(r2.sortedArray) ? "✓" : "✗");
// 三向切分版本
SortResult r3 = QuickSort3Way.sort(arr);
System.out.printf(" 3-Way : %s | 结果验证: %s%n",
r3, isSorted(r3.sortedArray) ? "✓" : "✗");
}
private static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) return false;
}
return true;
}
private static int[] generateRandomArray(int n, int bound) {
Random rand = new Random(42); // 固定种子保证可复现
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = rand.nextInt(bound);
return arr;
}
private static int[] generateSortedArray(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i;
return arr;
}
private static int[] generateDuplicateArray(int n, int distinct) {
Random rand = new Random(42);
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = rand.nextInt(distinct);
return arr;
}
}
八、复杂度分析
| 指标 | 最优情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 时间复杂度 | O(n log n) | O(n log n) | O(n²) |
| 空间复杂度 | O(log n) | O(log n) | O(n) |
| 稳定性 | 不稳定 | 不稳定 | 不稳定 |
说明：
– 最优/平均：每次 pivot 都能将数组大致均分，递归深度为 log n。
– 最坏情况：数组已有序且选择首尾元素作为 pivot，此时递归深度为 n。
– 三数取中优化：可将最坏情况概率降至极低，实践中几乎不可能触发 O(n²)。
– 三向切分：当存在大量重复元素时，时间复杂度退化为 O(n)，远优于标准快排。
九、方案对比与选型建议
| 方案 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| Lomuto | 教学理解 | 代码简洁，单向扫描易理解 | 交换次数多，对有序数组敏感 |
| Hoare | 通用场景 | 交换次数少，分区更均衡 | 分区边界理解稍复杂 |
| 三向切分 | 大量重复数据 | 重复元素O(n)处理 | 常数因子略大，通用数据无明显优势 |
十、总结
快速排序的魅力在于简单规则产生高效结果：仅通过一个 pivot 和双指针扫描，就能在平均情况下达到与归并排序相同的时间复杂度，同时保持原地排序的空间优势。掌握 Lomuto 与 Hoare 两种分区方案、三数取中优化以及荷兰国旗三向切分，足以应对绝大多数工程场景。建议读者运行本文提供的 QuickSortDemo 主程序，亲自观察三种实现在不同数据分布下的性能差异，加深对分治策略的理解。
