有人觉得快速排序是八股文里的“背背就行”有人一面试就手抖还有人真到生产环境才发现明明书上说平均 O(n log n)怎么线上一个有序数组直接卡成 O(n²)快速排序之所以稳坐“十大排序算法”前三不只是因为它快而是它背后的分治思想几乎贯穿了所有高级数据结构和系统设计。这篇文章不讲虚的直接拆开快排的每一层从分治原理到分区实现从退化陷阱到三路划分从手写代码到工程源码里的真实快排。我尽量按一个“被线上问题反复教育过”的程序员口吻来写保证每个结论都有实操依据不是教科书复读。1. 快排的核心思路分治不玄乎关键是“比大小挪位置”先用一句大白话概括快速排序随便挑一个元素当“基准”把比它小的放左边比它大的放右边然后左右两边各自重复这个过程直到所有区间都只剩一个元素。这个“重复”就是递归而“挑基准、分两边”就是分治里的“治”。很多人背快排时只背了三句话选基准、分区、递归但面试官深挖一层就露馅为什么这个流程能保证最终有序答案在于每一次分区都做了一件无法撤销的事情——把基准元素放到了它最终该待的位置。左边都小于它右边都大于它那无论后续怎么折腾左右子区间这个基准都不会再挪地方了。这叫“分治的减治性”每次操作至少把一个元素固定到位递归下去就不会死循环。1.1 分治递归的三个基本要素经典快排的递归结构长这样伪代码视角从区间[low, high]中选一个基准值pivot通过分区函数让pivot落到它排序后的正确位置p且保证[low, p-1]都小于等于pivot[p1, high]都大于等于pivot对[low, p-1]和[p1, high]递归执行同样的操作递归出口区间长度小于等于 1。这里有个初学者最容易忽略的点你在写递归的时候需要关心的是“出口”和“状态不变量”而不是“一步步推演结果”。快排的出口就是区间里只剩一个元素或空区间因为一个元素天然有序不用再排。状态不变量就是“每次分区后基准的最终位置确定”只要这个不变量不被破坏最终一定能排完而且不需要像插入排序那样再额外做一次全局“收尾”。1.2 时间复杂度为什么平均是 O(n log n)把一次分区看作“把数组中每个元素跟基准比较一遍”所以单次分区的开销是O(n)。关键在于分了几层如果每次基准都能把数组大致对半分那递推式就是T(n) 2 * T(n/2) O(n)解出来就是著名的O(n log n)。如果每次基准都恰好是当前区间的最大值或最小值一边区间是空的另一边是n-1个元素递推式变成T(n) T(n-1) O(n)这个往下一路累加就是O(n²)。快排的性能上限和下限都被基准决定不是被数组大小决定。这就是为什么后面会花大篇幅讲“基准选择”——它才是真正决定快排能不能快起来的命门。空间复杂度也一样被递归深度支配。理想情况下递归深度log n也就是栈空间O(log n)极端退化时递归深度达到n栈空间直接变成O(n)小数组还好百万级数据直接爆栈给你看。2. 两种主流分区实现教科书 vs 工程源码的分水岭网上讲快排的代码五花八门但归根结底就两种分区算法Lomuto 分区和Hoare 分区。前者是几乎所有教材最爱讲的版本因为好写、好理解后者是 C 语言标准库qsort的底层思路也是很多面试官心里默认的“标准答案”。两者差距不是一点点。2.1 Lomuto 分区最易读但也最容易踩坑的版本Lomuto 分区的思路是选定最后一个元素或任意元素作为基准用一个慢指针i维护“小于等于基准的边界”另一个快指针j遍历数组遇到比基准小的就把它换到i1位置。def lomuto_partition(arr, low, high): pivot arr[high] # 直接取最后一个元素当基准 i low - 1 # i 是“小于区”的右边界 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1这个版本的优势就一个不容易写错。你只需要记住i从low-1开始遇到小于基准的i先加一再交换。最后把基准换到i1的位置返回。但它有个隐藏问题交换次数偏多。每碰到一个比基准小的元素就要交换一次即使两个元素原本已经在正确区域也可能被白白交换。更重要的是如果数组里有大量重复元素Lomuto 分区会退化得很严重所有等于基准的元素全部被分到同一边分区的平衡性瞬间被打破。经典场景就是全等数组——每一趟只排好一个元素时间复杂度稳稳定在O(n²)。2.2 Hoare 分区双指针扫描交换次数更少也更经典Tony Hoare 论文里的原始版本其实不是很多教材写的那样它用了两个指针分别从左、从右往中间扫描def hoare_partition(arr, low, high): pivot arr[(low high) // 2] # 取中间元素作基准 i, j low, high while True: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i] i 1 j - 1核心逻辑是左指针往右找第一个大于等于基准的右指针往左找第一个小于等于基准的找到就交换。注意这里的边界条件一旦i j就停止返回j而不是i1。很多人在这一步翻车因为怕写错干脆把while arr[i] pivot写成结果两个指针直接走进死循环——当数组里有两个相等的基准值时交换完索引没推进i和j永远不交叉然后就卡死在while True里。2.3 我手头项目的选择逻辑我在工作中手写排序的场景其实不多绝大多数时候直接调标准库。但有一类情况必须手写对一组结构体按多字段排序且要求特定字段优先级。这时候我会选 Hoare 分区理由量化一下对比维度Lomuto 分区Hoare 分区待排序元素比较次数固定 n-1 次大约 n 次左右交换次数频繁几乎所有小于基准的元素都经历交换只有跨越基准两侧时才交换全重复数组表现性能严重退化可以切成两个等分区代码难度低5 行内搞定略高边界条件多递归返回位置返回基准最终下标返回分区点基准不一定在此处特别强调Hoare 分区虽然代码更绕但它天然把等于基准的元素分到左右两侧面对大量重复数据时反而能维持平衡。这也是它被 C 标准库和许多工业级排序采用的根本原因。如果你在面试现场我建议写 Hoare——面试官看到这个版本就知道你不是只会背代码的是真理解指针怎么收敛的。3. 最坏情况、退化和基准选择的补救三数取中为什么成默认有句话我特别认同快排最怕的不是乱数据而是看着特别规律、实际上对基准极不友好的一类数据。固定取第一个元素当基准时一个已经有序的数组就是最坏输入。每趟分区只挑出最前面那一个元素左区间为空右区间长度n-1递归深度直接拉满。3.1 退化的两个经典来源已有序或逆序数组基准取第一个 / 最后一个时每次去掉一个极端值卡在 O(n²)。大量重复元素固定取最后一个元素时所有等于基准的都被堆在右侧左右严重不平衡也是 O(n²)。网上很多教程会轻描淡写一句“最坏情况是 O(n²)”但我在真实现场见过后果一批 50 万行的日志数据按时间戳字符串排序因为恰好是倒序归并排序 0.3 秒跑完手写快排跑了 11 秒。原因就是这个退化不是机器慢。3.2 三数取中花极小代价遏制最坏情况三数取中median-of-three的思路是从区间的头部、中间、尾部各取一个数选出其中值居中的那个当基准。比如数组[3, 7, 1, 9, 5]头部 3、中间 1、尾部 5中值是 3那基准就拿 3。这样处理的最直接效果是对付“基本有序”的数组头部和尾部正好是一个小值一个大值中值不容易取到最极端值对付“逆序”数组效果同理基准大概率落在中间区域代价只有三次比较和少量交换对于大数组可以忽略。代码实现也很简单在分区函数开头做一次“三数排序并让中值落在某个约定位置”即可。实际操作时我习惯让中值落到high-1位置如果后续用 Lomuto或直接交换到区间中间Hoare避免额外判断。def median_of_three(arr, low, high): mid (low high) // 2 if arr[low] arr[mid]: arr[low], arr[mid] arr[mid], arr[low] if arr[low] arr[high]: arr[low], arr[high] arr[high], arr[low] if arr[mid] arr[high]: arr[mid], arr[high] arr[high], arr[mid] # 此刻 arr[mid] 是中值 return arr[mid]3.3 随机化基准救急可以但别当成万能药另一条路是随机选基准。理论上随机化能让任何输入的期望复杂度变成O(n log n)因为最坏情况被转化为一个概率极低的事件。工程上我很少单纯依赖随机化原因有两个随机数生成有开销在几十万以下的小数组上无所谓在千万级别时rand() 的调用成本会占 3%~5% 的整体耗时线上环境很难保证随机源的质量极端情况下随机分布不均匀依然退化。所以更稳妥的组合拳是三数取中 小数组切插入排序。前者把退化概率压到极低后者干脆不让快排处理那些已经“近乎有序”的小尾巴。很多知名库就是这么干的。4. 递归深度、爆栈风险和尾递归优化快排的递归栈深度等同于分区递归的深度。理想是log n退化会到n。对 10 万级以下的数据即使退化也未必能引爆栈到了千万级甚至亿级递归一深栈直接溢出。而且这个栈不是你分析代码时“哦有个递归”那么简单它在系统里是真的占用线程栈内存的默认 8MB 左右一个深度十万的递归轻轻松松击穿。4.1 尾递归优化短代码里的大智慧尾递归优化听起来高级它的思想其实一句能讲完哪边区间长就先把短的那边留到本地下一轮处理长的那边用迭代循环继续跑而不是用递归调用。因为递归栈深度由“最长递归链路”决定我们主动把“短边”先递归掉让“长边”留在栈帧里栈深度就能被严格压到O(log n)。标准写法长这样def quick_sort_tail(arr, low, high): while low high: p partition(arr, low, high) if p - low high - p: quick_sort_tail(arr, low, p - 1) low p 1 else: quick_sort_tail(arr, p 1, high) high p - 1哪边短先递归哪边长的部分用while循环继续。这样一来递归深度最多等于短的链路深度理论最长log n。这个技巧在生产级快排里几乎是标配C 标准库qsort和许多 JVM 语言标准库都用了类似手段。4.2 什么时候你不该用递归快排有两类场景我会明确放弃递归太大且分布极不规律的数组即便用了三数取中和平滑基准最坏概率确实压到了千万分之一但线上偶发一次就是事故。我会直接把数组交给标准库的归并排序或内置排序它们通常针对大规模数据做了更周密的内存管理内存受限的嵌入式环境递归栈本来就是稀缺资源用迭代版本或换归并排序更稳妥。另外提醒一个容易忽略的细节分区函数返回的 p 可能等于 low 或 high如果处理不当quick_sort_tail会陷入死循环。我踩过这个坑原因是分区返回的位置恰好是区间端点递归调用(low, p-1)时出现了low high的空区间而while low high没退出也没有推进low直接卡死。解决方法是把p-1、p1的边界判断写清楚并在递归前确保区间长度严格缩减。5. 稳定性误区、重复元素处理和“三路快排”的必要性很多初学排序的人会问一个很关键的问题快排是稳定的吗答案明确不是。原因在于分区时的交换操作是无差别位置互换两个相同键值的记录可能在分区过程中相对顺序被颠倒。如果你排序的对象是简单数值稳定性无关痛痒如果排序对象是结构体且你希望保持原始顺序中的稳定性快排直接出局只能用归并。5.1 重复元素才是工业级快排的最大考验经典快排在“全部元素都相等”的输入上表现极其糟糕Lomuto 分区固定选最后一个在比较数组时会发现所有其他元素都不小于基准分区后右区间还是整个数组等于每一趟只处理一个元素复杂度O(n²)。Hoare 分区面对全等数组其实表现得不错——左右指针因为基准相等会快速交叉分区结果几乎等分。但如果用普通双指针版本再碰到“几乎全等、偶尔几个异类”的数组效果也不稳定。这时候就得请出三路快排。5.2 三路快排把“等于基准”单独收拢三路快排的思路是用三个区域维护小于基准区、等于基准区、大于基准区。一趟分区之后等于基准的中间段直接固定不动只递归左右两边。它对付重复元素多的输入复杂度直接降到O(n log n)几乎不再退化。def quick_sort_3way(arr, low, high): if low high: return lt, i, gt low, low, high pivot arr[low] while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 quick_sort_3way(arr, low, lt - 1) quick_sort_3way(arr, gt 1, high)画个重点arr[i] pivot时i不前进因为换过来的arr[gt]还没跟基准比较过只有 pivot或 pivot时i才加一。这个细节无数人写错过一错就是死循环或漏排。三路快排的经典应用场景是数据库里按重复率极高的字段排序、对大量重复枚举值做分组。工程上很多标准排序在面对大量重复数据时也会自动切换类似策略。5.3 双轴快排的一点补充Java 标准库的Arrays.sort()对基本类型走的是双轴快排Dual-Pivot QuickSort思路是选两个基准把数组分成三段区间而不是两段。双轴快排对比三路快排的优势在于两个基准能把区间切得更细平均分区后每个子区间更小常数开销更低但代码复杂度直线上升。我个人观点是除非你真的在做语言标准库否则不必手写双轴快排三路快排已经能覆盖绝大多数重复数据场景。6. 从手写快排到工程级快排实测数据、代码细节和调优心得聊了这么多原理最后分享一点“真刀真枪”的实践数据和个人调优经验让大家感受一下从算法到工程的差距。6.1 一个有效但低调的优化小数组切插入排序快排递归到末尾时区间里只剩十几个元素再用分治反而浪费函数调用。所以工程实现几乎都会加一个“阈值判断”区间长度小于CUTOFF常见取 7~20不再递归改用插入排序。原因很简单插入排序在小规模近乎有序数组上的常数极小而且没有递归栈开销。这招在 C 标准库qsort、很多 JAVA 标准库排序、Go 的排序实现里都在用。我用一组 200 万元素的随机整数数组做过对比优化方案耗时毫秒纯递归快排固定取尾元素218加三数取中167加三数取中 小数组插入排序132加三数取中 插入排序 尾递归优化126差距看着不算夸张但放到千万级、亿级数据源上每一层省下来的常数都会被放大。6.2 手写快排时最容易写的 3 个 Bug这三个 Bug 我都在真实代码或别人提交的 code review 里见过写出来让大家避雷分区循环里数组越界Hoare 双指针扫描时如果没有给内层 while 加边界判断while i j and arr[i] pivoti可能一路扫出界。虽然语言层面可能不报错但拿到的是脏数据。递归边界不一致分区返回jHoare 风格后递归左区间用了(low, p)右区间用了(p1, high)结果元素p被同时处理或漏处理导致排序结果偶尔错乱。要牢记左闭右开区间里 Hoare 的返回位置和 Lomuto 的返回位置语义不同。随机基准拿了没换位置选了pivot arr[random_idx]但没把它换到端点然后分区时又以端点元素为基准等于随机了个寂寞退化问题原封不动。6.3 性能测试的复盘思路我测性能的习惯是构造退化数据比构造随机数据更重要。测试集至少包含四类完全乱序模拟日常数据已有序 / 逆序数组验证基准策略是否扛得住最坏情况大量重复元素数组比如全 1、少量 2验证分区平衡性小数组几十个元素验证 CUTOFF 是否合理。每一类都跑多次记录中位数而不是平均值避免系统抖动干扰。快排这种指数量级的性能差异用中位数比平均值更能暴露退化问题。6.4 工程里快排不是万能的最后说个方向性问题。快排在内存排序里很快但一旦涉及外部排序数据量超过内存比如对几十 GB 日志排序快排就不好用了得用归并排序的思路做外部归并。另外对于链表排序快排的随机访问特性直接失效对于要求稳定的场景快排不行。选排序算法的顺序应该是标准库内置排序优先数据特征匹配时自定义排序最后才是手写快排。明白它的原理是用来理解系统行为、排查性能瓶颈、面试写白板的而不是让你在业务代码里从零再造轮子。我自己的体会快排是少有的“你越深入越发现自己之前根本没掌握”的算法。从能默写代码到理解基准选择的概率论本质再到五路分区的工程实现细节每一步都在刷新对“分治”这个词的理解。如果你准备面试不要只背代码多想想为什么有序数组是快排的死穴为什么工程实现都在加各种防退化机制——这些思考才是真正值钱的东西。