1、简述
排序是数据结构与算法中最基础、最常见的问题之一。在各种排序算法中，快速排序（QuickSort） 因其 平均时间复杂度 O(n log n) 和实际运行的高效率，被广泛应用在工程实践和面试考题中。
今天我们来深入理解快速排序的思想，并给出 Java 实现及实践样例。
2、核心思想
快速排序属于 分治（Divide and Conquer） 算法，核心思想是：
✨ 选择基准（pivot）
从数组中选择一个元素作为基准（常见选择是第一个、最后一个或随机一个）。
✨ 分区（partition）
将小于基准的元素放在左边，大于基准的放在右边。
✨ 递归排序
对左右两个子数组递归执行快速排序，直到子数组大小为 1 或 0。
2.1 快速排序的示意图
假设数组： [3, 6, 8, 10, 1, 2, 1]
✨ 选择基准 pivot = 3
✨ 分区后： [1, 2, 1] | 3 | [6, 8, 10]
✨ 递归：
左边 [1, 2, 1] → [1, 1, 2]
右边 [6, 8, 10] → [6, 8, 10]
✨ 合并： [1, 1, 2, 3, 6, 8, 10]
2.2 快速排序的时间复杂度
✨ 最好情况：每次分区都能均匀分割 → O(n log n)
✨ 最坏情况：数组接近有序，每次只能分割出一个元素 → O(n^2)
✨ 平均情况：O(n log n)
空间复杂度：O(log n)（递归栈深度）。
3、实践样例
标准快速排序实现
public class QuickSort {
// 主方法
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1); // 左子数组
quickSort(arr, pivotIndex + 1, right); // 右子数组
}
}
// 分区方法
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选取最后一个元素作为基准
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right); // 将基准放到正确位置
return i + 1;
}
// 交换元素
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[] arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.length - 1);
System.out.print("排序结果：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
运行结果
排序结果：1 1 2 3 6 8 10
4、优化思路
虽然快速排序性能优秀，但仍有一些优化方法：
✨ 基准选择优化
随机选择基准（Randomized QuickSort）。
三数取中法（median-of-three）。
✨ 小数组优化
当子数组很小（如 ≤ 10），可以使用 插入排序 替代。
✨ 尾递归优化
避免过深的递归调用，减少栈开销。
5、总结
✨ 快速排序是 分治思想 的典型代表，平均时间复杂度为 O(n log n)。
✨ Java 实现并不复杂，核心在于 分区（partition） 操作。
✨ 在工程应用中，通常会结合随机基准、插入排序等优化方式，提升实际性能。
📌 通过本文你应该掌握了：
✅ 快速排序的基本原理
✅ Java 实现方式
✅ 运行样例和优化思路
