一、题目与核心思想题目要求给你一个整数数组nums将数组升序排序后返回。考察核心快速排序的手撕实现能力进阶要求随机化基准值避免有序数组下的时间复杂度退化快排核心思想分治快速排序的本质是分治算法三步完成选基准分区在区间中选一个基准值 pivot将数组切分为两部分 —— 左边都小于 pivot右边都大于等于 pivotpivot 最终落在自己的正确位置上递归处理子区间分别对 pivot 左边和右边的子区间重复执行分区操作递归终止当区间为空或只有一个元素时天然有序停止递归二、分区方案选型Lomuto 单指针分区本次手写采用Lomuto 洛穆托分区法也是最容易理解的分区实现。核心逻辑一句话概括只主动维护「小于 pivot 的左区间」大于等于 pivot 的元素不用主动处理自然会被留在右侧。两个指针的分工i 指针标记「小于 pivot 元素区间」的右边界初始为l - 1代表一开始小区间为空j 指针从左到右遍历整个区间除 pivot 本身遇到小于 pivot 的元素把它交换进左区间i 同步右扩一位遇到大于等于 pivot 的元素什么都不做j 继续前进遍历结束后把 pivot 交换到i 1的位置两个区间的中间完成归位三、复盘坑 1sortArray 缺少 return 语句 → 编译直接不通过public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); // 没有返回值 }现象编译报错missing return statement方法声明返回int[]但没有对应的 return 语句。修正调用完快排后返回排序后的数组return nums;坑 2递归无终止条件 → 运行栈溢出错误代码片段public void quickSort(int[] nums,int l,int r){ int pos randomPartition(nums,l,r); quickSort(nums,l,pos-1); quickSort(nums,pos1,r); }现象运行时报StackOverflowError栈溢出错误。原因递归必须有终止条件。当l r时区间为空或只有一个元素天然有序不需要再分区排序。不加判断会无限递归下去直到栈空间耗尽。修正用条件判断包裹分区与递归逻辑只有区间有效时才执行if (l r) { int pivotPos randomPartition(nums, l, r); quickSort(nums, l, pivotPos - 1); quickSort(nums, pivotPos 1, r); }补充另一种等价写法是开头加if (l r) return;两种写法逻辑完全一致只是风格不同。坑 3Random 定义为方法局部变量 → 编译找不到符号错误代码片段public int[] sortArray(int[] nums) { Random random new Random(); // 局部变量 ... } public int randomPartition(...) { int posIdx random.nextInt(...); // 访问不到 ... }现象编译报错cannot find symbol: variable random。原因和快速选择踩的是同一个坑方法内的局部变量作用域仅限当前方法其他方法无法访问。修正把Random提升为类成员变量所有方法共享同一个随机数实例彻底杜绝作用域问题。坑 4partition 循环边界写错 → 漏掉元素排序结果错误错误代码片段for(int j l; j r-1; j)现象分区不完整最终排序结果不正确。原因Lomuto 分区中pivot 固定在最右端r位置j 需要遍历[l, r-1]的所有元素。遍历到r-1停止对应的循环条件是j r写成j r-1相当于只遍历到r-2漏掉了一个元素修正循环条件改为j r。四、最终定稿随机化 Lomuto 快排 AC 代码import java.util.Random; class Solution { // 随机数实例提为成员变量所有方法共享避免作用域报错 private final Random random new Random(); public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); // 返回排序后的数组 return nums; } private void quickSort(int[] nums, int l, int r) { // 递归终止只有区间有效时才执行分区与递归 if (l r) { // 随机分区得到pivot最终位置 int pivotPos randomPartition(nums, l, r); // 递归排序左右子区间pivot已归位不再参与排序 quickSort(nums, l, pivotPos - 1); quickSort(nums, pivotPos 1, r); } } private int randomPartition(int[] nums, int l, int r) { // 闭区间等概率随机下标公式 int randIndex l random.nextInt(r - l 1); // 将随机选中的pivot交换到最右端适配Lomuto分区 swap(nums, randIndex, r); return partition(nums, l, r); } private int partition(int[] nums, int l, int r) { int pivot nums[r]; // pivot固定在区间最右端 int i l - 1; // i标记小于pivot区间的右边界 // j遍历[l, r-1]的所有元素 for (int j l; j r; j) { if (nums[j] pivot) { // 先扩边界再放元素 i; swap(nums, i, j); } } // pivot归位放到两个区间的中间 swap(nums, i 1, r); return i 1; } private void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }五、核心细节深度拆解1. 为什么必须先 i 再 swap这是由 i 的定义决定的i 是「小于 pivot 区间的右边界」。初始i l - 1代表小区间为空每找到一个新的小于 pivot 的元素需要先把小区间的右边界往右扩一格i再把新元素放到这个新边界上如果顺序反过来先 swap 再 i初始 i-1 时会直接数组下标越界记忆口诀先挪边界再放元素。2. 为什么要随机化 pivot如果每次都固定选最左 / 最右元素作为 pivot遇到完全有序的数组时每次分区都会切成「1 个元素 n-1 个元素」的极不均匀区间递归深度达到 n时间复杂度退化为 O (n²)。 随机选 pivot 可以极大程度避免这种最坏情况让时间复杂度稳定在平均 O (nlogn)。3. 等于 pivot 的元素去哪了判断条件是nums[j] pivot因此等于 pivot 的元素不会触发交换会被统一归到右半区。 这是 Lomuto 分区的特点逻辑极简但大量重复元素时分区不均匀如果需要优化重复元素场景可以升级为三路快排。六、拓展对比Lomuto vs Hoare 双指针分区常说的「传统两边指针移动交换」就是 Hoare 霍尔分区法和 Lomuto 目标一致但实现思路差异很大。维度Lomuto 单指针分区Hoare 双指针分区指针设计1 个遍历指针 j 1 个分界指针 i左右 2 个指针相向移动pivot 默认位置区间最右端r区间最左端l交换逻辑遇到小元素换到左区间单次只解决 1 个元素左右找到错位元素互换单次解决 2 个元素交换次数多存在大量无效自交换少数组越大性能优势越明显整体性能一般更优工业级快排普遍采用 Hoare 变体理解难度简单直观易懂稍复杂边界条件容易写错pivot 归位位置i 1两指针相遇位置通常为 right学习建议两个版本的边界、循环条件、归位位置完全不通用千万不要混写。入门先吃透 Lomuto 理解分区本质面试手写优先掌握 Hoare 版本性能更符合面试官预期。七、面试相关口述思路这道题我用随机化快速排序来实现核心是分治思想。每次在区间内随机选一个基准值通过 Lomuto 分区将数组切分为小于基准和大于等于基准的两部分基准值归位到正确位置然后递归排序左右两个子区间直到区间长度小于等于 1 时终止。随机选基准是为了避免有序数组下时间复杂度退化为 O (n²)平均时间复杂度 O (nlogn)空间复杂度主要是递归栈开销平均为 O (logn)。高频追问快排的时间复杂度平均 O (nlogn)最坏 O (n²)随机化 pivot 后最坏情况出现的概率极低工程中可以认为稳定在 O (nlogn)。快排是稳定排序吗不是。分区过程中的交换会打乱相等元素的相对顺序。为什么不用最左 / 最右当 pivot有序数组下会导致分区极度不均匀时间复杂度退化为 O (n²)随机化可以有效避免这个问题。Lomuto 和 Hoare 哪个更好理解难度上 Lomuto 更简单性能上 Hoare 交换次数更少效率更高是工业级实现的主流方案。八、复习速记选基准做分区小的都往左区挤 递归先判边界值随机防退化归位 i 加一。总结快速排序是分治算法的经典代表Lomuto 分区版本逻辑直白、代码简短非常适合入门手撕。 这道题的坑大多集中在细节上递归必有终止条件、工具变量注意作用域、循环边界要对准遍历范围这些都是快排、快速选择的通用易错点。