本文目录如下：

一、快速排序基本思想

1、时间复杂度

2、空间复杂度

二、数组分步排序演示

第一轮分区（基准值 pivot = 3）

递归处理左右子区间

三、快速排序核心规律小结（适配快排特性）

四、基础版快速排序代码（单边递归+左右指针法）

五、快速排序优化方案（面试必考）

六、面试核心总结（对标冒泡笔记结尾）

一、快速排序基本思想

快速排序是交换排序的一种，基于分治、递归思想，是冒泡排序的优化升级版。

核心思路：在序列中选取一个基准值（pivot），通过一趟排序，将数组分区，比基准值小的放左边，比基准值大的放右边。完成分区后，基准值就位。再对左右两个子区间递归重复分区操作，最终实现整体有序。

特点：每一轮排序确定一个基准值的最终位置，不像冒泡一样逐轮固定末尾最大值。

1、时间复杂度

基础版快排（固定左端基准）

- 最好情况（每次均分区间）：O(nlogn)

- 最坏情况（有序/逆序数组）：O(n²)

- 平均情况：O(nlogn)

优化版快排（随机/三数取中基准）

- 几乎杜绝最坏情况，日常稳定 O(nlogn)

- 平均、最好均为 O(nlogn)

2、空间复杂度

- 基础版、优化版：O(logn) ~ O(n)

- 解释：快排非原地排序（逻辑上原地），主要消耗递归栈空间；最优栈深度logn，最坏n

二、数组分步排序演示

待排序原始数组：3，9，-1，10，20

规则：默认选取最左侧元素为基准值，左指针找大值，右指针找小值，相遇交换，最终归位基准数。

第一轮分区（基准值 pivot = 3）

初始数组：【3，9，-1，10，20】

1、右指针先向左找小于3 的数：找到 -1

2、左指针向右找 大于3 的数：找到 9

3、交换 9 和 -1 → 数组：【3，-1，9，10，20】

4、左右指针继续移动，最终相遇在索引1位置

5、将基准值 3 与相遇位置的值交换 → 【-1，3，9，10，20】

第一轮结果：基准值3已归位，左边全部小、右边全部大

递归处理左右子区间

左区间：[-1]，只有单个元素，天然有序，无需排序

右区间：[9,10,20]

对右区间重复选取基准、分区、递归操作：

1、以9为基准，分区后9归位，右侧剩余[10,20]

2、以10为基准，分区后10归位，剩余20天然有序

最终得到有序数组：[-1，3，9，10，20]

三、快速排序核心规律小结（适配快排特性）

1、快排不固定循环轮数，采用递归分治，不断划分子区间

2、每一次分区，仅确定基准值的最终位置

3、相较于冒泡每轮只能确定一个最值，快排一次分区可批量规整大量元素，效率极高

4、极端情况下（有序数组选最左为基准）会退化效率，需要针对性优化

四、基础版快速排序代码（单边递归+左右指针法）

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, 20};
        quickSort(arr, 0, arr.length - 1);

        // 输出结果
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    // 快排递归方法
    public static void quickSort(int[] arr, int left, int right) {
        // 递归终止条件：区间只剩0/1个元素
        if (left >= right) {
            return;
        }

        // 得到基准值位置
        int pivotIndex = partition(arr, left, right);

        // 递归处理左区间
        quickSort(arr, left, pivotIndex - 1);
        // 递归处理右区间
        quickSort(arr, pivotIndex + 1, right);
    }

    // 分区方法：返回基准值最终下标
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left]; // 选最左为基准
        int l = left;
        int r = right;

        while (l < r) {
            // 右指针找比pivot小的
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            // 左指针找比pivot大的
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            // 交换左右指针元素
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }

        // 指针相遇，基准值归位
        arr[left] = arr[l];
        arr[l] = pivot;
        return l;
    }
}

五、快速排序优化方案（面试必考）

基础版缺陷：有序数组、逆序数组下，每次分区极不均衡，递归深度最大，算法退化严重，时间复杂度退化为 O(n²)。

优化方式：随机基准值 / 三数取中法，避免极端分区。

下面给出 随机选取基准优化版（工程常用、面试首选）：

import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, 20};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partitionRandom(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    // 优化：随机选取基准
    public static int partitionRandom(int[] arr, int left, int right) {
        // 随机下标
        int randomIndex = new Random().nextInt(right - left + 1) + left;
        // 交换到最左，复用原有分区逻辑
        int temp = arr[left];
        arr[left] = arr[randomIndex];
        arr[randomIndex] = temp;

        return partition(arr, left, right);
    }

    // 原有分区逻辑不变
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            while (l < r && arr[l] <= pivot) l++;
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        arr[left] = arr[l];
        arr[l] = pivot;
        return l;
    }
}

六、面试核心总结（对标冒泡笔记结尾）

1、快排核心：分治+递归+左右分区，基准值归位

2、相比于冒泡O(n²)，快排效率极高，是实战最常用排序

3、原生快排缺陷：有序数组会退化，必须随机基准优化

4、平均复杂度 O(nlogn) 的原因：绝大多数场景分区均衡，递归层数为logn