本文目录如下一、快速排序基本思想1、时间复杂度2、空间复杂度二、数组分步排序演示第一轮分区基准值 pivot 3递归处理左右子区间三、快速排序核心规律小结适配快排特性四、基础版快速排序代码单边递归左右指针法五、快速排序优化方案面试必考六、面试核心总结对标冒泡笔记结尾一、快速排序基本思想快速排序是交换排序的一种基于分治、递归思想是冒泡排序的优化升级版。核心思路在序列中选取一个基准值pivot通过一趟排序将数组分区比基准值小的放左边比基准值大的放右边。完成分区后基准值就位。再对左右两个子区间递归重复分区操作最终实现整体有序。特点每一轮排序确定一个基准值的最终位置不像冒泡一样逐轮固定末尾最大值。1、时间复杂度基础版快排固定左端基准-最好情况每次均分区间O(nlogn)-最坏情况有序/逆序数组O(n²)-平均情况O(nlogn)优化版快排随机/三数取中基准- 几乎杜绝最坏情况日常稳定 O(nlogn)- 平均、最好均为 O(nlogn)2、空间复杂度- 基础版、优化版O(logn)~O(n)- 解释快排非原地排序逻辑上原地主要消耗递归栈空间最优栈深度logn最坏n二、数组分步排序演示待排序原始数组39-11020规则默认选取最左侧元素为基准值左指针找大值右指针找小值相遇交换最终归位基准数。第一轮分区基准值 pivot 3初始数组【39-11020】1、右指针先向左找小于3的数找到 -12、左指针向右找大于3的数找到 93、交换 9 和 -1 → 数组【3-191020】4、左右指针继续移动最终相遇在索引1位置5、将基准值 3 与相遇位置的值交换 → 【-1391020】第一轮结果基准值3已归位左边全部小、右边全部大递归处理左右子区间左区间[-1]只有单个元素天然有序无需排序右区间[9,10,20]对右区间重复选取基准、分区、递归操作1、以9为基准分区后9归位右侧剩余[10,20]2、以10为基准分区后10归位剩余20天然有序最终得到有序数组[-1391020]三、快速排序核心规律小结适配快排特性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