Java 快速排序

快速排序（Quick Sort）是一种高效的分治排序算法，平均时间复杂度为 O(n log n)。其核心思想是通过选取一个**基准值（pivot）**将数组分为两部分，左边部分小于基准值，右边部分大于基准值，然后递归地对左右子数组排序。

以下是 Java 实现快速排序的详细代码和解析：

1. 快速排序实现代码

public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 边界条件：空数组或单元素数组已有序
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点，并确保左边 <= pivot，右边 >= pivot
            int pivotIndex = partition(arr, low, high);
            // 递归排序左子数组
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序右子数组
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最右边的元素作为基准值（pivot）
        int pivot = arr[high];
        int i = low - 1; // i 是小于 pivot 的边界指针

        for (int j = low; j < high; j++) {
            // 当前元素 <= pivot 时，将其交换到左边
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将 pivot 放到正确的位置（i+1）
        swap(arr, i + 1, high);
        return i + 1; // 返回 pivot 的最终位置
    }

    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 = {10, 7, 8, 9, 1, 5};
        quickSort(arr);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 输出: 1 5 7 8 9 10
    }
}

2. 关键步骤解析

1. 分区（Partition）：

   • 选择基准值（通常选最后一个元素 arr[high]）。
   • 使用指针 i 标记小于基准值的边界，j 遍历数组。
   • 当 arr[j] <= pivot 时，交换 arr[i] 和 arr[j]，并移动 i。
   • 最后将基准值交换到 i+1 的位置，完成分区。

2. 递归排序：

   • 对基准值左边的子数组（low 到 pivotIndex-1）递归排序。
   • 对基准值右边的子数组（pivotIndex+1 到 high）递归排序。

3. 终止条件：

   • 当子数组长度为 1 或 0 时（low >= high），递归结束。

3. 优化点

• 随机选择基准值：避免最坏情况（如数组已有序时选择最差基准值），可通过随机选择提高性能：

  int randomIndex = new Random().nextInt(high - low + 1) + low;
  swap(arr, randomIndex, high);
  int pivot = arr[high];
  

• 三数取中法：选择 low、mid、high 的中位数作为基准值，进一步优化分区效率。

4. 时间复杂度分析

• 平均情况：O(n log n)
  每次分区将数组大致分为两半，递归深度为 log n，每层需 O(n) 时间。
• 最坏情况：O(n²)
  当数组已有序且基准值选择最差时（如固定选择最右元素），每次分区只能减少一个元素。

5. 空间复杂度

• 递归栈空间：平均 O(log n)，最坏 O(n)（取决于递归深度）。
• 原地排序：仅需常数级额外空间（交换操作）。

6. 稳定性

快速排序是不稳定排序，因为分区时的交换可能改变相等元素的相对顺序。

总结

快速排序通过分治策略高效排序，适合大规模数据。理解其分区逻辑和递归过程是掌握算法的关键。实际应用中可通过随机化基准值或三数取中法优化性能。