在笔试或面试中手写快速排序算法是检验开发者基本功的经典考题。很多同学虽然理解其“分治”思想但在白板或纸上手写时却常常卡在边界条件、递归终止或分区细节上导致代码逻辑混乱甚至无法运行。本文将系统拆解快速排序的手写核心从应试角度出发提供一套清晰、易记、不易出错的代码模板和推导思路让你在紧张的考核中也能稳定输出正确代码。1. 快速排序核心思想与应试价值快速排序是一种高效的、基于“分治”策略的排序算法。其核心思想可以概括为“挖坑填数”或“双指针交换”通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分的关键字小然后递归地对这两部分记录继续进行排序以达到整个序列有序。为什么面试官钟爱考快速排序考察基础算法能力它融合了递归、双指针、分治等核心编程思想。考察代码严谨性边界条件如递归终止、指针移动极易出错能有效区分候选人的代码功底。考察优化思维面试官常会追问如何优化如随机化基准、三数取中、小数组切换插入排序从而考察知识深度。手写难度适中代码量适中既能在短时间内写完又能充分暴露问题。对于应试者而言掌握一个逻辑清晰、易于记忆且鲁棒的代码模板至关重要。2. 环境与语言版本说明本文代码示例将使用Java和Python两种主流语言进行展示以适应不同技术栈的面试场景。重点在于算法逻辑本身语言特性为辅。Java: 示例基于 Java 8 及以上版本主要展示数组操作和递归。Python: 示例基于 Python 3.x利用其列表切片和简洁语法也会展示原地排序版本。核心思想无论使用哪种语言快速排序的分区逻辑是相通的。理解并记忆分区过程是手写成功的关键。在笔试中请务必遵循题目要求的编程语言。如果未指定选择你最熟悉的一种。3. 算法原理与手写拆解快速排序的步骤可以明确分为两部分分区Partition和递归Recursive。手写时应集中精力先写好分区函数。3.1 分区过程详解以 Lomuto 分区方案为例Lomuto 分区方案是较为直观、易于手写的一种。我们以数组arr的区间[left, right]为例。分区目标选取一个基准值pivot将数组划分为两部分使得左边元素 ≤ pivot ≤ 右边元素并返回基准值的最终位置。手写步骤与记忆口诀定基准选择最右侧元素arr[right]作为基准值pivot。设指针设置一个“小区间”指针i left - 1。它的含义是i及其左边的所有元素都是小于等于pivot的。扫描交换用另一个指针j从left遍历到right - 1。如果arr[j] pivot说明这个元素应该属于“小区间”。先将i右移一位然后交换arr[i]和arr[j]。这样i始终指向“小区间”的最后一个元素。如果arr[j] pivot不做操作j继续后移该元素自然留在“大区间”。基准归位遍历结束后i1的位置就是pivot应该放入的位置。交换arr[i1]和arr[right]即最初的基准值。返回位置返回i1作为本次分区后基准值的索引。为什么选择 Lomuto 方案应试逻辑线性易于理解和记忆代码模板固定不易在边界上出错。虽然 Hoare 分区方案可能效率稍高但边界条件更复杂手写时容易陷入死循环。3.2 递归过程分区函数完成后递归过程就非常直观了调用分区函数得到基准位置pivot_index。递归排序左半部分[left, pivot_index - 1]。递归排序右半部分[pivot_index 1, right]。递归终止条件当left right时说明当前区间没有元素或只有一个元素无需再排序直接返回。这是手写时最容易遗漏的一步4. 完整手写代码模板与逐行分析下面提供可直接用于应试的代码模板并附上关键注释。4.1 Java 实现模板public class QuickSort { /** * 快速排序入口函数 * param arr 待排序数组 */ public static void quickSort(int[] arr) { if (arr null || arr.length 1) { return; // 边界检查体现代码健壮性 } sort(arr, 0, arr.length - 1); } /** * 递归排序函数 * param arr 待排序数组 * param left 当前区间左边界 * param right 当前区间右边界 */ private static void sort(int[] arr, int left, int right) { // 递归终止条件必须写 if (left right) { return; } // 进行分区并获取基准值位置 int pivotIndex partition(arr, left, right); // 递归排序左半部分 sort(arr, left, pivotIndex - 1); // 递归排序右半部分 sort(arr, pivotIndex 1, right); } /** * Lomuto 分区方案 * param arr 待分区数组 * param left 区间左边界 * param right 区间右边界基准值位置 * return 基准值最终位置 */ private static int partition(int[] arr, int left, int right) { // 1. 选择最右侧元素作为基准值 int pivot arr[right]; // 2. 初始化小区间指针 i int i left - 1; // 3. 遍历区间 [left, right-1] for (int j left; j right; j) { // 如果当前元素小于等于基准值 if (arr[j] pivot) { i; // 扩大小区间 // 交换 arr[i] 和 arr[j] swap(arr, i, j); } // 如果 arr[j] pivot, j 继续后移什么也不做 } // 4. 将基准值放到正确位置 (i1) swap(arr, i 1, right); // 5. 返回基准值位置 return i 1; } /** * 交换数组中两个元素 * 这是一个好习惯使主逻辑更清晰 */ 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}; System.out.println(排序前: Arrays.toString(arr)); quickSort(arr); System.out.println(排序后: Arrays.toString(arr)); // 输出 // 排序前: [10, 7, 8, 9, 1, 5] // 排序后: [1, 5, 7, 8, 9, 10] } }4.2 Python 实现模板原地排序版本Python 因其语法简洁常被要求手写。以下是符合算法原理的原地排序版本而非利用列表切片的简单写法面试官可能要求展示分区过程。def quick_sort(arr, left, right): 快速排序 (原地修改) :param arr: 待排序列表 :param left: 当前区间左索引 :param right: 当前区间右索引 # 递归终止条件 if left right: return # 分区操作获取基准位置 pivot_index partition(arr, left, right) # 递归排序左半部分 quick_sort(arr, left, pivot_index - 1) # 递归排序右半部分 quick_sort(arr, pivot_index 1, right) def partition(arr, left, right): Lomuto 分区方案 :return: 基准值最终位置 # 1. 选择最右侧元素为基准 pivot arr[right] # 2. 初始化小区间指针 i i left - 1 # 3. 遍历 [left, right-1] for j in range(left, right): if arr[j] pivot: i 1 # 交换 arr[i] 和 arr[j] arr[i], arr[j] arr[j], arr[i] # 4. 将基准值放到正确位置 arr[i 1], arr[right] arr[right], arr[i 1] # 5. 返回基准位置 return i 1 # 测试用例 if __name__ __main__: test_arr [10, 7, 8, 9, 1, 5] print(f排序前: {test_arr}) quick_sort(test_arr, 0, len(test_arr) - 1) print(f排序后: {test_arr}) # 输出 # 排序前: [10, 7, 8, 9, 1, 5] # 排序后: [1, 5, 7, 8, 9, 10]手写要点回顾先写分区函数partition这是核心。再写递归函数sort/quick_sort注意终止条件left right。最后写入口函数进行空数组或单元素数组的边界处理。交换操作可以单独写成swap函数使逻辑更清晰。5. 手写过程中的常见错误与排查思路在笔试或面试手写时以下几个错误最高频错误现象可能原因排查与纠正栈溢出递归无法终止递归终止条件写错或漏写例如写成if (left right)但处理单元素区间时出错或根本没写终止条件。强制检查在写递归函数时第一行就写下if (left right) return;。排序结果不正确部分有序或完全错误1. 分区函数逻辑错误指针移动或交换条件不对。2. 递归调用区间错误例如左区间写成了[left, pivotIndex]包含了基准值。1.单步模拟用一个小数组如[3,1,2]在纸上手动走一遍分区过程。2.检查递归调用左区间必须是[left, pivotIndex-1]右区间是[pivotIndex1, right]。数组下标越界1. 在partition的for循环中j的遍历范围错误包含了right。2. 递归调用时pivotIndex-1或pivotIndex1可能超出[left, right]范围但递归终止条件会处理。1.牢记循环范围j从left到right-1因为right是基准。2.信任终止条件只要终止条件正确递归调用传递的边界是安全的。对于已排序或逆序数组效率极低总是选择最左或最右元素作为基准导致分区极度不平衡退化为 O(n²) 时间复杂度。向面试官说明这是经典问题可以通过“随机选择基准”或“三数取中法”优化。即使手写不实现也要能说出这个知识点。应试策略写完代码后务必用一个小例子在脑中或纸上模拟运行一遍这是发现逻辑错误最有效的方法。例如用[5, 2, 3]测试。6. 进阶追问与最佳实践如何体现深度当面试官看到你正确写出基础版后常会进行追问。提前准备这些点能大大加分。6.1 时间复杂度与空间复杂度分析时间复杂度平均情况 O(n log n)每次分区大致均匀。最坏情况 O(n²)每次分区极不均匀如数组已有序且总选最值为基准。这是快速排序的主要缺点。最好情况 O(n log n)每次分区都能对半划分。空间复杂度主要取决于递归调用栈的深度。平均情况 O(log n)。最坏情况 O(n)退化为链表式的递归。6.2 如何优化快速排序随机化基准在分区前随机选择[left, right]中的一个元素与arr[right]交换再执行标准流程。这能极大避免因输入数据特性导致的最坏情况。// 在 partition 函数开头添加 int randomIndex left rand.nextInt(right - left 1); swap(arr, randomIndex, right); // 将随机选中的元素换到最右端作为基准 // 然后再执行原来的 partition 逻辑三数取中法取left、mid、right三个位置元素的中位数作为基准值并交换到right位置。这比纯随机更稳定。小数组切换插入排序当递归到子数组规模较小如长度 15时快速排序的递归开销可能比排序本身还大。此时切换为插入排序能提升整体性能。private static void sort(int[] arr, int left, int right) { // 优化小数组使用插入排序 if (right - left 1 INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } // ... 原来的分区和递归逻辑 }尾递归优化递归调用sort时先处理较短的那部分区间较长的区间通过循环迭代。这可以将最坏情况下的栈深度降至 O(log n)。了解即可手写要求不高6.3 快速排序的稳定性与适用场景稳定性快速排序是不稳定的排序算法。因为在分区过程中相等的元素可能会因为交换而改变相对次序。例如对[3a, 2, 3b, 1]用a,b区分相同值排序结果中3a和3b的顺序可能改变。适用场景适用于数据量大的内存排序对缓存利用友好。是许多语言标准库如 JavaArrays.sort()对基本类型的排序实现基础。不适用于对稳定性有要求的场景也不适合链表结构分区操作在链表上低效。7. 应试技巧与临场发挥建议先理清思路再动笔用30秒在脑中或草稿纸上画出分区过程的示意图明确i,j,pivot的职责。从核心到外围先写下partition函数的骨架参数、返回值、基准选择、循环再填充内部交换逻辑。然后写递归函数最后写入口。注释关键步骤在代码旁简要注释如// 1. 选择基准、// 2. 初始化指针。这既能帮助自己理清思路也能向面试官展示逻辑。主动进行测试写完代码后主动说“我用一个简单例子测试一下比如数组[4, 2, 5, 1]。”然后逐步解释执行过程。这展示了你的调试能力和信心。准备后续讨论当代码正确后可以主动提及“这是一个基础实现。在实际应用中我们可能会通过随机选择基准来避免最坏情况或者对小数组使用插入排序来优化。”这引导面试进入你熟悉的深度讨论区。保持代码整洁即使是在纸上也尽量对齐缩进划分函数区域。清晰的卷面是专业性的体现。掌握快速排序的手写不仅仅是背下一段代码更是对分治思想和严谨编程的一次训练。建议在理解上述模板的基础上脱离本文在白纸上独立默写几次直到能流畅、准确地完成。这将使你在未来的技术面试中面对这道经典考题时游刃有余。