快速排序原理与真题拆解：从手写模板到非递归与TopK

手写快速排序几乎可以和链表反转并列成为技术面试里的钉子户题目。我记得第一次完整写完这段代码是在很多年前当时只理解到“选一个数小的放左边大的放右边”真要落笔才发现指针怎么移动、递归从哪里切、两个 while 条件里的等号到底要不要全都成了送命题。今天只聊一件事快速排序以及它背后那些真题。无论你是在准备笔试、背面试八股还是想把手写快排练到半分钟不出错都可以照着下面的思路过一遍。这篇文章会把原理、代码、非递归写法、常考题型以及我踩过的坑全部拆开讲尤其会把“真题到底怎么考”这件事说透。1. 为什么快速排序是笔试题里的钉子户1.1 一个考点能串起多少知识点我在参加过的技术面试和坐在面试官位置上的经历里几乎可以这么下结论只要和算法沾边的岗位快速排序要么是直接考题要么是追问链的起点。它的出场率高得离谱和链表反转、二叉树遍历属于同一梯队。之所以这么高频是因为它牵涉的知识点太密集了分治思想、递归函数的写法与终止条件、数组上的双指针操作、循环不变量、基准元素选择、时间复杂度推导、空间复杂度递归栈深、稳定性分析、甚至随机化算法和工程优化技巧。面试官通过一道快排题基本就能判断一个人的算法基本功是否扎实因为很多隐藏细节都能从代码里被挖出来。1.2 真题考察的两个层次会写与会优化大多数人的准备只停留在“能背出代码”。但真题很少只问代码本身。我整理了一下这些年见过的快排真题基本分两个层次。第一层是基础代码题要求你写出可运行的升序或降序排序能正确处理空数组、单元素、重复元素第二层是进阶追问比如“递归改成非递归怎么写”“最坏情况何时出现、怎么避免”“如何用它求数组的第K大元素”“链表能不能快排”。如果你只准备了第一个层次遇到第二个层次就可能卡壳。所以这篇文章的编排思路是先解决底层原理再给三套可复现的代码然后专门拆解非递归写法最后用一个章节梳理真题里的六大题型。你把这条线走完快排这道题基本就能做到进退自如。2. 原理拆解分治、分区和基准选择2.1 分治思想用整理书架理解快排我习惯把快速排序比喻成整理书架。桌子上有一堆乱书你随手拿一本出来当参照物比如一本厚词典然后把所有书分成两堆比词典薄的一堆、比词典厚的一堆。词典自己放到两堆中间它已经找到了最终位置。接下来对两堆书分别重复这个动作直到每堆只剩一本或零本。这就是分治Divide and Conquer把大问题拆成两个规模更小的子问题分别解决子问题的解合起来就是原问题的解。快速排序是分治思想最经典的应用之一理解它之后再看归并排序、二分查找、树上的递归思路都是相通的。分治本身不难理解真正难的是“分区”这一步怎么写得又对又快因为所有快排的翻车现场几乎都发生在 partition 里。2.2 Partition 过程逐行拆解一个具体例子快速排序的核心在分区Partition选一个基准元素 pivot把小于它的元素移到左边大于等于它的元素移到右边之后基准就落在最终位置然后递归处理左右两个区间。以数组 [49, 38, 65, 97, 76, 13, 27, 49] 为例假设基准取首元素49使用经典的“填坑法”先用变量 pivot 保存49此时索引0成为“坑”右指针 j 从末尾向左找小于49的元素找到27索引6把它填到索引0数组变成 [27,38,65,97,76,13,27,49]此时索引6成为新坑左指针 i 从0向右找大于49的元素找到65索引2把它填到索引6数组变成 [27,38,65,97,76,13,65,49]此时索引2成为新坑继续从右向左找小于49的元素此时 j 从索引6继续左移跳过65找到13索引5填到索引2数组变成 [27,38,13,97,76,13,65,49]坑移到索引5继续从左向右找大于49的元素找到97索引3填到索引5数组变成 [27,38,13,97,76,97,65,49]坑移到索引3继续从右向左找小于49的元素右指针一路左移当 j 越过 i 时循环结束把 pivot 填回当前坑位索引3最终得到 [27,38,13,49,76,97,65,49]。第一趟结束时基准49落在索引3左侧 [27,38,13] 全部小于49右侧 [76,97,65,49] 全部大于等于49。接下来递归排序左右区间即可。从这个例子能直观看到每一趟分区后至少有一个元素基准确定了最终位置所以排序一定会收敛。2.3 基准选择的门道首元素、随机化、三数取中上面的演示用的是直接取首元素作为基准这是最简单也最容易写错的写法。后面第5章会讲到如果数组本身有序固定取首元素会让分区严重失衡复杂度退化到 O(n^2)。工程上常用的改进思路有三个随机选基准在区间内随机选一个位置和首元素交换后再进入分区逻辑。通过概率保证最坏情况几乎不会出现三数取中取首、中、尾三个元素的中位数作为基准能在多数场景下让分区更均衡递归小数组切换插入排序当区间长度小于某个阈值比如16时直接用插入排序收尾减少递归调用开销。实际面试时能主动提出这三种策略并解释它们为什么能改善退化情况通常会让面试官觉得你不是在背模板而是真的理解过这个算法。3. 真题手写代码三种语言一次吃透3.1 Java 递归实现与边界条件分析先给Java实现这是面试中最常用的版本。我把分区逻辑封装成一个方法避免在递归时把代码揉成一团public static void quickSort(int[] arr, int left, int right) { if (left right) return; int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; return i; }有几个地方是真题特别喜欢检查的递归终止条件是 left right不是 left right。因为如果递归区间参数计算错误可能出现 left right这时候不终止就会无限递归内层两个 while 都要带 i j 条件否则指针会越界访问右指针找的是小于 pivot 的值左指针找的是大于 pivot 的值等于 pivot 的元素先原地保留循环结束后再由分区结果自然归类最后把 pivot 放回 i 的位置并返回这个索引这个索引就是下一轮递归的分割点。3.2 C 语言实现指针操作与内存注意C语言版本和Java版本逻辑基本一致差别在于边界和内存管理需要你自己负责void quick_sort(int arr[], int left, int right) { if (left right) return; int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; quick_sort(arr, left, i - 1); quick_sort(arr, i 1, right); }注意这里的 right 是“最后一个元素的下标”不是数组长度。如果调用quick_sort(arr, 0, n - 1)递归时传的是 i - 1 和 i 1新手最常见的错误是把 n 传进去导致最后一趟访问 arr[n] 越界。另外C语言数组作为参数会退化成指针函数内部不能用sizeof(arr) / sizeof(arr[0])求长度正确做法是在调用前把 n-1 传进来。这个点虽然看起来基础但笔试白板上写代码时很容易忽略。3.3 Python 实现优雅但容易踩坑Python 写快排最容易但也最容易在面试中暴露对递归深度的忽视def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right)Python 默认递归深度大约是1000层如果数组长度上万且分区不理想会直接抛 RecursionError。应试时除了用sys.setrecursionlimit提高上限更稳妥的解法是把递归版本改成非递归版本这正好引出第4章的内容也能向面试官展示你处理工程问题的能力。3.4 手写代码时的评分点作为面试官视角我观察候选人写快排时会重点看这几个维度边界条件是否正确左指针是否有可能越过右指针递归是否可能在单元素或空区间上继续执行分区代码是否有明显越界或死循环风险递归参数是不是围绕 pivotIndex 分成了两个互不相交的子区间是否能解释每一行代码在做什么而不是只会背模板。真题中常见的降序要求只要把两个比较符号反过来即可arr[j] pivot改成arr[j] pivot同时arr[i] pivot改成arr[i] pivot。但要注意别只改一处只改一半会导致分区逻辑错乱排序结果完全不对。4. 非递归快速排序面试官的进阶追问4.1 为什么真题里会出现非递归写法我面试过的人里能流利写出递归版快排的大概占六成能继续写非递归版的不超过两成所以这道进阶题的分层效果非常明显。非递归写法的价值有两个方面。第一它考察你是否真正理解递归的本质——递归调用在系统层面其实就是函数栈的压栈与出栈手动用栈模拟这个过程说明你对执行模型有直觉。第二递归版快排在极端场景下可能 StackOverflowError比如数组已经有序、基准又固定取首元素时递归深度会达到 n系统函数调用栈很容易爆掉。改成显式栈操作可以避免系统调用栈过深虽然核心算法的时间复杂度并没有变化。4.2 用栈模拟递归从代码到原理解析非递归版的核心是把“待排序区间”存进栈循环弹出区间处理处理完再把新生成的子区间压入栈public static void quickSortIterative(int[] arr) { if (arr null || arr.length 2) return; Dequeint[] stack new ArrayDeque(); stack.push(new int[]{0, arr.length - 1}); while (!stack.isEmpty()) { int[] range stack.pop(); int left range[0]; int right range[1]; if (left right) continue; int pivotIndex partition(arr, left, right); stack.push(new int[]{left, pivotIndex - 1}); stack.push(new int[]{pivotIndex 1, right}); } }这里的 partition 完全复用第3章的填坑法不需要额外改动。有两个设计点值得说明为什么用Dequeint[]而不是两个独立栈因为每个区间有两个边界用一个长度为2的数组打包逻辑上更直观也不容易弄混左右边界为什么要在出栈后检查 left right因为分区后可能产生空区间或单元素区间这些区间不需要再处理continue 一下就能跳过。压栈顺序本身没有严格要求先压左区间还是先压右区间只影响待处理区间的弹出顺序不影响最终排序结果。如果面试官问“这个栈最多会存多少个区间”可以回答最坏情况下 O(n)平均 O(log n)这是一个能加分的细节。4.3 手写非递归的易错细节第一个易错点忘记把 partition 返回的基准索引排除掉。正确做法是压入 left 到 pivotIndex-1 和 pivotIndex1 到 right 两个区间如果压成 left 到 pivotIndex基准元素会被反复处理极端情况下可能造成栈内存持续增长。第二个易错点Java 中ArrayDeque不能 push null如果传入空数组会直接异常所以函数开头要判空。第三个易错点出栈后要先检查 left right 再继续避免对已经完成的区间重复分区否则虽然结果不会错但会产生大量无效操作。5. 真题六大题型逐一拆解5.1 手写代码题边界条件怎么答不丢分题目示例“设计一个快速排序算法将长度为 n 的整数数组升序排列要求平均时间复杂度 O(n log n)写出核心代码并说明递归深度。”这种题的隐藏考点有三个第一输入参数的语义要统一right 是末位下标还是长度前后必须一致第二递归退出条件是否覆盖 left right 的情况第三是否在递归调用前把基准索引位置排除。标准答案里建议加入空数组和单元素数组的快速返回。即使主函数里已经保证 n 2写出来也能体现你的防御性编程习惯。把这个习惯带进代码面试官对你的印象会和只会默写模板的候选人明显不同。5.2 过程推演题一趟排序结果必须写对题目示例“对数组 [49, 38, 65, 97, 76, 13, 27, 49]取第一个元素为基准写出第一趟排序后的数组和基准所在位置。”这类题在笔试填空题里很常见。按照第2章的填坑法第一趟结果是 [27, 38, 13, 49, 76, 97, 65, 49]基准49落在索引3。推演时最容易犯的错是忽略末尾的49。注意这里有两个49末位的49在第一趟中不会被交换最终基准的右侧含有一个等于49的元素。这正好呼应后面关于稳定性的讨论。这道题也常被改成让基准跑向末位或者要求用随机基准但只要抓住“每一趟结束基准在中间左边都比它小、右边都不小于它”的核心就不会推错。5.3 复杂度问答题最坏情况与退化原因面试经典问法“快速排序的时间复杂度是多少最坏情况下怎么退化如何规避”标准回答分三层平均和最坏平均 O(n log n)最好 O(n log n)最坏 O(n^2)发生在每次分区极度不均衡时。比如数组已经有序、基准固定取首元素这样每次分区只减少一个元素递归树变成一条链比较次数约等于 n (n-1) ... 1空间复杂度递归栈深度平均 O(log n)最坏 O(n)非递归版的空间也是 O(n)因为需要显式栈存区间但它不受系统函数栈深限制规避方法随机选基准、三数取中、小区间插入排序、双路/三路快排处理大量重复元素。如果面试官追问“平均 O(n log n) 怎么来的”可以简要说明每次 partition 的代价是线性级的理想情况下递归树高度为 O(log n)所以总代价约为 n log n最坏情况下退化成链比较次数是等差数列求和的结果。能把推导逻辑讲清楚比直接抛结论更有说服力。5.4 稳定性与额外空间考点快速排序是不稳定排序。给出具体反例[3, 3a, 1]选基准3第一趟做完后两个3的相对顺序可能发生变化取决于分区交换的方向和时机。稳定性在真题里怎么考常见问法是“快排稳定吗为什么归并排序为什么稳定”你需要现场演示一遍。额外空间考点对应的是原地排序与递归栈空间的区别快排是原地排序算法不需要额外数组但递归需要 O(log n) 到 O(n) 的函数栈空间归并排序需要额外 O(n) 辅助数组并且是稳定的。维度快速排序归并排序平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n^2)O(n log n)空间复杂度O(log n)~O(n)递归栈O(n)辅助数组稳定性不稳定稳定适用场景数组、内存排序链表、外部排序这张对比表要记牢因为它几乎能覆盖所有围绕快排的理论追问。5.5 变种题TopK 与第 K 大元素快速选择真题很少只考排序本身更多是借快排的 partition 方法解决衍生问题。最典型的是“求无序数组第K大元素”或“最小的K个数”。核心思路是快速选择Quick Select。每轮 partition 后基准的下标 pivotIndex 已经确定。如果它恰好是目标位置直接返回如果比目标位置小就去右侧区间继续找反之去左侧。每一轮只需要处理一边所以平均时间复杂度是 O(n)比先排序再取值 O(n log n) 快得多。Java 参考实现public static int quickSelect(int[] arr, int left, int right, int target) { if (left right) return arr[left]; int pivotIndex partition(arr, left, right); if (pivotIndex target) return arr[pivotIndex]; else if (target pivotIndex) return quickSelect(arr, left, pivotIndex - 1, target); else return quickSelect(arr, pivotIndex 1, right, target); }求第K大时可以继续用升序 partition调用时传target arr.length - K。例如数组 [3,2,1,5,6,4]第2大元素是5升序排序后5在索引4而arr.length - 2 4。这种方式复用代码更少出错面试时推荐优先考虑。5.6 综合设计题链表快排思路链表上的快排是八股之外的高频变种。思路和数组快排一致但链表不能随机访问所以只能取链头元素作为基准遍历剩余节点拆成两条链小于基准的链和大于等于基准的链然后递归排序两条链最后拼接。注意两个坑链表快排需要小心处理尾节点拼接时要避免形成环对链表来说归并排序通常更稳定也更自然因为链表的随机访问受限归并排序的空间复杂度反而不依赖辅助数组的随机索引。所以面试官考链表快排时你回答“我会先考虑归并排序因为链表结构天然适合如果必须用快排就用链头分区加递归合并”反而能够体现更全面的算法视野。6. 踩坑笔记从死循环到栈溢出6.1 指针移动顺序错误导致死循环我见过大量候选人把两个 while 的内部条件写反while (i j arr[i] pivot) i--; while (i j arr[j] pivot) j;哨兵方向一反过来分区根本没意义数组越界、死循环立刻出现。正确顺序是右指针 j 先向左移动寻找小于基准的元素左指针 i 再向右移动寻找大于基准的元素。方向不能乱否则基准无法落到正确位置。还有一个细节内层 while 的条件必须包含 i j否则当数组所有元素都满足条件时指针会一直移动越过边界访问到数组外部的未定义内存导致崩溃或者异常结果。6.2 递归区间写错导致 StackOverflowError把递归调用写成quickSort(arr, left, pivotIndex)而不排除基准时基准元素永远留在待处理区间里递归无法收敛最终栈溢出。正确写法是分别传 left 到 pivotIndex-1 和 pivotIndex1 到 right。核心认知是每经过一次分区基准元素的位置就永远确定了递归排列左右子区间时都不应该再碰它。如果写错即使没崩溃排序结果也可能是错的只是在小数组上不容易被发现。6.3 相同元素数组的分区塌缩当数组里的元素全部相同时固定取首元素的快排会发生“分区塌缩”每次 partition 后基准虽然落在某个位置但左右子区间划分严重失衡一个为空、一个只减少一个元素整体复杂度退化到 O(n^2)。实际工程里解决这个问题常用“双路快排”两个指针同时向中间移动遇到等于基准的元素也进行交换让相等的元素尽量均匀分布在两侧更彻底的做法是“三路快排”把数组划分成小于、等于、大于三部分大量重复元素时性能最佳。真题遇到“给你一个全部相等的数组快排要跑多久”时能说出这个优化思路基本就能过关。别直接说“我不知道”哪怕说不清细节也应该提一句“固定基准的普通快排会退化需要双路或三路优化”。6.4 一个完整的调试反思案例我之前带新人时有个同学写的快排在本地一跑就 StackOverflowError。排查后发现两个问题叠加。第一个问题递归终止条件写成了if (left right) return没有覆盖 left right 的情况一旦分区后产生空区间递归就不会停下来第二个问题调用时把 n 当作 right 传入最后一次递归访问了 arr[n]直接越界报错。当时他非常困惑因为代码结构看起来完整。后来我们一步一步在纸上推演了一个长度为2的数组才发现右侧区间递归到空区间时终止条件没有拦住而越界访问又进一步破坏了内存。这个案例说明快排细节里没有“看起来差不多”指针编号、边界语义、等号取舍都要一板一眼。我的经验是写完快排后不要急着跑先在纸上用 [3,1,2]、[5,3,8,1,9,2,7] 这类小数组手动模拟一遍再把递归区间、终止条件、指针移动全部标记清楚能极大降低出错概率。最后说点个人体会。我带过的很多候选人在快排这道题上翻车几乎都不是因为不懂分治而是细节没有形成肌肉记忆边界条件、基准选取、指针移动方向、等于号的取舍任何一个地方放松警惕写出来的代码就是一颗定时炸弹。我的建议是先把第3章里的填坑法模板练到不用过脑就能写对再自己动手推演两遍真题过程特别是有重复元素和有相等值的数组。等到你能在五分钟内写出无 bug 的快排和非递归版本面试中再遇到快排相关的任何追问你都不会慌。