到O(n log n)的进阶之路)
1. 从一道题看面试官的真正意图先说个可能让不少人意外的事实快速排序几乎是面试中出现频率最高、但通过率最低的“送分题”。很多候选人觉得“快排我背过”结果一落笔就露馅——要么写出的代码在[1, 2, 3, 4, 5]这种有序数组上直接退化到 O(n²)要么 partition 的边界条件一改就崩要么被追问“你的快排稳定吗”“为什么库函数不用快排”时支支吾吾。作为写过多年 C、也坐在面试官那一侧看过不少候选人现场写代码的人我可以负责任地告诉你面试官让你手写快排绝不是为了考察你会不会背代码而是想通过这一道题看你的工程思维、边界意识和对算法本质的理解。一个能把快排从“基础版”一路演进到“最优版”的候选人通常对指针操作、递归开销、数据分布敏感度都有扎实的把握这些东西恰恰是 C 日常开发中最需要的能力。这篇文章我会用一次完整的面试回答视角把快速排序从最朴素的写法开始一步步推到面试官满意的“最优解”包括三数取中、双路 partition、小区间插入排序、非递归实现以及如何应对那些常见的追问。每一版代码都会说清楚“为什么这么改”“解决了什么问题”“代价是什么”而不是丢一堆代码让你自己悟。2. 先想明白一件事快排凭什么比冒泡快2.1 分治思想的朴素起点快速排序的核心思想只有一句话选一个基准值把数组分成“小于基准”和“大于基准”两半然后递归处理两半。听起来和归并排序有点像但有个本质区别归并排序的“分”是单纯地对半切真正的排序工作在“合”的阶段完成而快速排序的“分”本身就带着排序效果——每次 partition 之后基准元素就已经落到了它最终该在的位置左边全部小于它右边全部大于它。所以快排的排序工作发生在“分”的阶段“合”根本不需要额外操作。这个差异决定了两种算法在工程上的命运归并排序需要 O(n) 的额外空间来做合并而快速排序可以做到原地排序只需要 O(log n) 的递归栈空间。在数据量大的时候这个内存优势是决定性的。2.2 平均复杂度为什么是 O(n log n)最坏又为什么是 O(n²)很多初学者背下了“快排平均 O(n log n)、最坏 O(n²)”这两个结论但说不清原因。我建议你用“每次 partition 的扫描量”来理解每一次 partition你要从头到尾扫描当前区间扫描量是区间长度 n。如果每次 partition 都能把区间大致对半分那么总共需要 log₂n 层扫描每层合起来扫描 n 个元素总工作量就是 n log n。但如果你每次选的基准都恰好是当前区间的最大值或最小值那么 partition 后一侧是空的另一侧是 n-1 个元素一共要递归 n 层每层扫描量从 n 递减到 1总工作量就是 n (n-1) (n-2) … ≈ n²/2也就是 O(n²)。所以快排的性能瓶颈从来不在“扫描”本身而在你能不能选出一个把区间切得足够均匀的基准值。这也是后面所有优化版本的出发点一切手段都是为了让基准值更接近“中位数”。注意面试时如果你能主动说出上面这段推导而不是只背结论面试官对你的印象分会明显不同。3. 第一版最基础的单路快排以及它的两个致命缺陷3.1 教科书版写法与逐行拆解先把最标准的“教科书版”写出来作为讨论的起点。这个版本我建议每个人都应该能闭着眼写对#include vector #include algorithm // partition返回基准值最终所在位置 int partition(std::vectorint nums, int left, int right) { int pivot nums[right]; // 选最右元素作为基准 int i left - 1; // i 指向“已处理的小于基准的区间”末尾 for (int j left; j right; j) { if (nums[j] pivot) { i; std::swap(nums[i], nums[j]); } } // 把基准放到正确位置 std::swap(nums[i 1], nums[right]); return i 1; } void quickSort(std::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); }这个写法是网上最常见的“单路快排”它的核心逻辑在 partition 函数的循环里用j从左往右扫描用i标记“小于基准的区域的最后一个位置”。遇到比基准小的元素就把i往后挪一格然后和j交换把这个小元素“扔进”左侧已处理区域。循环结束后i 1位置放基准值左边全是小于基准的右边全是大于等于基准的。这里有个细节值得记住循环里用的是nums[j] pivot而不是。这意味着等于基准的元素会被分到右侧。这个细节在标准场景下无关紧要但在有大量重复元素的数组里会引发严重问题——这正好引出了这一版的第一个致命缺陷。3.2 缺陷一有序数组直接退化到 O(n²)如果输入数组已经是升序排列的比如[1, 2, 3, 4, 5, 6, 7, 8]我们每次选最右元素作为基准那么基准永远是这个区间里的最大值。每次 partition 的结果是基准被放到最右端左侧区间大小只减少 1。也就是说每一层递归只能排好一个元素总共需要 n 层递归复杂度直接拉满到 O(n²)。面试的时候如果面试官让你跑一下这个用例你会发现 10 万量级的有序数组快排需要递归 10 万层。这在真实环境中不仅慢而且栈溢出——C 默认的调用栈大概只有 1MB 到 8MB10 万层递归的栈帧累积下来很容易爆掉。3.3 缺陷二大量重复元素时左右严重失衡再考虑一个全是相同元素的情况比如[5, 5, 5, 5, ..., 5]。因为我们用的是而不是所以所有等于基准的元素都会被分到右侧。第一次 partition 之后左侧为空右侧有 n-1 个元素。第二层同样如此——每次只排好一个元素又是 O(n²)。这其实比有序数组更隐蔽因为很多测试用例是随机生成的不会恰好全是重复元素。但真实业务里数据重复是非常常见的比如按城市分组、按状态位过滤后的数据如果快速排序在重复数据上退化线上就等着被打爆。提示很多人的面试“翻车现场”就是写了这个版本然后面试官随口说“你跑一下全是相同数字的数组”代码直接原地爆炸。4. 第二版三数取中 双路 partition解决核心痛点4.1 三数取中用最廉价的代价逼近中位数解决有序数组退化问题的最常见手段是三数取中从区间的左端、中间、右端选三个数取它们的中位数作为基准值。int medianOfThree(std::vectorint nums, int left, int right) { int mid left (right - left) / 2; // 简单排序这三个位置让 nums[left] nums[mid] nums[right] if (nums[left] nums[mid]) std::swap(nums[left], nums[mid]); if (nums[left] nums[right]) std::swap(nums[left], nums[right]); if (nums[mid] nums[right]) std::swap(nums[mid], nums[right]); return nums[mid]; }为什么不用“取整个数组的中位数”因为那需要先做一次 O(n) 的查找或排序成本太高。三数取中的逻辑非常朴素对于完全有序的数组取左、中、右三个位置的值中位数恰好是中间那个数相当于每次都能把区间对半分。对于随机数组三数取中的表现也足够接近最优。取到中位数之后我们把它交换到数组末尾或者开头看你 partition 的实现习惯然后继续用标准 partition。这一步的代价是常数级的收益却是把最坏情况从 O(n²) 降到了接近 O(n log n)。4.2 双路 partition把相等的元素“均匀”地分到两侧接下来处理重复元素的问题。单路快排的问题在于所有等于基准的元素都去了同一侧。双路快排的思路是两个指针从两端向中间扫遇到不符合“小于基准在左、大于基准在右”规则的元素就交换让等于基准的元素“均匀”地分布在两侧。// 双路快排的 partition返回两个指针相遇或交错的位置 int partitionDual(std::vectorint nums, int left, int right) { int mid left (right - left) / 2; // 三数取中 if (nums[left] nums[mid]) std::swap(nums[left], nums[mid]); if (nums[left] nums[right]) std::swap(nums[left], nums[right]); if (nums[mid] nums[right]) std::swap(nums[mid], nums[right]); // 此时 nums[mid] 是中位数把它换到 right - 1 位置 std::swap(nums[mid], nums[right - 1]); int pivot nums[right - 1]; int i left 1; // 左指针从 left1 开始 int j right - 2; // 右指针从 right-2 开始 while (true) { while (nums[i] pivot) i; while (nums[j] pivot) --j; if (i j) break; std::swap(nums[i], nums[j]); i; --j; } // 把基准放回中间 std::swap(nums[i], nums[right - 1]); return i; }这个版本的核心思路是等于基准的元素不会被特意赶到某一侧而是在双指针的交换过程中自然散落在两侧。无论输入有多少重复值partition 后两侧的大小差距都不会太离谱。这个过程有个细节左侧指针用nums[i] pivot才前进右侧指针用nums[j] pivot才后退。遇到等于 pivot 的元素两个指针会停下来并交换这保证了相等的元素不会扎堆在一侧。我在实际面试中观察到能写出双路快排的候选人占比不到两成。多数人到“三数取中”就停了。但这恰恰是区分“背过答案”和“真正理解”的分水岭。4.3 别忘了递归出口的优化小区间插入排序除了上面两个核心优化还有一个工程上常用的技巧当区间长度小于某个阈值通常是 10~20时改用插入排序。void quickSortImproved(std::vectorint nums, int left, int right) { const int kThreshold 15; if (left right) return; // 小区间用插入排序 if (right - left 1 kThreshold) { 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; } return; } int pivotIndex partitionDual(nums, left, right); quickSortImproved(nums, left, pivotIndex - 1); quickSortImproved(nums, pivotIndex 1, right); }原因是递归到小区间时函数调用开销栈帧压栈、参数传递、分支判断已经大于元素比较本身的开销了。而插入排序在近乎有序的小区间上非常高效并且没有额外空间。很多工业级实现——包括某些标准库的 introsort——都会做这个优化。面试时你主动提出来算是典型的“加分项”。5. 第三版非递归快排绕开栈溢出的坑5.1 为什么需要手写栈即使做了三数取中快排的递归深度在理想情况下也只有 O(log n)。但面试官经常会追问一句“你能写一个非递归版本吗”这个问题背后的动机有两个考察你对“递归本质是栈”的理解是否到位。考察你是否意识到在极端情况下比如无法使用三数取中、或者数据分布极其特殊递归依然可能因为调用栈过深而溢出。模拟递归的经典做法是用显式的栈保存待排序区间的左右边界每次从栈中弹出一个区间partition 之后把两个子区间压入栈中。void quickSortNonRecursive(std::vectorint nums, int left, int right) { // 用栈保存待处理的区间 std::vectorstd::pairint, int stack; stack.push_back({left, right}); while (!stack.empty()) { auto [l, r] stack.back(); stack.pop_back(); if (l r) continue; int pivotIndex partitionDual(nums, l, r); // 先把较大的区间压栈再压较小的区间控制栈深度 if (pivotIndex - l r - pivotIndex) { stack.push_back({pivotIndex 1, r}); stack.push_back({l, pivotIndex - 1}); } else { stack.push_back({l, pivotIndex - 1}); stack.push_back({pivotIndex 1, r}); } } }这里有一个很实用的小技巧优先把较大的区间压栈、较小的区间后压栈并先处理。这样栈中同时存在的区间数量始终控制在 O(log n) 级别。不这么做的话极端情况下这个模拟栈也可能膨胀到 O(n)就失去了意义。我用std::vector模拟栈而不是std::stack因为std::stack默认底层容器是deque在这种频繁 push/pop 的场景下性能不如vector。5.2 三种实现方式的取舍对比面试时如果时间充裕我会建议把“递归版 非递归版”都写出来并主动对比它们的使用场景维度递归版非递归版代码可读性高符合分治思维中需要理解“用栈模拟调用过程”栈溢出风险有最坏情况 O(n) 深度可控显式栈可在堆上分配性能函数调用有少量开销手动压栈/弹栈也有开销通常略慢适用场景一般业务、面试首选数据量极大、可用栈空间受限的环境我在实际开发中遇到过一次递归快排导致栈溢出的线上问题——那是一个深度嵌套的配置树递归层数明明不深但每次递归中局部变量特别大把栈撑爆了。从那以后凡是处理不确定深度数据的排序逻辑我都默认用非递归版本。注意面试时写非递归快排最好在一分钟内完成思路说明——“用栈保存区间循环处理”——而不是埋头写代码。这种“先说思路再动手”的习惯本身就是面试官想看到的。6. 面试追问环节这些“附加题”比快排本身更重要6.1 经典追问一快速排序是稳定的吗不是。标准的快速排序不是稳定排序。原因很简单partition 过程中会大量交换元素的位置特别是不相邻的元素之间的交换这会破坏相同元素的相对顺序。举个具体例子数组[3a, 2, 1, 3b]3a 和 3b 表示两个值相同的不同对象如果基准选的是 3b在 partition 交换的过程中3a 可能被换到 3b 的右边相对顺序就被打破了。一个合格的 C 开发者还应该补充一句C 标准库的std::sort并不能保证稳定性而std::stable_sort可以但std::stable_sort的实现不是快排而是归并排序或其变体代价是额外的内存或更复杂的合并策略。6.2 经典追问二既然快排最坏是 O(n²)为什么排序库不用堆排这题考察的是对工程权衡的理解。堆排序的最坏复杂度确实是严格的 O(n log n)但它有一个致命弱点对缓存极不友好。堆排序的访问模式是“跳着访问”的比如访问堆顶后要下沉到它的某个子节点子节点和父节点的位置相距很远会导致大量的缓存未命中。快速排序的访问模式是顺序扫描的从左往右、从右往左这对 CPU 的预取机制和缓存行非常友好实际运行速度通常比堆排序快 2~3 倍。工业界的答案往往是两者结合。C 标准库的std::sort通常实现为 introsort——是一种结合了快排、堆排序和插入排序的混合算法以快排为主体当递归深度超过阈值通常是 2 × log₂n时切换为堆排序防止最坏情况小区间用插入排序提升常数性能。这个设计思路面试时讲出来会让面试官觉得你不仅会写代码还了解背后的工业级考量。6.3 经典追问三如何用快排思想找第 K 大的数这题本质上就是quickselect 算法。它的思路是只需要关心基准的某一边而不需要两边都递归。// 找第 k 大的数k 从 1 开始计数 int quickSelect(std::vectorint nums, int left, int right, int k) { if (left right) return nums[left]; int pivotIndex partitionDual(nums, left, right); // 右侧元素数量 int rightCount right - pivotIndex; if (k rightCount 1) { return nums[pivotIndex]; } else if (k rightCount) { return quickSelect(nums, pivotIndex 1, right, k); } else { return quickSelect(nums, left, pivotIndex - 1, k - rightCount - 1); } }这个算法的期望复杂度是 O(n)——每层只需要处理一边扫描量是 n n/2 n/4 … ≈ 2n。它是“用快排的 partition 思想解决选择问题”的经典范例面试中出现频率极高。可以把这题看作是快排的“进阶应用”能直接回答出 quickselect 的候选人通常都能给面试官留下深刻印象。6.4 经典追问四如何优化大量重复元素的排序——三路快排对于全是相同元素的数据三数取中 双路快排已经能避免 O(n²) 的退化但还可以更进一步三路快速排序。它的思想是把数组分成三块小于基准、等于基准、大于基准。等于基准的部分不再参与递归。// 三路快排的 partition返回 {小于基准区的末尾, 大于基准区的开头} std::pairint, int partitionThreeWay(std::vectorint nums, int left, int right) { int pivot nums[left]; int lt left; // lt 左侧都是小于 pivot 的元素 int gt right 1; // gt 右侧都是大于 pivot 的元素 int i left 1; while (i gt) { if (nums[i] pivot) { std::swap(nums[i], nums[lt 1]); lt; i; } else if (nums[i] pivot) { std::swap(nums[i], nums[gt - 1]); --gt; // 注意i 不前进因为换过来的元素还没比较过 } else { i; } } // 把基准值放到等于区间的开头 std::swap(nums[left], nums[lt]); return {lt - 1, gt}; }三路快排的价值在于当数组中重复元素非常多时等于基准的大块区间不参与递归可以大幅减少递归层数和扫描量。这也是 Java 标准库Arrays.sort()在对基本类型排序时的实现思路之一。提示三路快排是面试中的加分项但如果你对双路快排的边界条件都还不太熟练建议先把基础打牢再上三路。面试时写一个写不对的“高级版本”不如写一个完全正确的“普通版本”。7. 现场写码的实战建议手写过程中的常见坑位7.1 边界条件循环里到底用还是这是手写快排时最容易出错的地方。partition 的双指针循环中while (i j)和while (i j)会产生完全不同的行为。用i j指针相遇后不再交换基准位置通常取i用i j指针交错后才停止基准位置需要重新计算。两种写法都对但务必保持一致不要在同一版代码里混用两种风格。递归终止条件写if (left right) return;还是写if (left right) return;推荐写成因为当区间只有一个元素时没必要递归。这个细节虽然不影响正确性但面试官看到你写会觉得你考虑过边界。7.2 交换操作不要用异或交换想炫技反而容易翻车很多人知道“异或交换两个数”的技巧a ^ b; b ^ a; a ^ b;。但要提醒你如果 a 和 b 是同一个变量同一个数组位置异或交换会把值变成 0。在快排的 partition 中i和j是有可能指向同一个位置的直接用异或交换就会出错。所以请老老实实用std::swap。这是我在面试现场亲眼见过的“炫技翻车”案例不再用很短的时间就能验证。7.3 防御性检查swap 之后指针的移动方向在双路快排中有一个非常隐蔽的坑当你交换了nums[i]和nums[j]之后不要立刻让i和j--——你先得检查交换过来的值是否又满足了停止条件。正确做法可以是在 swap 之后立即i; --j;跳过已处理位置也可以让循环体回到顶部重新判断。这两种写法各有偏好我建议你选一种固定下来多练几遍形成肌肉记忆。面试现场的紧张氛围下最怕的就是边界条件的不确定性。8. 把这版代码跑起来验证与基准测试8.1 最小验证用例清单写完代码之后面试现场大概率会让你“跑几个用例验证一下”。我的习惯是准备这样一组用例覆盖各种边界情况#include iostream #include vector #include cassert void print(const std::vectorint v) { for (int x : v) std::cout x ; std::cout \n; } int main() { std::vectorstd::vectorint cases { {1, 2, 3, 4, 5}, // 升序最容易退化 {5, 4, 3, 2, 1}, // 降序 {5, 5, 5, 5, 5}, // 全相同 {3, 5, 3, 1, 3, 2, 5, 4}, // 有大量重复 {1}, // 单元素 {} // 空数组 }; for (auto nums : cases) { quickSortImproved(nums, 0, (int)nums.size() - 1); assert(std::is_sorted(nums.begin(), nums.end())); } std::cout all test cases passed!\n; }这组用例覆盖了最坏情况的输入有序、全部重复、单元素、空数组。如果你用第一版代码跑这个测试第 1 和第 4 个用例就会非常慢甚至崩掉用三数取中 双路版就能顺利通过。8.2 用时间和内存做一次直观对比如果在本地想验证优化效果可以做一个简单实验分别用基础版和优化版对 100 万个有序整数排序。你会看到基础版耗时可能是数十秒甚至更久递归深也可能直接栈溢出程序崩溃。优化版耗时稳定在几十到几百毫秒之间。这个差距在面试现场不需要真的跑数据用言语表述出来就足够有说服力了“基础版在 100 万有序数据上会直接栈溢出或慢到不可忍受而优化版可以轻松处理 1 亿以内的数据。”如果能配上一句“我实际跑过量级差距至少百倍”效果更好。8.3 环境配置提示VSCode 跑 C 的注意事项有些同学在面试复盘时想自己跑一下代码结果卡在了环境配置上。这里说一个最常见的问题在 VSCode 里配置 C 编译环境时至少要安装一个编译器Windows 上推荐 MinGW-w64 或 MSVC和 C/C 扩展插件。我踩过的坑是只装了扩展、没装编译器按住 F5 调试时报出“无法找到编译器”之类的错误。安装 MinGW-w64 后还需要确认编译器路径已加入系统 PATH。另外在 Windows 上编译时如果遇到fopen之类的安全函数报警告可以在编译命令中加-D_CRT_SECURE_NO_WARNINGS这是 MSVC 环境特有的问题或者在代码里用标准库的文件流而不是 C 风格的fopen。如果你只是为了刷算法题我建议用在线编译器比如 Compiler Explorer或者本地只装一个带 MinGW 的 Dev-C 也行。VSCode 的调试体验虽好但对新手来说配置成本略高不要把时间浪费在环境上重点还是理解算法本身。9. 从面试回归到工程快排思想在日常开发中的延伸9.1 不只是排序——partition 思想在“分组”场景的应用快速排序最值得借鉴的不是排序本身而是partition 的“按条件分组”能力。我写过很多需要把数组按某种条件分成两类的场景把负数移到数组左边、正数移到右边荷兰国旗问题的简化版。把有效数据和不合法数据分开而且要求保持相对顺序此时需要稳定 partition可以用额外数组也可以用类似“原地稳定分区”的技巧。把对象按某个属性值切成左右两半便于二分查找后续处理。这些场景如果不加思考地用std::partition标准库自带当然没问题但半笔试背景下能手写 partition其实也是对你代码能力的验证。用习惯了之后你会发现partition 本质上就是一个带条件的“分组筛选”操作比排序本身更常用。9.2 标准库的排序算法选择什么时候用 std::sort日常 C 开发中你几乎不需要自己写快排——直接用std::sort就行了。但理解快排仍然必要因为std::sort的实现原理introsort就是从快排演化来的理解快排之后你能预判std::sort在不同数据分布下的表现。如果你需要对vector的一部分区间排序std::partial_sort底层逻辑也和“选择第 k 个元素”的快速选择思想有关。当你需要稳定排序时std::stable_sort会额外分配内存并采用归并排序如果你不清楚快排和归并的稳定性差异很容易在工程选型上犯错误。9.3 大数据场景外部排序与分治的边界当数据量大到无法全部放入内存时比如几十 GB 的日志文件快排这类的“内存排序”就不适用了这时会用到外部排序也就是“先分块排序、再多路归并”的思路。这种场景下归并排序的“合”阶段反而成了主角——它的合并操作天然适合顺序读取磁盘、减少随机 IO。理解快排的“分”和归并的“合”各自主导的应用边界能让你在设计系统时多一层判断维度。10. 我的一些实战心得写快排的正确“姿势”文章的最后我想分享几个从面试现场和实际工程中沉淀下来的经验。不要背代码要背推理过程。背下来的代码在压力面试下很容易变形因为一个符号错了你自己都发现不了。但如果你脑中有一条清晰的推理链——“选基准 → 三数取中避免有序退化 → 双路指针处理重复 → 递归时小区间切到插入排序”那么即使一时忘了某行写法也能在纸上推出来。写代码前先把思路口头说出来。我面试别人时特别看重候选人写代码前的“口头前置说明”——比如“我打算先实现单路版本再优化”会让沟通成本大幅降低。如果你能做到面试官大概率会帮你排除一些非关键分歧你写起来反而更放松。一定要准备非递归版本。十个候选人里有六七个能写出递归版但只有两三个能顺畅地写出非递归版。这不是说非递归版本身有多难而是多数人没有刻意练过。花半小时把递归版改成显式栈版本性价比极高。类似的“套路性改造”在面试中还有许多——比如把 DFS 改成迭代版、把二分查找改成非递归版——只要掌握一次就能举一反三。把快排当作理解 C 特性的试金石。通过快排这道题你能同时展示引用传递的正确使用、对栈空间和递归深度的认知、对复杂度的直觉、甚至对标准库实现原理的了解。面试官问你一个问题你却能在一个答案里侧面展示多项能力这正是资深开发者与应届生拉开差距的地方。就说这些。如果你能把上面这些版本都亲手写一遍用我给的用例跑一遍再把那几个追问自己口头回答一遍那么下次面试遇到“手写快速排序”这道题你一定不会只是背出一个标准答案——你会让面试官觉得你是真的吃透了它。 快速排序优化实战：从O(n²)到O(n log n)的进阶之路
1. 从一道题看面试官的真正意图先说个可能让不少人意外的事实快速排序几乎是面试中出现频率最高、但通过率最低的“送分题”。很多候选人觉得“快排我背过”结果一落笔就露馅——要么写出的代码在[1, 2, 3, 4, 5]这种有序数组上直接退化到 O(n²)要么 partition 的边界条件一改就崩要么被追问“你的快排稳定吗”“为什么库函数不用快排”时支支吾吾。作为写过多年 C、也坐在面试官那一侧看过不少候选人现场写代码的人我可以负责任地告诉你面试官让你手写快排绝不是为了考察你会不会背代码而是想通过这一道题看你的工程思维、边界意识和对算法本质的理解。一个能把快排从“基础版”一路演进到“最优版”的候选人通常对指针操作、递归开销、数据分布敏感度都有扎实的把握这些东西恰恰是 C 日常开发中最需要的能力。这篇文章我会用一次完整的面试回答视角把快速排序从最朴素的写法开始一步步推到面试官满意的“最优解”包括三数取中、双路 partition、小区间插入排序、非递归实现以及如何应对那些常见的追问。每一版代码都会说清楚“为什么这么改”“解决了什么问题”“代价是什么”而不是丢一堆代码让你自己悟。2. 先想明白一件事快排凭什么比冒泡快2.1 分治思想的朴素起点快速排序的核心思想只有一句话选一个基准值把数组分成“小于基准”和“大于基准”两半然后递归处理两半。听起来和归并排序有点像但有个本质区别归并排序的“分”是单纯地对半切真正的排序工作在“合”的阶段完成而快速排序的“分”本身就带着排序效果——每次 partition 之后基准元素就已经落到了它最终该在的位置左边全部小于它右边全部大于它。所以快排的排序工作发生在“分”的阶段“合”根本不需要额外操作。这个差异决定了两种算法在工程上的命运归并排序需要 O(n) 的额外空间来做合并而快速排序可以做到原地排序只需要 O(log n) 的递归栈空间。在数据量大的时候这个内存优势是决定性的。2.2 平均复杂度为什么是 O(n log n)最坏又为什么是 O(n²)很多初学者背下了“快排平均 O(n log n)、最坏 O(n²)”这两个结论但说不清原因。我建议你用“每次 partition 的扫描量”来理解每一次 partition你要从头到尾扫描当前区间扫描量是区间长度 n。如果每次 partition 都能把区间大致对半分那么总共需要 log₂n 层扫描每层合起来扫描 n 个元素总工作量就是 n log n。但如果你每次选的基准都恰好是当前区间的最大值或最小值那么 partition 后一侧是空的另一侧是 n-1 个元素一共要递归 n 层每层扫描量从 n 递减到 1总工作量就是 n (n-1) (n-2) … ≈ n²/2也就是 O(n²)。所以快排的性能瓶颈从来不在“扫描”本身而在你能不能选出一个把区间切得足够均匀的基准值。这也是后面所有优化版本的出发点一切手段都是为了让基准值更接近“中位数”。注意面试时如果你能主动说出上面这段推导而不是只背结论面试官对你的印象分会明显不同。3. 第一版最基础的单路快排以及它的两个致命缺陷3.1 教科书版写法与逐行拆解先把最标准的“教科书版”写出来作为讨论的起点。这个版本我建议每个人都应该能闭着眼写对#include vector #include algorithm // partition返回基准值最终所在位置 int partition(std::vectorint nums, int left, int right) { int pivot nums[right]; // 选最右元素作为基准 int i left - 1; // i 指向“已处理的小于基准的区间”末尾 for (int j left; j right; j) { if (nums[j] pivot) { i; std::swap(nums[i], nums[j]); } } // 把基准放到正确位置 std::swap(nums[i 1], nums[right]); return i 1; } void quickSort(std::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); }这个写法是网上最常见的“单路快排”它的核心逻辑在 partition 函数的循环里用j从左往右扫描用i标记“小于基准的区域的最后一个位置”。遇到比基准小的元素就把i往后挪一格然后和j交换把这个小元素“扔进”左侧已处理区域。循环结束后i 1位置放基准值左边全是小于基准的右边全是大于等于基准的。这里有个细节值得记住循环里用的是nums[j] pivot而不是。这意味着等于基准的元素会被分到右侧。这个细节在标准场景下无关紧要但在有大量重复元素的数组里会引发严重问题——这正好引出了这一版的第一个致命缺陷。3.2 缺陷一有序数组直接退化到 O(n²)如果输入数组已经是升序排列的比如[1, 2, 3, 4, 5, 6, 7, 8]我们每次选最右元素作为基准那么基准永远是这个区间里的最大值。每次 partition 的结果是基准被放到最右端左侧区间大小只减少 1。也就是说每一层递归只能排好一个元素总共需要 n 层递归复杂度直接拉满到 O(n²)。面试的时候如果面试官让你跑一下这个用例你会发现 10 万量级的有序数组快排需要递归 10 万层。这在真实环境中不仅慢而且栈溢出——C 默认的调用栈大概只有 1MB 到 8MB10 万层递归的栈帧累积下来很容易爆掉。3.3 缺陷二大量重复元素时左右严重失衡再考虑一个全是相同元素的情况比如[5, 5, 5, 5, ..., 5]。因为我们用的是而不是所以所有等于基准的元素都会被分到右侧。第一次 partition 之后左侧为空右侧有 n-1 个元素。第二层同样如此——每次只排好一个元素又是 O(n²)。这其实比有序数组更隐蔽因为很多测试用例是随机生成的不会恰好全是重复元素。但真实业务里数据重复是非常常见的比如按城市分组、按状态位过滤后的数据如果快速排序在重复数据上退化线上就等着被打爆。提示很多人的面试“翻车现场”就是写了这个版本然后面试官随口说“你跑一下全是相同数字的数组”代码直接原地爆炸。4. 第二版三数取中 双路 partition解决核心痛点4.1 三数取中用最廉价的代价逼近中位数解决有序数组退化问题的最常见手段是三数取中从区间的左端、中间、右端选三个数取它们的中位数作为基准值。int medianOfThree(std::vectorint nums, int left, int right) { int mid left (right - left) / 2; // 简单排序这三个位置让 nums[left] nums[mid] nums[right] if (nums[left] nums[mid]) std::swap(nums[left], nums[mid]); if (nums[left] nums[right]) std::swap(nums[left], nums[right]); if (nums[mid] nums[right]) std::swap(nums[mid], nums[right]); return nums[mid]; }为什么不用“取整个数组的中位数”因为那需要先做一次 O(n) 的查找或排序成本太高。三数取中的逻辑非常朴素对于完全有序的数组取左、中、右三个位置的值中位数恰好是中间那个数相当于每次都能把区间对半分。对于随机数组三数取中的表现也足够接近最优。取到中位数之后我们把它交换到数组末尾或者开头看你 partition 的实现习惯然后继续用标准 partition。这一步的代价是常数级的收益却是把最坏情况从 O(n²) 降到了接近 O(n log n)。4.2 双路 partition把相等的元素“均匀”地分到两侧接下来处理重复元素的问题。单路快排的问题在于所有等于基准的元素都去了同一侧。双路快排的思路是两个指针从两端向中间扫遇到不符合“小于基准在左、大于基准在右”规则的元素就交换让等于基准的元素“均匀”地分布在两侧。// 双路快排的 partition返回两个指针相遇或交错的位置 int partitionDual(std::vectorint nums, int left, int right) { int mid left (right - left) / 2; // 三数取中 if (nums[left] nums[mid]) std::swap(nums[left], nums[mid]); if (nums[left] nums[right]) std::swap(nums[left], nums[right]); if (nums[mid] nums[right]) std::swap(nums[mid], nums[right]); // 此时 nums[mid] 是中位数把它换到 right - 1 位置 std::swap(nums[mid], nums[right - 1]); int pivot nums[right - 1]; int i left 1; // 左指针从 left1 开始 int j right - 2; // 右指针从 right-2 开始 while (true) { while (nums[i] pivot) i; while (nums[j] pivot) --j; if (i j) break; std::swap(nums[i], nums[j]); i; --j; } // 把基准放回中间 std::swap(nums[i], nums[right - 1]); return i; }这个版本的核心思路是等于基准的元素不会被特意赶到某一侧而是在双指针的交换过程中自然散落在两侧。无论输入有多少重复值partition 后两侧的大小差距都不会太离谱。这个过程有个细节左侧指针用nums[i] pivot才前进右侧指针用nums[j] pivot才后退。遇到等于 pivot 的元素两个指针会停下来并交换这保证了相等的元素不会扎堆在一侧。我在实际面试中观察到能写出双路快排的候选人占比不到两成。多数人到“三数取中”就停了。但这恰恰是区分“背过答案”和“真正理解”的分水岭。4.3 别忘了递归出口的优化小区间插入排序除了上面两个核心优化还有一个工程上常用的技巧当区间长度小于某个阈值通常是 10~20时改用插入排序。void quickSortImproved(std::vectorint nums, int left, int right) { const int kThreshold 15; if (left right) return; // 小区间用插入排序 if (right - left 1 kThreshold) { 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; } return; } int pivotIndex partitionDual(nums, left, right); quickSortImproved(nums, left, pivotIndex - 1); quickSortImproved(nums, pivotIndex 1, right); }原因是递归到小区间时函数调用开销栈帧压栈、参数传递、分支判断已经大于元素比较本身的开销了。而插入排序在近乎有序的小区间上非常高效并且没有额外空间。很多工业级实现——包括某些标准库的 introsort——都会做这个优化。面试时你主动提出来算是典型的“加分项”。5. 第三版非递归快排绕开栈溢出的坑5.1 为什么需要手写栈即使做了三数取中快排的递归深度在理想情况下也只有 O(log n)。但面试官经常会追问一句“你能写一个非递归版本吗”这个问题背后的动机有两个考察你对“递归本质是栈”的理解是否到位。考察你是否意识到在极端情况下比如无法使用三数取中、或者数据分布极其特殊递归依然可能因为调用栈过深而溢出。模拟递归的经典做法是用显式的栈保存待排序区间的左右边界每次从栈中弹出一个区间partition 之后把两个子区间压入栈中。void quickSortNonRecursive(std::vectorint nums, int left, int right) { // 用栈保存待处理的区间 std::vectorstd::pairint, int stack; stack.push_back({left, right}); while (!stack.empty()) { auto [l, r] stack.back(); stack.pop_back(); if (l r) continue; int pivotIndex partitionDual(nums, l, r); // 先把较大的区间压栈再压较小的区间控制栈深度 if (pivotIndex - l r - pivotIndex) { stack.push_back({pivotIndex 1, r}); stack.push_back({l, pivotIndex - 1}); } else { stack.push_back({l, pivotIndex - 1}); stack.push_back({pivotIndex 1, r}); } } }这里有一个很实用的小技巧优先把较大的区间压栈、较小的区间后压栈并先处理。这样栈中同时存在的区间数量始终控制在 O(log n) 级别。不这么做的话极端情况下这个模拟栈也可能膨胀到 O(n)就失去了意义。我用std::vector模拟栈而不是std::stack因为std::stack默认底层容器是deque在这种频繁 push/pop 的场景下性能不如vector。5.2 三种实现方式的取舍对比面试时如果时间充裕我会建议把“递归版 非递归版”都写出来并主动对比它们的使用场景维度递归版非递归版代码可读性高符合分治思维中需要理解“用栈模拟调用过程”栈溢出风险有最坏情况 O(n) 深度可控显式栈可在堆上分配性能函数调用有少量开销手动压栈/弹栈也有开销通常略慢适用场景一般业务、面试首选数据量极大、可用栈空间受限的环境我在实际开发中遇到过一次递归快排导致栈溢出的线上问题——那是一个深度嵌套的配置树递归层数明明不深但每次递归中局部变量特别大把栈撑爆了。从那以后凡是处理不确定深度数据的排序逻辑我都默认用非递归版本。注意面试时写非递归快排最好在一分钟内完成思路说明——“用栈保存区间循环处理”——而不是埋头写代码。这种“先说思路再动手”的习惯本身就是面试官想看到的。6. 面试追问环节这些“附加题”比快排本身更重要6.1 经典追问一快速排序是稳定的吗不是。标准的快速排序不是稳定排序。原因很简单partition 过程中会大量交换元素的位置特别是不相邻的元素之间的交换这会破坏相同元素的相对顺序。举个具体例子数组[3a, 2, 1, 3b]3a 和 3b 表示两个值相同的不同对象如果基准选的是 3b在 partition 交换的过程中3a 可能被换到 3b 的右边相对顺序就被打破了。一个合格的 C 开发者还应该补充一句C 标准库的std::sort并不能保证稳定性而std::stable_sort可以但std::stable_sort的实现不是快排而是归并排序或其变体代价是额外的内存或更复杂的合并策略。6.2 经典追问二既然快排最坏是 O(n²)为什么排序库不用堆排这题考察的是对工程权衡的理解。堆排序的最坏复杂度确实是严格的 O(n log n)但它有一个致命弱点对缓存极不友好。堆排序的访问模式是“跳着访问”的比如访问堆顶后要下沉到它的某个子节点子节点和父节点的位置相距很远会导致大量的缓存未命中。快速排序的访问模式是顺序扫描的从左往右、从右往左这对 CPU 的预取机制和缓存行非常友好实际运行速度通常比堆排序快 2~3 倍。工业界的答案往往是两者结合。C 标准库的std::sort通常实现为 introsort——是一种结合了快排、堆排序和插入排序的混合算法以快排为主体当递归深度超过阈值通常是 2 × log₂n时切换为堆排序防止最坏情况小区间用插入排序提升常数性能。这个设计思路面试时讲出来会让面试官觉得你不仅会写代码还了解背后的工业级考量。6.3 经典追问三如何用快排思想找第 K 大的数这题本质上就是quickselect 算法。它的思路是只需要关心基准的某一边而不需要两边都递归。// 找第 k 大的数k 从 1 开始计数 int quickSelect(std::vectorint nums, int left, int right, int k) { if (left right) return nums[left]; int pivotIndex partitionDual(nums, left, right); // 右侧元素数量 int rightCount right - pivotIndex; if (k rightCount 1) { return nums[pivotIndex]; } else if (k rightCount) { return quickSelect(nums, pivotIndex 1, right, k); } else { return quickSelect(nums, left, pivotIndex - 1, k - rightCount - 1); } }这个算法的期望复杂度是 O(n)——每层只需要处理一边扫描量是 n n/2 n/4 … ≈ 2n。它是“用快排的 partition 思想解决选择问题”的经典范例面试中出现频率极高。可以把这题看作是快排的“进阶应用”能直接回答出 quickselect 的候选人通常都能给面试官留下深刻印象。6.4 经典追问四如何优化大量重复元素的排序——三路快排对于全是相同元素的数据三数取中 双路快排已经能避免 O(n²) 的退化但还可以更进一步三路快速排序。它的思想是把数组分成三块小于基准、等于基准、大于基准。等于基准的部分不再参与递归。// 三路快排的 partition返回 {小于基准区的末尾, 大于基准区的开头} std::pairint, int partitionThreeWay(std::vectorint nums, int left, int right) { int pivot nums[left]; int lt left; // lt 左侧都是小于 pivot 的元素 int gt right 1; // gt 右侧都是大于 pivot 的元素 int i left 1; while (i gt) { if (nums[i] pivot) { std::swap(nums[i], nums[lt 1]); lt; i; } else if (nums[i] pivot) { std::swap(nums[i], nums[gt - 1]); --gt; // 注意i 不前进因为换过来的元素还没比较过 } else { i; } } // 把基准值放到等于区间的开头 std::swap(nums[left], nums[lt]); return {lt - 1, gt}; }三路快排的价值在于当数组中重复元素非常多时等于基准的大块区间不参与递归可以大幅减少递归层数和扫描量。这也是 Java 标准库Arrays.sort()在对基本类型排序时的实现思路之一。提示三路快排是面试中的加分项但如果你对双路快排的边界条件都还不太熟练建议先把基础打牢再上三路。面试时写一个写不对的“高级版本”不如写一个完全正确的“普通版本”。7. 现场写码的实战建议手写过程中的常见坑位7.1 边界条件循环里到底用还是这是手写快排时最容易出错的地方。partition 的双指针循环中while (i j)和while (i j)会产生完全不同的行为。用i j指针相遇后不再交换基准位置通常取i用i j指针交错后才停止基准位置需要重新计算。两种写法都对但务必保持一致不要在同一版代码里混用两种风格。递归终止条件写if (left right) return;还是写if (left right) return;推荐写成因为当区间只有一个元素时没必要递归。这个细节虽然不影响正确性但面试官看到你写会觉得你考虑过边界。7.2 交换操作不要用异或交换想炫技反而容易翻车很多人知道“异或交换两个数”的技巧a ^ b; b ^ a; a ^ b;。但要提醒你如果 a 和 b 是同一个变量同一个数组位置异或交换会把值变成 0。在快排的 partition 中i和j是有可能指向同一个位置的直接用异或交换就会出错。所以请老老实实用std::swap。这是我在面试现场亲眼见过的“炫技翻车”案例不再用很短的时间就能验证。7.3 防御性检查swap 之后指针的移动方向在双路快排中有一个非常隐蔽的坑当你交换了nums[i]和nums[j]之后不要立刻让i和j--——你先得检查交换过来的值是否又满足了停止条件。正确做法可以是在 swap 之后立即i; --j;跳过已处理位置也可以让循环体回到顶部重新判断。这两种写法各有偏好我建议你选一种固定下来多练几遍形成肌肉记忆。面试现场的紧张氛围下最怕的就是边界条件的不确定性。8. 把这版代码跑起来验证与基准测试8.1 最小验证用例清单写完代码之后面试现场大概率会让你“跑几个用例验证一下”。我的习惯是准备这样一组用例覆盖各种边界情况#include iostream #include vector #include cassert void print(const std::vectorint v) { for (int x : v) std::cout x ; std::cout \n; } int main() { std::vectorstd::vectorint cases { {1, 2, 3, 4, 5}, // 升序最容易退化 {5, 4, 3, 2, 1}, // 降序 {5, 5, 5, 5, 5}, // 全相同 {3, 5, 3, 1, 3, 2, 5, 4}, // 有大量重复 {1}, // 单元素 {} // 空数组 }; for (auto nums : cases) { quickSortImproved(nums, 0, (int)nums.size() - 1); assert(std::is_sorted(nums.begin(), nums.end())); } std::cout all test cases passed!\n; }这组用例覆盖了最坏情况的输入有序、全部重复、单元素、空数组。如果你用第一版代码跑这个测试第 1 和第 4 个用例就会非常慢甚至崩掉用三数取中 双路版就能顺利通过。8.2 用时间和内存做一次直观对比如果在本地想验证优化效果可以做一个简单实验分别用基础版和优化版对 100 万个有序整数排序。你会看到基础版耗时可能是数十秒甚至更久递归深也可能直接栈溢出程序崩溃。优化版耗时稳定在几十到几百毫秒之间。这个差距在面试现场不需要真的跑数据用言语表述出来就足够有说服力了“基础版在 100 万有序数据上会直接栈溢出或慢到不可忍受而优化版可以轻松处理 1 亿以内的数据。”如果能配上一句“我实际跑过量级差距至少百倍”效果更好。8.3 环境配置提示VSCode 跑 C 的注意事项有些同学在面试复盘时想自己跑一下代码结果卡在了环境配置上。这里说一个最常见的问题在 VSCode 里配置 C 编译环境时至少要安装一个编译器Windows 上推荐 MinGW-w64 或 MSVC和 C/C 扩展插件。我踩过的坑是只装了扩展、没装编译器按住 F5 调试时报出“无法找到编译器”之类的错误。安装 MinGW-w64 后还需要确认编译器路径已加入系统 PATH。另外在 Windows 上编译时如果遇到fopen之类的安全函数报警告可以在编译命令中加-D_CRT_SECURE_NO_WARNINGS这是 MSVC 环境特有的问题或者在代码里用标准库的文件流而不是 C 风格的fopen。如果你只是为了刷算法题我建议用在线编译器比如 Compiler Explorer或者本地只装一个带 MinGW 的 Dev-C 也行。VSCode 的调试体验虽好但对新手来说配置成本略高不要把时间浪费在环境上重点还是理解算法本身。9. 从面试回归到工程快排思想在日常开发中的延伸9.1 不只是排序——partition 思想在“分组”场景的应用快速排序最值得借鉴的不是排序本身而是partition 的“按条件分组”能力。我写过很多需要把数组按某种条件分成两类的场景把负数移到数组左边、正数移到右边荷兰国旗问题的简化版。把有效数据和不合法数据分开而且要求保持相对顺序此时需要稳定 partition可以用额外数组也可以用类似“原地稳定分区”的技巧。把对象按某个属性值切成左右两半便于二分查找后续处理。这些场景如果不加思考地用std::partition标准库自带当然没问题但半笔试背景下能手写 partition其实也是对你代码能力的验证。用习惯了之后你会发现partition 本质上就是一个带条件的“分组筛选”操作比排序本身更常用。9.2 标准库的排序算法选择什么时候用 std::sort日常 C 开发中你几乎不需要自己写快排——直接用std::sort就行了。但理解快排仍然必要因为std::sort的实现原理introsort就是从快排演化来的理解快排之后你能预判std::sort在不同数据分布下的表现。如果你需要对vector的一部分区间排序std::partial_sort底层逻辑也和“选择第 k 个元素”的快速选择思想有关。当你需要稳定排序时std::stable_sort会额外分配内存并采用归并排序如果你不清楚快排和归并的稳定性差异很容易在工程选型上犯错误。9.3 大数据场景外部排序与分治的边界当数据量大到无法全部放入内存时比如几十 GB 的日志文件快排这类的“内存排序”就不适用了这时会用到外部排序也就是“先分块排序、再多路归并”的思路。这种场景下归并排序的“合”阶段反而成了主角——它的合并操作天然适合顺序读取磁盘、减少随机 IO。理解快排的“分”和归并的“合”各自主导的应用边界能让你在设计系统时多一层判断维度。10. 我的一些实战心得写快排的正确“姿势”文章的最后我想分享几个从面试现场和实际工程中沉淀下来的经验。不要背代码要背推理过程。背下来的代码在压力面试下很容易变形因为一个符号错了你自己都发现不了。但如果你脑中有一条清晰的推理链——“选基准 → 三数取中避免有序退化 → 双路指针处理重复 → 递归时小区间切到插入排序”那么即使一时忘了某行写法也能在纸上推出来。写代码前先把思路口头说出来。我面试别人时特别看重候选人写代码前的“口头前置说明”——比如“我打算先实现单路版本再优化”会让沟通成本大幅降低。如果你能做到面试官大概率会帮你排除一些非关键分歧你写起来反而更放松。一定要准备非递归版本。十个候选人里有六七个能写出递归版但只有两三个能顺畅地写出非递归版。这不是说非递归版本身有多难而是多数人没有刻意练过。花半小时把递归版改成显式栈版本性价比极高。类似的“套路性改造”在面试中还有许多——比如把 DFS 改成迭代版、把二分查找改成非递归版——只要掌握一次就能举一反三。把快排当作理解 C 特性的试金石。通过快排这道题你能同时展示引用传递的正确使用、对栈空间和递归深度的认知、对复杂度的直觉、甚至对标准库实现原理的了解。面试官问你一个问题你却能在一个答案里侧面展示多项能力这正是资深开发者与应届生拉开差距的地方。就说这些。如果你能把上面这些版本都亲手写一遍用我给的用例跑一遍再把那几个追问自己口头回答一遍那么下次面试遇到“手写快速排序”这道题你一定不会只是背出一个标准答案——你会让面试官觉得你是真的吃透了它。