1. 手写快排到底在考什么面试官让你手写快速排序表面上考的是“会不会写代码”实际上是在考你三个层面的东西第一对分治思想的理解是否透彻第二写代码时对边界条件的掌控力也就是能不能一次写对第三在写完基础版之后能不能主动说出优化方向体现出“有性能意识”。很多人在准备这道题的时候有个误区背一个模板就完事了。这恰恰是面试里最容易翻车的地方。因为快排的坑全在细节里背模板的人往往是“默写”状态而不是“理解”状态面试官随便改个条件——比如数组里有大量重复元素、数据量特别大、要求不能用递归——就能把真实水平问出来。我自己在面试别人的时候也很喜欢用这道题一试深浅。能一次性写对并且清晰解释每个边界条件的人基本代码功底是过关的。而那种写完就开始含糊其辞、说不出为什么right要先走、也说不清最坏复杂度的人心里基本就有数了。所以这篇文章不打算只给一个模板而是把从最基础版本到最优版本的完整思考过程拆开每一步都讲清楚“为什么”包括循环不变量的设计、边界条件的推导、优化策略的适用场景。你看完之后应该能做到不仅写得对还能讲得通。先给出一个贯穿全文的核心结论快排的正确性取决于你是否维护了一个清晰的循环不变量快排的性能取决于你对分区均衡性和递归深度的控制。后面所有内容都是围绕这两句话展开的。2. 最基础的版本先把循环不变量立住2.1 递归结构的设计快速排序的递归结构本身非常简洁选一个基准元素把数组划分成两部分左边小于等于基准右边大于等于基准然后递归处理左右两边。这个结构可以用下面的代码骨架来表示void quickSort(vectorint nums, int left, int right) { if (left right) return; // 递归终止条件 int pivotIndex partition(nums, left, right); // 分区 quickSort(nums, left, pivotIndex - 1); // 排序左半部分 quickSort(nums, pivotIndex 1, right); // 排序右半部分 }递归终止条件left right是很多初学者容易写错的地方。有的写成left right乍一看没问题但如果分区后返回的pivotIndex恰好等于left那么递归调用quickSort(nums, left, pivotIndex - 1)就会变成quickSort(nums, left, left - 1)此时left right如果终止条件只处理了相等情况这里就会造成非法递归或者越界访问。我见过不少人在这个细节上翻车。写终止条件的时候宁可多写一个等号也不要只写相等判断这是保险的写法。2.2 分区函数的两大流派分区函数是快排的核心也是面试官最喜欢追问细节的地方。市面上常见的写法有两种挖坑法和交换法。挖坑法的思路是先把基准值存下来形成一个“坑”然后从两端交替扫描找数据填坑。它的代码风格比较紧凑但逻辑上的状态切换较多。交换法的思路则是维护两个指针一个从左往右找大一个从右往左找小找到后交换最终把基准放到正确位置。从实际使用和面试表达的角度我更推荐交换法因为它更容易用循环不变量去解释和验证。下面以交换法为例展开。int partition(vectorint nums, int left, int right) { int pivot nums[left]; // 选择最左边的元素作为基准 int i left, j right; while (i j) { // 右侧扫描找小于等于基准的元素 while (i j nums[j] pivot) j--; // 左侧扫描找大于等于基准的元素 while (i j nums[i] pivot) i; if (i j) swap(nums[i], nums[j]); } swap(nums[left], nums[i]); return i; }2.3 循环不变量这里为什么要这么写上面这段代码里的两个内层循环条件是面试里最容易被追问的地方。尤其是右侧的nums[j] pivot和左侧的nums[i] pivot它们的等号处理是不对称的这并非随意为之而是一个精心设计的循环不变量。先定义清楚循环不变量在每一轮外层循环开始时left位置的元素是基准值i左侧的所有元素都满足小于等于基准j右侧的所有元素都满足大于基准。注意这里的“小于等于”和“大于”是互补的不重叠因此在极端情况下——比如数组中所有元素都相等——指针能够正常移动不会死循环。我们来验证一个最容易出错的场景数组全部相等例如{5, 5, 5, 5}。如果右侧循环条件写成nums[j] pivot右侧指针会因为条件始终为真而一直走到超出边界最终必然越界。而写成nums[j] pivot则右侧指针遇到等于基准的值会停下来随后左侧循环也会因为nums[i] pivot而推进最终两个指针在某个位置相遇完成分区。这就防止了死循环和越界。反过来如果左侧循环条件写成nums[i] pivot左侧指针遇到等于基准的值也会停下来但两侧同时停下来的话就可能发生无限交换。所以等号放在左侧循环保证指针最终能够相交或相邻是正确的选择。这套不等式设计是快排能够正确运行的基石。面试时你如果能说出这一层“等号为什么要放在左侧”面试官多半会对你另眼相看。这比背十遍模板都管用。3. 从正确到高效四个关键优化基础版本能让人看出你具备良好的代码功底但距离面试官期待的高水平还差一步在写完基础版之后能否自然地说出优化方案。快排的优化是一个完整的问题链条每一环都有明确的动机和适用场景按顺序展开效果最好。3.1 基准值的选取为什么固定取左会被人针对基础的版本固定取区间最左边的元素做基准这在数据随机分布时通常表现不错但存在一个致命弱点当数组本身已经是有序或接近有序时每次分区只能分离出一个元素递归深度退化为O(n)时间复杂度退化为O(n²)。在面试场景中一个已经排序的数组简直是“专门来克”固定取左方案的。面试官如果想测试你的边界处理能力很可能就给你一个{1, 2, 3, 4, 5, 6, 7, 8, 9}看你能不能意识到问题所在。更极端的情况是“恶意数据”如果排序算法被用在在线系统中处理用户输入攻击者可能构造出完全有序或逆序的数组让系统掉进最坏复杂度里这本质上是一种算法层面的拒绝服务攻击。所以千万别觉得“性能退化只是理论上”的事情。解决这个问题的标准方案是随机化选基准在[left, right]区间内随机选一个下标与left位置交换然后再走正常的分区流程int randomPivotIndex left rand() % (right - left 1); swap(nums[left], nums[randomPivotIndex]);这样任何固定分布的输入都无法稳定地把我们引导到最坏情形。尽管随机化不能消除理论上的最坏复杂度但它能让最坏情形变成一个概率极低的事件。这就是为什么很多工业级实现比如STL某些版本的sort都使用随机化或近似随机化的策略。顺带提一个问题面试官偶尔会问既然随机化选基准这么好为什么还经常看到“三数取中”的方案答案是两者解决的问题角度不完全一样。随机化解决的是“对抗恶意输入”三数取中解决的是“在大多数情况下直接挑到比较好的基准”。实际工程中三数取中更常用因为它不需要调用随机数生成器也就没有随机数生成带来的额外开销和不确定性。3.2 三数取中一个硬币的两面三数取中的思路很朴素取区间最左、最右和最中间三个位置的元素找出它们的中位数作为基准。这样做的好处是对于已经有序或接近有序的数组基准直接就是中位数分区非常均衡递归深度接近最佳。实现了三数取中之后你可能会发现递归深度显著下降了。我最初自己写这个版本的时候也惊讶于它的效果对一个接近有序的大数组固定取左基准时递归深度可能达到数万层而三数取中后深度直接压缩到对数级别。这种差异不是常量级别的优化而是数量级上的差异。典型的实现方式是这样的int medianOfThree(vectorint nums, int left, int right) { int mid left (right - left) / 2; // 三个数比较返回中位数的下标 if (nums[left] nums[mid]) swap(nums[left], nums[mid]); if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[mid] nums[right]) swap(nums[mid], nums[right]); return mid; }这里有一个细节值得说出来计算中位下标时在工程上通常写成left (right - left) / 2而不是(left right) / 2。后者在left和right都很大时可能造成整数溢出这是隐蔽的Bug也是面试中可以主动展示的细节意识。但也有一个需要权衡的地方中位数的代价是至多三次比较和三次交换。对于极小的区间比如长度小于等于3三数取中的效果就没什么意义了甚至可能把代码弄复杂。所以三数取中在实践中往往跟“小区间插入排序”配合使用而不是独立存在。三数取中的另一个细节是返回的是下标还是值。有些实现返回中位数的值然后分区时与left位置交换。但需要注意如果返回的是值当数组中存在重复元素时pivot这个值可能与多个位置的值相等容易在交换时引入不必要的复杂性。我个人的建议是返回下标再显式与left交换这样代码的语义更清晰便于在头脑中维护循环不变量。3.3 小区间插入排序不要杀鸡用牛刀快排在递归到非常小的区间时表现其实并不好。原因在于递归调用本身有函数调用开销而且对于长度只有几个元素的数组分区的“均衡性优势”根本发挥不出来。这时候插排反而是更好的选择。插入排序在小规模数据上的常数非常小且对局部有序数据表现极佳。这个优化在标准库实现中非常常见比如Introsort在区间长度小于等于16时会切换到插入排序。之所以阈值经常选16是因为这是一个经过实测的平衡点小于等于16时插入排序的性能优势明显大于16时分治的优势才显现出来。实现方式很朴素就是在快排的递归函数里加一个阈值判断const int kThreshold 16; void quickSort(vectorint nums, int left, int right) { if (left right) return; if (right - left 1 kThreshold) { insertionSort(nums, left, right); return; } int pivotIndex partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex 1, right); }这里要注意一个细节插入排序的范围是[left, right]整个区间而不是小区间的局部。递归调用已经保证了当前区间是未排序的子问题所以切换排序时直接对子区间做插入排序是安全的不需要担心会破坏全局有序性。有些资料会说“阈值选10或者选20都可以”这个说法基本成立但更深一层的原因是你需要在“减少递归深度”和“增加插入排序处理的数据量”之间做权衡。插入排序最坏是O(m²)其中m是区间长度所以阈值不能太大但如果阈值太小收益又不明显。面试时你如果能说出“这个阈值本质上是一个经验参数一般推荐在16左右过大过小都会有性能回退”就已经比绝大多数候选人到位了。3.4 三路划分解决重复元素灾难前面所有讨论都隐含了一个假设数组中的元素分布比较“均匀”。如果数组中存在大量重复元素前面介绍的经典分区策略都会退化。理由很简单经典分区把等于基准的元素分散在左右两边当重复元素数量很大时分区后左右两边的规模严重不均衡递归深度可能退化为O(n)整体变为O(n²)。典型场景是对一个包含大量重复ID或状态值的数组排序比如按用户状态只有几种取值排序或者对某个枚举字段排序。这种数据在实际业务中非常常见。三路划分是专治重复元素问题的方案。它的思路是把数组分成三段小于基准的、等于基准的、大于基准的。这样一来所有等于基准的元素一次到位不需要参与后续递归大大压缩了递归规模。三路划分的实现思路是维护三个指针一个leftPtr指向小于区域的右边界一个j做动态扫描一个rightPtr指向大于区域的左边界。分区过程中把等于基准的元素拦截在中间区域pairint, int partition3way(vectorint nums, int left, int right) { int pivot nums[left]; int i left, j left 1, k right; // 循环不变量 // [left, i) 元素 pivot // [i, j) 元素 pivot // (k, right] 元素 pivot while (j k) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; j; } else if (nums[j] pivot) { swap(nums[j], nums[k]); k--; } else { j; } } return {i, k}; }这个代码的边界条件是全文中最为微妙的。j指针不断扫描未知区域i表示等于区间的左边界k表示大于区间的右边界他们三者的相对位置必须始终满足[left, i)、[i, j)和(k, right]三段互不重叠且完整覆盖原始区间。你在手写这个实现时最难的地方在于从左往右扫描时从右侧交换过来的值可能比基准还大也可能等于基准甚至可能还小于基准所以交换后不能轻易移动j需要对该位置重新判断。这一点即使是有多年经验的工程师偶尔也会在匆忙间写错。我面试别人的时候很爱让人写这个。真正理解三路划分和能完整手写出来的人要比会写基础快排的人少一个数量级。而一旦你能流畅地写出三路划分面试官对你的算法功底基本不会再有任何怀疑。三路划分最好的应用场景是配合随机化基准使用。比如在库函数中处理颜色、类别等离散值数据或者对有明显重复模式的记录进行排序。单纯的随机化选基准去掉了一个对抗性的可能但并没有消除重复元素造成的退化三路划分则从根本上保证了重复元素的处理效率。4. 非递归版本用栈代替递归面试官在快排这道题上的最后一个常见追问是如果数据规模极大递归调用会导致栈溢出怎么办这时候你需要当场改写为非递归版本。递归版快排的调用深度在最坏情况下可能达到O(n)在数据量上亿时足以让栈空间崩溃。非递归版本的核心思路是用显式的栈来模拟递归调用过程中压栈和弹栈的过程每次分区后把左右子区间的边界入栈下一次循环从栈中取出边界继续处理。实现起来并不复杂void quickSortIterative(vectorint nums) { stackpairint, int stk; stk.push({0, (int)nums.size() - 1}); while (!stk.empty()) { auto [left, right] stk.top(); stk.pop(); if (left right) continue; int pivotIndex partition(nums, left, right); // 先把较大的区间入栈再压入较小区间 if (pivotIndex - left right - pivotIndex) { stk.push({left, pivotIndex - 1}); stk.push({pivotIndex 1, right}); } else { stk.push({pivotIndex 1, right}); stk.push({left, pivotIndex - 1}); } } }这里有一个非常容易被忽视的优化点入栈的顺序。如果我们总是先把较大的区间入栈再处理较小区间栈空间的增长速度会慢得多。这个技巧本质上和最坏情况下递归深度的控制是同一个思想优先处理规模更小的子问题大问题暂时挂在栈上这样可以有效压缩栈的峰值大小。关于是否真的需要“优先处理小区间”我再稍微展开一下它并不能改变算法的时间复杂度但显著影响的是空间复杂度。最坏情况下如果每次都先压入大区间再压入小区间栈里可能积压大量未处理区间而优先处理小区间则能让栈的最大深度始终保持在O(log n)量级。面试的时候你可以主动说这个优化很多候选人根本不会想到这一层。非递归版本和递归版本在分区函数上是完全复用的所以你的基础分区函数写得好非递归版的迁移成本就会很低。5. 复杂度对比与稳定性问题快排的复杂度、稳定性是面试官追问的延伸话题属于高频附加题。我建议你把它们整理成一个清晰的知识框架而不是零散地记结论。5.1 三种复杂度情形快速排序的平均时间复杂度和最佳时间复杂度都是O(n log n)最坏是O(n²)。空间复杂度方面递归调用栈的深度平均为O(log n)最坏为O(n)。这三个指标必须能跟具体输入建立对应关系情形触发条件时间复杂度解决办法最好每次分区都恰好把区间一分为二O(n log n)-平均数据随机分布分区基本均衡O(n log n)-最坏每次分区极度不均衡如有序数组固定取左O(n²)三数取中/随机化有一点容易搞混快排的平均复杂度是O(n log n)这是在“随机输入”的假设下推导出来的数学期望。工程上为了让这个假设“无条件成立”才引入了随机化选基准让算法对任意输入都能大概率达到平均表现。5.2 稳定性问题及其代价快速排序是不稳定的排序算法。也就是说如果两个元素的值相等排序后它们的相对顺序可能会改变。很多初学者不理解“不稳”到底带来什么实际影响。举一个业务例子假设你有一批订单记录每条记录包含下单时间和订单金额两个字段。如果先按时间排好序再按金额做稳定排序那么金额相同的订单中原有“时间从早到晚”的顺序会保留下来。但如果第二次排序用了快排金额相等的订单之间的先后顺序就被打乱了你可能就得额外地加一个“时间”作为次级排序条件。面试时如果被问到“为什么快排不稳定”你要能指出问题出在分区过程中跨距离交换这一步所以相等的元素被交换到彼此的前后位置时原有的相对顺序就无法保留了。归并排序是稳定的代价是需要O(n)的额外空间。如果你在学习时把“排序稳定性”做成一张对照表把快排、归并、堆排、插入排序的稳定性都逐一对照起来看面试时被问到谁稳定谁不稳定就会答得非常快。注意面试现场如果候选人能把“快排不稳定”和“跨距离交换”之间的因果关系讲清楚这道题基本就稳了。很多人只知道结论很少能解释原因。6. 面试实战中的错误排查清单手写代码时出Bug是难免的但你要有一份自己的排查清单能在写完代码后主动检查。我在这里整理一份实际面试中最常见的错误速查表你可以收藏下来面试之前过一遍。6.1 七个高频Bug及其原因我在帮人做模拟面试和代码评审时总结出以下七类高频错误每一类的根本原因和排查方向都不相同错误现象根本原因排查方向死循环分区循环条件中的等号处理不对称两侧指针同时卡住检查和的搭配数组越界内层循环缺少i j保护或递归终止条件只写了left right检查边界条件是否覆盖left right排序结果错误基准交换位置选错pivotIndex返回的不是基准最终位置仔细推导分区后基准应该落在哪个位置大量重复元素时性能急剧恶化经典分区无法有效处理等于基准的元素使用三路划分递归栈溢出数据规模极大且分区极不均衡或未使用非递归版本三数取中/随机化非递归分区后左右区间重叠分区函数返回值与递归调用的区间范围不一致检查pivotIndex 1和pivotIndex - 1是否正确元素被丢失交换操作在指针重合时误交换基准值在swap前仔细检查指针状态6.2 我在实际写代码时踩过的坑第一个是“右侧扫描条件写反”的坑。有一段时间我习惯性地把右侧循环写成while (i j nums[j] pivot) j--;理由是“找比基准小的数”从语义上理解为“大于等于基准就跳过”。这个逻辑本身是对的但在全等元素场景下左右两侧都会因为条件为真而各自移动最终一切正常可一旦基准值非常小比如数组中所有元素都大于基准那么左侧指针会一直向右移动最后i会停在right位置然后swap(nums[left], nums[i])会把基准和最大值交换排序结果错得一塌糊涂。第二个是“递归区间写错”的坑。分区函数返回的pivotIndex已经放在了正确的位置所以递归调用应该排除它本身即quickSort(nums, left, pivotIndex - 1)和quickSort(nums, pivotIndex 1, right)。我见过有同学把区间写成[left, pivotIndex]和[pivotIndex, right]这会导致基准元素反复参与递归最后排序结果莫名其妙而且很难一眼看出来问题出在哪里。第三个是在非递归版本里忘记压栈边界条件的坑。如果你在循环里弹出一个区间但没判断left right就继续处理那么当区间长度为1时分区函数仍会对一个单元素区间做交换操作虽然通常不会出错但会造成多余计算。更重要的是如果边界判断缺失空区间也会被压入栈中造成无限循环这是典型的手写代码才能踩出来的坑。6.3 面试中的主动自查策略写完代码后不要默默交给面试官而是主动做两个自查动作这会显得你非常有工程素养。第一个动作是画小数组的推演图。选一个长度为5的数组在草稿纸上手动推演一遍分区过程确认指针的每一步移动都符合预期。这个过程能在1分钟内做完但能挡住80%以上的低级错误。第二个动作是说明你的测试用例。你可以这样说“我可以用三个用例来验证这段代码全随机数组、完全有序的数组、全部相等的数组。全随机数组验证常规功能有序数组验证最坏情况不会爆栈全相等数组验证不会死循环。”如果面试官听完这句基本就知道你肚子里是有货的。我还想再补一个自查点如果你的分区函数选择的是交换法一定要注意最后一步是swap(nums[left], nums[i])而不是swap(nums[left], nums[j])。由于两个指针最终相遇的位置可能落在i也可能在j附近用错一个变量就会让基准落到错误的位置。我在代码评审中遇到过的错误里这个是最隐蔽的因为小数据样例下偶尔也能跑出正确结果。7. 完整的最优版本一次集成全部优化至此我们已经把快排从基础版本一路优化到了能应对几乎所有场景的最优形态。现在把它们集成在一起构成一个完整的、可以作为面试“标准答案”的代码const int kThreshold 16; void insertionSort(vectorint nums, int left, int right) { for (int i left 1; i right; i) { int key nums[i]; int j i - 1; while (j left nums[j] key) { nums[j 1] nums[j]; j--; } nums[j 1] key; } } int medianOfThree(vectorint nums, int left, int right) { int mid left (right - left) / 2; if (nums[left] nums[mid]) swap(nums[left], nums[mid]); if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[mid] nums[right]) swap(nums[mid], nums[right]); swap(nums[mid], nums[left]); // 中位数放到最左 return nums[left]; } pairint, int partition3way(vectorint nums, int left, int right) { int pivot medianOfThree(nums, left, right); int i left, j left 1, k right; while (j k) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; j; } else if (nums[j] pivot) { swap(nums[j], nums[k]); k--; } else { j; } } return {i, k}; } void quickSort(vectorint nums, int left, int right) { if (left right) return; if (right - left 1 kThreshold) { insertionSort(nums, left, right); return; } auto [lt, gt] partition3way(nums, left, right); quickSort(nums, left, lt - 1); quickSort(nums, gt 1, right); }这里有一个设计上的取舍需要说明三路划分本身已经能处理大量重复元素小区间插入排序则负责处理递归到极小区间时的常数开销三数取中保证所有数据形态下基准都比较接近中位数。三个优化方向互补而不是互相替代。如果你在面试现场需要跟面试官讨论这套代码的复杂度可以直接说平均O(n log n)最坏O(n²)概率极低空间O(log n)。我想提醒一句能够有条件地讲解这套代码本身比背下来更重要。面试官很可能会说“把三数取中去掉还能保证正确性吗”或者“分区这里能不能改成单指针单方向扫描”。你能不能在修改中保持正确直接反映出你是否真正理解了代码底层的循环不变量。8. 一些从实际面试中总结的真心话到了文末说一点不太会在教科书里出现但非常实际的经验。第一件事面试的时候千万别一上来就写最优版本。先写下朴素但正确的基础快排把核心逻辑讲明白然后再逐步提出优化方向。这个递进过程本身就是一种展示它反映的是“从正确到高效”的真实思考过程而不是背答案。你如果一上来就写三路划分三数取中插入排序的终极版面试官反而会怀疑你只是在背一个标准模板。第二件事手写代码时字迹和布局其实会影响面试官的判断。这听起来有点外貌歧视但事实就是如此。分区函数里指针的初始位置、循环条件、递归边界尽量对齐排列方便面试官跟随你的思路走。如果你写得杂乱无章面试官在顺着你的代码找逻辑时会额外消耗精力容易产生“这代码有问题”的先入为主印象。这不是教你去取巧而是说码风本身就是工程素养的一部分。第三件事如果某个边界条件你当时没想清楚千万不要沉默硬写。可以大大方方地对面试官说“这里我需要花一点时间验证一下边界条件。”绝大多数面试官都能接受这种坦诚因为你在展示的是严谨性而不是试图蒙混过关。真正减分的行为是写了错误代码、被问了又说不出为什么这才是最糟糕的。我面试过不少候选人通常能完整推演这套思考链条的人无论最终是否拿到offer面试后都能对快排留下一个系统性的理解而不是零散的碎片。如果这篇文章能帮你建立同样清晰的框架那么你面对这道题时就不再是“背了一个答案”的状态而是真正“掌握了一个算法”。