上周线上面试，面试官让手写快速排序。我心想这还不简单，提笔就写双指针。结果跑完测试用例输出一半对一半乱，当场尬住。面试官的时间紧迫、自己的代码不敢保证正确，这种焦虑感是很多候选人共同的痛点。

回来之后我盯着代码半小时越看越不服气。上学时只学过冒泡、选择、插入——都是两层循环硬刚。时间复杂度 O，数据量大了直接挂。一直说快排是排序算法里的 “性能担当”，平均 O，但我始终没彻底搞懂它到底快在哪。每次写都是照着模板硬背，稍微变个基准选择方式就写错。

索性这次不背了顺着思路一步步推。把踩过的坑全捋了一遍，终于算是把这点东西嚼透了。

快排的主要原因：选个基准。拆成两半

说穿了快排的思路特别朴素，完全是 “分而治之” 的路子。你想给一整个数组排序，不用从头到尾一个个比。先随便挑一个元素当 “基准”。跑一轮下来把比它小的全扔到左边，比它大的全扔到右边。老实说，这一轮结束，这个基准元素的最终位置就定死了再也不用动。

剩下的事就简单了：左边那一半数组。再挑个基准，重复一样的操作；右边那一半也一样，拆到最终每个子数组只剩一个元素的时候。自然就是有序的，整个数组也就排好了。

我当时用排身高举例，一下就通了：班里同学乱站着。你随便拉一个人出来当参照，比他矮的站左边，高的站右边，这个人就站对位置了。接下来左边、右边各自再拉一个人继续分，用不了几轮所有人都能站好。老实说，

说白了就是把 “排一个大数组” 这个难事拆成 “排无数个小数组” 的小事。小事解决了大事自然成了，这就是简单讲的分治思想。

手搓一版能跑的代码

思路通了代码写起来顺畅。主要只有两个函数：

• partition负责把数组按基准拆开，并返回基准的最终索引；
• quickSort递归调用自己，对左右子数组继续排序。

// 分区函数：处理 区间。返回基准数的最终索引
function partition {
let i = left,j = right;// 以最左侧元素为基准
// 别问我为什么下面先动 j 指针。我踩了三次坑才记住
while {
// 从右往左找，第一个小于基准的数
while {
j--;}
// 从左往右找，第一个大于基准的数
while {
i++;其实，}
// 左右交换，小的去左边。大的去右边
nums] =,nums];}
// 指针相遇，把基准数换到分界线上
// 这一步是灵魂。换完基准的位置就彻底定了
nums] =,nums];return i，}
function quickSort {
// 区间只剩一个元素或者空，直接返回
if return;// 排好一个基准，拿到分界点
const pivotIndex = partition;// 递归排左边
quickSort;老实说，// 递归排右边
quickSort;}
// 跑个测试用例
const nums =;quickSort，console.log;
// 输出：

跑通那一刻还挺得意，以为“一切都搞定”。说起来，结果后面换几个测试用例，又踩到了三个常见坑。

我踩过的那几个经典坑

坑一这方面。指针移动顺序写反——排序直接乱套

最开始，我理所当然地先写左指针，再写右指针，以为谁先谁后无简单讲。结果数组直接乱成一锅粥，回顾流程后才发现：

• 选最左侧元素做基准时需要先移动右指针寻找第一个小于基准的数；
• 随后再移动左指针寻找第一个大于基准的数；
• 相遇后才把基准和i/j相遇的位置交换。

划主要： 基准在左端点 → 先动右指针**；基准在右端点 → 先动左指针**。

从坑二来看。有序数组直接跑——栈溢出

我随手拿了一个已经有序的大数组 测试，却立刻收到栈溢出错误。原因是这方面，

• 每轮都选最左端点作为基准；在有序数组里这会导致每次分区只“固定”左端点。一个元素归位，其余全部落在右区间；话说回来，
• 递归深度等于 n。导致调用栈爆炸，同时时间复杂度退化为 O。

实战调整： 随机挑选 pivot 或者“三数取中”可以极大降低最坏情况出现概率。

坑三这方面，误以为快排是稳定排序——相等元素顺序被打乱

S对等元素不会互换是错误认知。我用 测试后发现，两者顺序颠倒了。

原因： 快排在分区过程中会进行远距离交换。相等元素可能被跨越式调换位置，从而破坏原有相对顺序。快排是不稳定 的。如果业务要求保持相等元素顺序，请改用归并排序或稳定版快速排序实现。怎么说呢，

别把分治和递归搞混了

#误区清除：

• 递归一种实现技术。让函数自行调用自己，一层层缩小问题规模，接下来逐层返回结果。它像锤子，是完成任务的一件工具。
• 分治一种算法思想，“分 + 治 + 合”。把大问题拆成若干独立的小问题，各自解决后合并得到答案。它像搬运方案，是处理问题的大方向。
• KISS： 快排使用递归来实现分治。但如果你喜欢，也可以用显式栈来完成一样思路，只是代码更繁琐。

#为什么平均 O 能这么快？

• Pivots 把数组近乎平衡地二分： 递归深度约为 log₂n；每层遍历全部 n 个元素比较一下与交换 → O。乘积即 O，相比冒泡 O，数据量大时差距呈指数级增长。
• #原地排序优势： 不需要额外数组。仅依赖递归栈，对缓存友好，这也是工程实践中它被频繁采用的原因之一。

#没有万能算法：

• 数据量极小时插入排序因常数更低往往更快；
• 需要保持相等元素相对顺序时请选稳定算法；

#三条收获：

1. Avoid blind memorization. 算法不是死记硬背模板。而是理解背后的“分治+指针移动”过程，一旦掌握细节，就能自行推导代码。
2. Pitfalls are everywhere. 十几行看似简单。却隐藏“指针顺序”“递归终止”“pivot 策略”等致命细节，一处错误全盘皆输。
3. No silver bullet. 即使是最快速、最常用的快速排序，也有适配场景和局限性。懂得何时使用、何时放弃，比会敲代码更关键。

If you’ve also tripped over quick‑sort in an interview or on a real project,feel free to drop a comment below – let’s compare notes on “pain points” we’ve all endured.

---