在准备数据结构与算法的笔试或面试时快速排序Quick Sort几乎是必考的核心算法。很多同学虽然能理解其“分治”思想但一到手写代码环节就容易在边界条件、递归终止、分区逻辑上出错导致面试官一眼看出基础不牢。本文将彻底拆解快速排序的手写过程从核心思想到一行行代码的推导再到应试中如何写出既正确又优雅的代码并提供完整的代码示例、常见错误分析和避坑指南。无论你是正在备战校招、社招还是想巩固算法基础这篇文章都能帮你把快速排序从“大概懂”变成“闭着眼睛都能写对”。1. 快速排序的核心思想与重要性快速排序是一种高效的、基于“分治”策略的排序算法由 Tony Hoare 在 1960 年提出。它的平均时间复杂度为 O(n log n)最坏情况下为 O(n²)但由于其原地排序in-place的特性在实际应用中尤其是对大规模数据排序时性能通常优于其他 O(n log n) 的算法如归并排序。1.1 分治三步走理解快速排序关键在于掌握其“分治”的精髓这个过程可以概括为三个步骤分解Partition从待排序数组中选择一个元素作为“基准”pivot。然后重新排列数组使得所有小于基准的元素都移到基准的左边所有大于基准的元素都移到基准的右边。操作结束后基准元素就位于其最终的正确位置上。解决Conquer递归地对基准左侧和右侧的两个子数组进行快速排序。合并Combine由于快速排序是原地排序当子数组排序完成后整个数组自然就有序了无需额外的合并操作。这个“分治”过程就像是给一个班级的学生按身高排序先随便挑一个学生作为“标杆”pivot让比他矮的站左边比他高的站右边。然后在左边和右边的队伍里再分别重复这个过程直到每个队伍都排好序。1.2 为什么面试官爱考快速排序快速排序是检验候选人算法基本功的“试金石”原因如下综合性高它涵盖了递归、双指针、边界处理、原地操作等多个基础编程概念。细节多一个简单的快速排序隐藏着无数个“坑”如基准的选择、循环不变量、递归终止条件等能有效区分候选人的代码严谨性。变体多面试官可能要求你写出递归版、迭代版、针对链表的版本或者分析其稳定性、空间复杂度等考察知识的深度和广度。因此仅仅能背诵代码是不够的必须理解每一行代码背后的意图并能应对各种追问。2. 手写快速排序前的准备工作在动手写代码之前我们需要明确几个关键点这能让你在面试时思路更清晰。2.1 理解“分区Partition”过程分区是快速排序的灵魂。我们通常使用“双指针法”或“Lomuto分区方案”来实现。为了应试的通用性和易于讲解本文重点介绍更常见且易于手写的Lomuto 分区方案。Lomuto 分区思路选择最右侧的元素作为基准pivot。初始化一个指针i指向“小于基准”区域的末尾初始为low - 1。使用另一个指针j从左到右遍历数组从low到high - 1。如果arr[j]小于等于基准就将i向右移动一位然后交换arr[i]和arr[j]。这样i及其左侧的元素都小于等于基准。遍历结束后i 1的位置就是基准最终的正确位置。将基准arr[high]与arr[i 1]交换。返回基准的最终位置i 1。这个过程保证了基准左边的元素都不大于它右边的元素都不小于它。2.2 明确递归函数签名一个标准的快速排序递归函数通常需要以下参数arr: 待排序的数组。low: 当前需要排序的子数组的起始索引。high: 当前需要排序的子数组的结束索引。初始调用时low 0,high arr.length - 1。2.3 牢记递归终止条件这是手写递归算法最容易忘记的一步递归必须有一个明确的出口。对于快速排序当low high时意味着当前子数组没有元素或只有一个元素自然已经有序无需再排序。因此递归函数的第一行通常就是if (low high) { return; }3. 手把手推导从思路到完整代码Java实现我们现在遵循“分治”思想一步步写出代码。我们以对数组[10, 80, 30, 90, 40, 50, 70]排序为例。3.1 第一步编写分区函数partition根据 Lomuto 方案我们先实现核心的分区操作。/** * Lomuto 分区方案 * param arr 待分区数组 * param low 分区起始索引 * param high 分区结束索引通常作为基准 * return 基准元素的最终位置 */ private static int partition(int[] arr, int low, int high) { // 1. 选择最右侧元素作为基准 int pivot arr[high]; // 2. i 指向小于基准区域的末尾 int i low - 1; // 3. j 指针遍历 low 到 high-1 for (int j low; j high; j) { // 4. 如果当前元素小于等于基准 if (arr[j] pivot) { i; // 扩大小于基准的区域 // 交换 arr[i] 和 arr[j] swap(arr, i, j); } } // 5. 将基准放到正确位置 (i1) swap(arr, i 1, high); // 6. 返回基准位置 return i 1; } // 辅助交换函数 private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; }让我们手动模拟一下第一次分区low0, high6, pivot70: 初始:[10, 80, 30, 90, 40, 50, 70],i -1j0:arr[0]10 70-i0, 交换arr[0]和arr[0](无变化) -[10, 80, 30, 90, 40, 50, 70]j1:80 70- 无操作j2:30 70-i1, 交换arr[1]和arr[2]-[10, 30, 80, 90, 40, 50, 70]j3:90 70- 无操作j4:40 70-i2, 交换arr[2]和arr[4]-[10, 30, 40, 90, 80, 50, 70]j5:50 70-i3, 交换arr[3]和arr[5]-[10, 30, 40, 50, 80, 90, 70]循环结束。i3。交换arr[4] (i1)和arr[6] (pivot)-[10, 30, 40, 50, 70, 90, 80]返回基准位置4。可以看到索引4左边都小于等于70右边都大于等于70。3.2 第二步编写递归排序函数quickSort有了分区函数递归排序就非常直观了。/** * 快速排序主函数 * param arr 待排序数组 * param low 起始索引 * param high 结束索引 */ public static void quickSort(int[] arr, int low, int high) { // 递归终止条件子数组长度为0或1 if (low high) { return; } // 分区操作获取基准位置 int pivotIndex partition(arr, low, high); // 递归排序左半部分 quickSort(arr, low, pivotIndex - 1); // 递归排序右半部分 quickSort(arr, pivotIndex 1, high); }3.3 第三步提供对外的便捷调用接口通常我们会提供一个更简洁的公共方法。/** * 快速排序对外接口 * param arr 待排序数组 */ public static void quickSort(int[] arr) { if (arr null || arr.length 1) { return; } quickSort(arr, 0, arr.length - 1); }3.4 第四步编写测试代码手写时向面试官说明你会如何测试。public class QuickSortDemo { // 将上面的 partition, swap, quickSort 方法放在这里 public static void main(String[] args) { int[] arr {10, 80, 30, 90, 40, 50, 70}; System.out.println(排序前: Arrays.toString(arr)); quickSort(arr); // 调用对外接口 System.out.println(排序后: Arrays.toString(arr)); // 预期输出: [10, 30, 40, 50, 70, 80, 90] } }4. 应试核心技巧与常见“坑点”分析在笔试或面试的紧张环境下如何保证一次写对以下技巧和坑点你必须烂熟于心。4.1 技巧一先说思路再写代码不要一上来就埋头写。先向面试官清晰地阐述算法思想“我将使用基于分治的快速排序核心是Partition操作。”分区方案“我采用Lomuto分区方案选择最右元素为基准用双指针i, j遍历...”递归过程“分区后递归排序左半部和右半部。”终止条件“当子数组起始索引大于等于结束索引时返回。” 这样即使代码有小瑕疵面试官也知道你思路清晰。4.2 技巧二严格处理边界条件这是手写代码出错的重灾区。递归终止条件必须是if (low high)而不是if (low high)。考虑low5, high4的情况子数组为空也必须终止。分区循环边界for (int j low; j high; j)j必须严格小于high因为arr[high]是基准不参与比较。递归调用边界左半部是(low, pivotIndex-1)右半部是(pivotIndex1, high)。绝对不能包含pivotIndex因为它已经在正确位置了。4.3 技巧三选择合适的中枢Pivot我们例子中选择了最右元素这在应试中简单可行。但你要知道这不是最优的并准备好回答面试官的追问。问题如果数组已经有序或逆序选最左或最右作为基准会导致分区极度不平衡时间复杂度退化为 O(n²)。优化方案了解即可手写时用最简单的随机选择int pivotIndex low random.nextInt(high - low 1); swap(arr, pivotIndex, high);三数取中取low、high、mid三个位置的中位数作为基准。 在面试中你可以先写出基础版本然后补充说“在生产环境中为了避免最坏情况我们会采用随机选择或三数取中法来优化基准的选择。”4.4 技巧四理解循环不变量Loop Invariant这是证明算法正确性的关键概念理解它能帮你写出正确的循环。对于我们的 Lomuto 分区不变量在for循环的每次迭代开始时对于任意索引k如果low k i则arr[k] pivot。如果i1 k j-1则arr[k] pivot。如果k high则arr[k] pivot。 在面试中如果能提及并解释这个不变量会是巨大的加分项。5. 快速排序的变体与相关问题面试官可能不会只满足于标准写法。5.1 Hoare 分区方案这是快速排序发明者最初使用的方案比 Lomuto 更高效交换次数更少但边界条件更复杂。private static int partitionHoare(int[] arr, int low, int high) { int pivot arr[low]; // 选最左为基准 int i low - 1; int j high 1; while (true) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) return j; // 注意这里返回的是 j swap(arr, i, j); } } // 递归调用需改为quickSort(arr, low, p); quickSort(arr, p1, high);应试建议除非面试官明确要求否则优先写 Lomuto 方案因为它更直观不易出错。5.2 迭代法实现快速排序使用栈来模拟递归过程避免递归调用栈过深的问题。public static void quickSortIterative(int[] arr) { if (arr null || arr.length 1) return; StackInteger stack new Stack(); stack.push(0); stack.push(arr.length - 1); while (!stack.isEmpty()) { int high stack.pop(); int low stack.pop(); if (low high) continue; int pivotIndex partition(arr, low, high); // 压入左子数组边界 stack.push(low); stack.push(pivotIndex - 1); // 压入右子数组边界 stack.push(pivotIndex 1); stack.push(high); } }这展示了你不止会递归也理解其本质。5.3 面试常见追问与回答Q: 快速排序是稳定的吗A:不是。在分区过程中相等元素的相对位置可能会被交换。例如[3a, 2, 3b, 1]用a,b区分相同值排序后3a和3b的顺序可能改变。Q: 空间复杂度是多少A:主要是递归调用栈的空间。平均情况深度为 O(log n)故平均空间复杂度 O(log n)。最坏情况有序数组深度为 O(n)。Q: 什么情况下会退化为 O(n²)A:当每次分区选取的基准都是当前子数组的最大或最小元素时导致分区极度不平衡。对已排序或逆序数组且基准选在端点时就会出现。Q: 和归并排序比优缺点是什么A:快速排序平均更快且是原地排序节省空间。但不稳定最坏情况性能差。归并排序稳定最坏也是 O(n log n)但需要 O(n) 的额外空间。6. 手写实战应对不同场景的代码模板在纸上或白板上书写格式清晰至关重要。6.1 标准手写模板推荐public class QuickSort { public void sort(int[] nums) { if (nums null || nums.length 2) return; quickSort(nums, 0, nums.length - 1); } private void quickSort(int[] nums, int l, int r) { if (l r) return; // 1. 终止条件 int p partition(nums, l, r); // 2. 分区 quickSort(nums, l, p - 1); // 3. 递归左 quickSort(nums, p 1, r); // 4. 递归右 } private int partition(int[] nums, int l, int r) { int pivot nums[r]; // 选最右为基准 int i l - 1; for (int j l; j r; j) { if (nums[j] pivot) { i; swap(nums, i, j); } } swap(nums, i 1, r); return i 1; } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }6.2 应对“不能修改原数组”的要求有时面试官要求返回新数组。这时需要结合归并排序的思想。public int[] sortArray(int[] nums) { if (nums null || nums.length 0) return new int[0]; return quickSort(nums, 0, nums.length - 1); } private int[] quickSort(int[] nums, int l, int r) { if (l r) return new int[0]; if (l r) return new int[]{nums[l]}; int p partition(nums, l, r); int[] left quickSort(nums, l, p - 1); int[] right quickSort(nums, p 1, r); // 合并 left, nums[p], right int[] res new int[left.length 1 right.length]; System.arraycopy(left, 0, res, 0, left.length); res[left.length] nums[p]; System.arraycopy(right, 0, res, left.length 1, right.length); return res; } // partition 方法同上但注意这会修改原数组nums需在开始前拷贝或向面试官说明。7. 从理解到精通最佳实践与扩展思考要真正掌握快速排序不能停留在背诵层面。7.1 刻意练习步骤盲写在不看任何参考的情况下定时如10分钟内完成标准快速排序代码。模拟面试向朋友或自己口述算法思想、步骤、复杂度、优缺点。变体练习尝试写出 Hoare 分区、迭代版本、针对链表排序的版本。调试与画图用一个小数组如[5,1,1,2,0,0]手动模拟每一步或使用 IDE 调试观察变量变化。7.2 工程中的注意事项虽然手写时我们关注正确性但在实际项目中小数组优化当子数组长度小于某个阈值如10时切换为插入排序因为插入排序在小数据量上常数因子更小。尾递归优化编译器可能会对尾递归进行优化但我们可以手动先递归较小的子数组以减少递归深度。private void quickSortOpt(int[] nums, int l, int r) { while (l r) { // 改为循环 int p partition(nums, l, r); // 先递归短的区间 if (p - l r - p) { quickSortOpt(nums, l, p - 1); l p 1; // 更新l循环处理右区间 } else { quickSortOpt(nums, p 1, r); r p - 1; // 更新r循环处理左区间 } } }警惕栈溢出对于极大规模数据即使优化递归也可能导致栈溢出。迭代版本是更安全的选择。快速排序的掌握程度直接反映了你对基础算法和编程思想的把握。它不仅仅是一个排序算法更是理解递归、分治、双指针、算法分析的一个完美载体。下次面试再被问到“手写快速排序”时希望你能从容不迫从思想到代码从边界到优化清晰地展示你的实力。记住清晰的思路和严谨的代码远比死记硬背更有说服力。