快速排序是一种高效的排序算法，它基于分治（Divide and Conquer）的思想，通过选择一个“基准元素”，将数组分成两部分，一部分所有元素都比基准小，另一部分所有元素都比基准大，然后递归地对这两部分进行排序。这种方法能快速处理大规模数据，平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。
快速排序的基本步骤¶
以数组 [6, 3, 8, 5, 2, 7] 为例，我们来一步步演示快速排序的过程：
- 选择基准元素（Pivot）：这里选择数组最右边的元素
7作为基准。 - 分区（Partition）：遍历数组，将小于基准的元素移到基准左侧，大于基准的元素移到右侧。分区后数组变为
[6, 3, 5, 2, 7, 8]，基准7最终位于位置4（索引从 0 开始）。 - 递归排序：此时，基准左侧的子数组
[6, 3, 5, 2]和右侧的子数组[8]（长度为 1，无需排序）需要分别递归排序。 - 处理左侧子数组：对
[6, 3, 5, 2]重复上述步骤，选择最右边元素2作为基准，分区后得到[3, 5, 2, 6]，基准2位于位置0，左侧子数组为空，右侧子数组[3, 5, 6]继续递归排序。 - 最终结果：经过多次递归后，数组将完全有序：
[2, 3, 5, 6, 7, 8]。
分区函数的核心逻辑¶
分区是快速排序的关键步骤，其目标是将数组分为“小于基准”和“大于基准”两部分，并返回基准元素的最终位置。以选择最右侧元素为基准为例，分区过程如下：
- 定义变量
pivot = arr[right]（基准元素）。 - 定义指针
i指向“小于基准区域”的末尾（初始为left - 1）。 - 遍历数组（从
left到right - 1）：
- 若当前元素arr[j] <= pivot，则将其加入“小于基准区域”，即i++后交换arr[i]和arr[j]。 - 遍历结束后，将基准元素
pivot交换到i + 1的位置（“小于基准区域”的末尾 + 1），此时基准元素左侧均小于它，右侧均大于它。
Java 代码实现¶
下面是使用 Java 实现快速排序的完整代码，包含分区函数和递归排序逻辑：
public class QuickSort {
// 快速排序主方法：递归排序数组的 [left, right] 区间
public static void quickSort(int[] arr, int left, int right) {
// 递归终止条件：区间长度小于等于1时无需排序
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; // i 指向“小于基准区域”的末尾（初始为空）
// 遍历数组，将小于等于基准的元素移到左侧
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++; // 扩展“小于基准区域”
// 交换 arr[i] 和 arr[j]，将当前元素加入“小于基准区域”
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素交换到最终位置（i+1）
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
// 返回基准元素的索引
return i + 1;
}
// 测试方法：验证快速排序的正确性
public static void main(String[] args) {
int[] arr = {6, 3, 8, 5, 2, 7};
System.out.println("排序前数组：");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println("\n排序后数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
代码运行结果¶
运行上述代码，输出如下：
排序前数组：
6 3 8 5 2 7
排序后数组：
2 3 5 6 7 8
时间复杂度与空间复杂度¶
- 时间复杂度：平均情况下为 O(n log n)（每次分区操作将数组分为大致相等的两部分，递归深度为 log n）；最坏情况下（如数组已排序或逆序）为 O(n²)（每次分区仅将数组分为 1 和 n-1 两部分，递归深度为 n）。
- 空间复杂度：主要来自递归调用栈，平均为 O(log n)，最坏为 O(n)。
总结¶
快速排序通过分治思想高效排序数组，核心在于分区操作和递归处理。其优点是平均效率高，适合大规模数据；缺点是不稳定排序（相等元素的相对顺序可能改变），且最坏情况性能较差。掌握快速排序不仅能理解分治算法，也能为后续学习更复杂的排序算法打下基础。