算法系列（Algorithm）- 快速排序-程序员充电站

1. 基本思想与核心原理

快速排序的核心思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

该算法的基本步骤包括：

选择基准值（Pivot）：从数组中选择一个元素作为基准值
分区操作（Partition）：重新排列数组，使所有小于基准值的元素都放在基准值的左边，所有大于基准值的元素都放在基准值的右边
递归排序：对基准值左右两边的子数组递归地执行快速排序

2. 快速排序的详细实现步骤

2.1 分区操作详解

分区操作是快速排序算法的核心部分，其目标是将数组重新排列，使得所有小于基准值的元素位于基准值的左侧，所有大于基准值的元素位于基准值的右侧。

分区算法的具体过程：

选择数组的最后一个元素作为基准值（pivot）
初始化两个指针：i指向较小元素的边界（初始为low-1），j用于遍历数组
遍历数组从low到high-1：
- 如果当前元素小于等于基准值，将i指针右移一位，然后交换arr[i]和arr[j]
最后将基准值放到正确位置（i+1处）

2.2 递归排序过程

完成分区操作后，基准值已经处于其最终排序位置。此时，数组被分成两个子数组：

左子数组：包含所有小于基准值的元素
右子数组：包含所有大于基准值的元素

对这两个子数组分别递归地执行快速排序，直到子数组的大小为0或1（即已经有序）。

2.3 打个比喻

可以把快速排序想象成快速分类快递：

选一个参考快递：比如选一个重量为1kg的快递作为参考
快速分堆：把所有小于1kg的放左边，大于1kg的放右边
每堆再分：对左边那堆，再选一个0.5kg的作为参考，继续分
直到分完：一直分到每堆只有一个快递，就全部排好序了

这个方法的聪明之处在于：不用一个个比较所有快递，而是通过选参考值快速分成两堆，大大减少了比较次数。

3. Java实现完整代码

以下是快速排序在Java中的标准实现，包含详细的注释说明：

import java.util.Arrays; public class QuickSort { /** * 快速排序的入口方法 * @param arr 待排序的数组 */ public static void quickSort(int[] arr) { if (arr == null || arr.length == 0) { return; } quickSort(arr, 0, arr.length - 1); } /** * 递归实现快速排序 * @param arr 待排序的数组 * @param low 子数组的起始索引 * @param high 子数组的结束索引 */ private static void quickSort(int[] arr, int low, int high) { if (low < high) { // 执行分区操作，获取基准值的正确位置 int pivotIndex = partition(arr, low, high); // 递归排序左子数组（基准值左边的元素） quickSort(arr, low, pivotIndex - 1); // 递归排序右子数组（基准值右边的元素） quickSort(arr, pivotIndex + 1, high); } } /** * 分区操作 - 快速排序的核心 * @param arr 待分区的数组 * @param low 分区起始索引 * @param high 分区结束索引 * @return 基准值的最终位置索引 */ private static int partition(int[] arr, int low, int high) { // 选择最后一个元素作为基准值（pivot） int pivot = arr[high]; // i指向较小元素的边界，初始为low-1 int i = low - 1; // 遍历数组，将小于基准值的元素移到左边 for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } // 将基准值放到正确的位置（i+1） swap(arr, i + 1, high); // 返回基准值的最终位置 return i + 1; } /** * 交换数组中两个元素的位置 * @param arr 数组 * @param i 第一个元素的索引 * @param j 第二个元素的索引 */ 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) { // 测试用例1：普通数组 int[] arr1 = {10, 7, 8, 9, 1, 5}; System.out.println("原始数组1: " + Arrays.toString(arr1)); quickSort(arr1); System.out.println("排序后数组1: " + Arrays.toString(arr1)); // 测试用例2：包含重复元素的数组 int[] arr2 = {3, 6, 8, 10, 1, 2, 1}; System.out.println("\n原始数组2: " + Arrays.toString(arr2)); quickSort(arr2); System.out.println("排序后数组2: " + Arrays.toString(arr2)); // 测试用例3：已排序数组 int[] arr3 = {1, 2, 3, 4, 5}; System.out.println("\n原始数组3: " + Arrays.toString(arr3)); quickSort(arr3); System.out.println("排序后数组3: " + Arrays.toString(arr3)); // 测试用例4：逆序数组 int[] arr4 = {5, 4, 3, 2, 1}; System.out.println("\n原始数组4: " + Arrays.toString(arr4)); quickSort(arr4); System.out.println("排序后数组4: " + Arrays.toString(arr4)); } }

4. 算法性能分析

4.1 时间复杂度分析

快速排序的时间复杂度取决于分区操作的质量：

最佳情况：每次分区都能将数组均匀分成两半，此时时间复杂度为O(n log n)
平均情况：在随机数据下，快速排序的平均时间复杂度也为O(n log n)，这是其在实际应用中表现优异的主要原因
最坏情况：当每次分区都产生极度不平衡的分区时（例如数组已经有序或逆序），时间复杂度会退化到O(n²)

4.2 空间复杂度分析

快速排序是原地排序算法，不需要额外的存储空间来存储数据副本。其空间复杂度主要来自递归调用栈：

最佳和平均情况：O(log n)（递归深度）
最坏情况：O(n)（递归深度达到n）

4.3 稳定性分析

快速排序是一种不稳定的排序算法。在分区过程中，相等元素的相对位置可能会发生变化。

5. 快速排序的优化策略

虽然基本的快速排序算法已经相当高效，但在实际应用中还可以通过以下策略进行优化：

5.1 基准值选择优化

随机选择基准值：通过随机选择基准值，可以避免最坏情况的发生，提高算法的平均性能
三数取中法：选择数组的第一个、中间和最后一个元素的中位数作为基准值，可以减少分区不平衡的情况
随机化快速排序：在分区前随机交换一个元素到末尾作为基准值

5.2 小数组优化

当子数组的大小小于某个阈值（通常为10-20）时，可以使用插入排序代替快速排序。因为对于小数组，插入排序的常数因子更小，实际运行速度更快。

5.3 三路快速排序

对于包含大量重复元素的数组，可以使用三路快速排序（Three-way QuickSort）。它将数组分成三部分：小于基准值、等于基准值和大于基准值。这样可以避免对相等元素的重复比较和交换。

三路快速排序的实现示例：

public static void threeWayQuickSort(int[] arr, int low, int high) { if (low < high) { int[] pivotRange = threeWayPartition(arr, low, high); threeWayQuickSort(arr, low, pivotRange[0] - 1); threeWayQuickSort(arr, pivotRange[1] + 1, high); } }