快速排序在C语言学习和算法面试里几乎是一道必修坎。很多朋友能背出代码可一被追问“为什么分区后递归传的是p-1而不是p”就卡壳数据量一上来又可能在一个已经有序的数组上直接栈溢出。这篇我会从左右指针和单指针两种分区写法讲起把快速排序的边界细节拆开揉碎再给三数取中、小区间插入排序、三路快排、显式栈和尾递归优化这些实战变式最后整理我这些年排查快排问题的实际经验。代码都是完整可运行的C语言代码复制到本地编译器就能验证。适合正在学C语言数据结构、准备算法面试以及想让手写快排真正能上生产环境的读者。1. 快速排序的核心思想与基本实现1.1 分治核心与基准选择为什么“快”的本质是平衡快速排序的思想可以用四个字概括分而治之。但它和同样分治的归并排序有本质区别——归并排序的合并阶段发生在递归返回之后真正干活的是“合并”快速排序的分区阶段发生在递归之前真正干活的是“划分”。选定一个基准值把小于它的元素放到左边大于它的元素放到右边基准值自己落到最终位置然后对左右两个子区间递归重复。平均复杂度O(n log n)的推导很多教材直接给结论但真正值得记住的是快排快不快取决于分区之后左右两边是否大致等量。如果每次分区都接近对半开递归树高度约为log n如果每次把数组切成1和n-1递归树就变成一条长链复杂度退化成O(n^2)。所以后面所有变式本质都是在围绕“让基准更像中位数”和“别让递归深度失控”这两件事做文章。生活中的类比是整理书架随手抽一本书把比它薄的全放左边比它厚的全放右边这本书就定好了位置再对左右两摞分别重复。手气好每次抽到中间厚度的书很快就能整理完手气差每次抽最薄或最厚的就基本退化成一次移动一本慢到不能忍。基准元素怎么选最朴素的写法是选第一个或最后一个元素。这种选法实现最简单但恰好碰到数组已有序或接近有序时就会稳定进入最坏情况。这也是为什么工程级快排一定会引入三数取中和随机化它们不是炫技而是在压低最坏情况出现的概率。理解了这一层后面看变式代码时会觉得极其自然。1.2 Hoare分区基础版左右夹逼的原始快排Hoare分区是Tony Hoare在1961年提出的原始写法。它用两个指针从数组两端向中间移动左边找到大于等于基准的元素右边找到小于等于基准的元素然后交换。当两个指针交错时右指针的位置就是分区点。#include stdio.h void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; } int partitionHoare(int arr[], int low, int high) { int pivot arr[low]; int i low - 1; int j high 1; while (1) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) return j; swap(arr[i], arr[j]); } } void quickSortHoare(int arr[], int low, int high) { if (low high) return; int p partitionHoare(arr, low, high); quickSortHoare(arr, low, p); quickSortHoare(arr, p 1, high); }这段代码有三个要点do...while保证指针先移动再做判断初始i和j都在数组外侧所以第一次移动后一定指向有效下标。判断条件写成和而不是和。基准值本身就是天然的“哨兵”可以防止两个指针越过边界后继续跑向未定义内存。返回的j不是基准元素的位置而是右半区的左边界。因此递归区间是[low, p]和[p1, high]这和后面 Lomuto 分区的[low, p-1]、[p1, high]完全不同。很多人在这里写错结果要么漏元素要么死循环。Hoare 分区的平均交换次数比 Lomuto 少大数据量下的常数也更优但边界逻辑确实绕。初学阶段建议手写感受一下面试时如果不能保证一次写对优先选择下面这种更直观的写法。1.3 Lomuto分区简洁版教学首选变式地基Lomuto分区是后来教科书里更常见的版本。它只用一个指针i维护“小于等于基准区域”的末端再用一个指针j遍历数组每遇到一个不大于基准的元素就把它交换到i1位置。遍历结束后把基准从数组末尾交换到中间返回基准下标。int partitionLomuto(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quickSortLomuto(int arr[], int low, int high) { if (low high) return; int p partitionLomuto(arr, low, high); quickSortLomuto(arr, low, p - 1); quickSortLomuto(arr, p 1, high); }循环里用而不是是为了把等于基准的元素也放进左侧区域。如果改成当基准恰好是当前区间最小值时i几乎不动分区点跑到最左边递归右侧会包含 n-1 个元素退化风险很高。在大量重复元素时会让分区点总靠近边界复杂度接近O(n^2)。用虽然不能让重复元素完全跳过递归但比安全得多。两种分区方式对比对比项HoareLomuto基准通常选第一个或中间元素最后一个元素返回值的含义小于区与大于区的边界基准的最终位置递归区间[low,p]与[p1,high][low,p-1]与[p1,high]平均交换次数偏少略多代码可读性中低高变式扩展难度较高较低我的建议是面试时优先写 Lomuto因为它容易改对但心里要清楚 Hoare 的存在能解释两者的差异也是一种加分项。接下来要展开的优化变式大多基于 Lomuto 分区。2. 三个实战必改的经典变式把朴素快排直接扔到生产环境会遇到三个很典型的问题已有序数组上退化、递归末端函数调用开销过大、大量重复元素导致分区失衡。对应的解法是下面三套组合拳。2.1 三数取中法用三次比较干掉“最坏输入”先解决最坏输入。三数取中就是取区间首、中、尾三个位置的值把大小居中的那个选出来当基准。成本只有三次比较和最多三次交换收益却立竿见影对一个已经有序的数组它会直接选中中间值让分区保持平衡对一个随机数组它也比“无脑选末尾”更不容易连续碰到极值。实现思路先把三个位置的值排序然后把中位数交换到high位置再调用刚才的 Lomuto 分区。int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) swap(arr[low], arr[mid]); if (arr[high] arr[low]) swap(arr[low], arr[high]); if (arr[high] arr[mid]) swap(arr[mid], arr[high]); swap(arr[mid], arr[high]); // 中位数放到末尾当基准 return arr[high]; } int partitionMO3(int arr[], int low, int high) { int pivot medianOfThree(arr, low, high); int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; }为什么把中位数放到high因为 Lomuto 分区默认读取arr[high]作为基准这是一个“约定优于配置”的设计核心循环保持原样只改变基准的来源改动面最小。有人习惯在取中位数前再混入一次rand()我实测过加随机化对绝大多数数据没有质的提升反而增加了srand初始化和调试复现的成本。确定性的三数取中已经能挡住“已排序”和“逆序”这两种最常见的坏输入。它把最坏情况的触发条件从“输入恰好有序”变成“三个采样点都偏向同一侧”后者在实际数据里几乎不会出现。2.2 小区间插入排序递归末端的性价比之王快排递归到小区间时函数调用、栈帧分配和分区扫描的开销相对于那十几个元素的排序工作量来说太奢侈。插入排序的优势恰恰体现在小规模数组上常数小代码简单在接近有序的小数组上表现极好。这个变式的做法是在快排入口加一个阈值判断区间长度小于阈值时直接改用插入排序。#define INSERTION_THRESHOLD 16 void insertionSort(int arr[], int low, int high) { for (int i low 1; i high; i) { int key arr[i]; int j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } void quickSortHybrid(int arr[], int low, int high) { if (high - low 1 INSERTION_THRESHOLD) { insertionSort(arr, low, high); return; } int p partitionMO3(arr, low, high); quickSortHybrid(arr, low, p - 1); quickSortHybrid(arr, p 1, high); }注意这里判断的是区间长度high - low 1而不是下标差。我刚上手时写错过一次阈值10一个长度为11的区间因为high - low 10误触发插入排序。改用长度判断后逻辑才准确。阈值取多少我见过从5到20不等实际和编译优化级别、CPU缓存都有关系。一般先用16作为默认再对10、16、32三组值做基准测试选当前机器上最稳的。这个优化不是靠复杂度碾压而是靠“少调函数、少分配栈帧”赢的常数优势。观察递归调用次数加上这段之后会明显下降。2.3 三路快排重复元素是普通快排的“天敌”普通快排遇到全相同数组会怎样以 Lomuto 分区为例所有arr[j] pivot都成立i一路走到high-1分区点落在high递归左侧还有 n-1 个元素右侧为空。每轮只排掉一个元素复杂度O(n^2)递归深度O(n)。明明排序结果不需要任何交换朴素实现却要跑满整个过程。三路快排把数组分成小于、等于、大于三部分递归时只处理小于区和大于区等于区直接跳过。void quickSort3Way(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; int lt low; int gt high; int i low 1; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); lt; i; } else if (arr[i] pivot) { swap(arr[i], arr[gt]); gt--; } else { i; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }运行过程是三个区域的推移[low, lt-1]是小于区[lt, gt]是等于区[gt1, high]是大于区i从左向右扫描未处理部分。遇到小于基准的值交换到lt位置并同时推进lt和i遇到大于基准的值交换到gt位置但i不动因为换回来的元素还没被检查遇到等于基准的值直接i跳过。为什么不把等于区的元素也交换因为基准就是arr[low]等于区天然在左侧形成交换反而是多余的还可能打乱等于区内部顺序。全等数组下第一次循环把所有元素都归入等于区lt保持lowgt保持high递归立刻结束复杂度降为O(n)。这个思路在很多语言的标准库里都能看到影子Java 对基本类型排序使用的 DualPivotQuicksort本质上就是更极致的多路分区。手写排序时如果数据里重复值很多三路快排绝对值得优先考虑。3. 从递归到迭代工程级快排的避坑路径3.1 用显式栈替代递归调用防止爆栈朴素递归的隐患在数据规模大或输入恰好退化时就会暴露函数调用栈被递归撑爆。我在嵌入式环境遇到过线程栈只有64KB排个几万 int 就直接崩。这时候除了调大栈空间更可控的办法是把递归改成显式栈。实现思路很直接把待处理的区间压入自定义栈循环里弹出一个区间分区后把非空子区间重新压回去。#define MAX_RANGES 1024 typedef struct { int low; int high; } Range; void quickSortIterative(int arr[], int n) { Range stack[MAX_RANGES]; int top 0; stack[top] (Range){0, n - 1}; while (top 0) { Range cur stack[--top]; if (cur.low cur.high) continue; int p partitionMO3(arr, cur.low, cur.high); int leftLen p - 1 - cur.low; int rightLen cur.high - (p 1); // 小区间先压栈大区间后压栈保证大区间先被处理 if (leftLen rightLen) { stack[top] (Range){cur.low, p - 1}; stack[top] (Range){p 1, cur.high}; } else { stack[top] (Range){p 1, cur.high}; stack[top] (Range){cur.low, p - 1}; } } }这样压栈顺序栈中堆积的区间大小会呈递减趋势通常深度是O(log n)。注意如果不配合三数取中最坏情况下每次分区一边为0一边为n-1栈里区间数量仍可能达到O(n)所以MAX_RANGES要留足余量。显式栈只是把空间从系统调用栈转移到了数据结构栈并没有改变算法最坏空间复杂度。要真正压低最坏复杂度仍要配合平衡策略。3.2 尾递归优化把递归深度锁到对数级别除了显式栈另一个巧妙的优化是尾递归优化。核心做法是分区后只对较小区间递归较大区间通过循环继续处理。这样递归深度最坏是O(log n)代码也比显式栈更简洁。void quickSortTail(int arr[], int low, int high) { while (low high) { int p partitionMO3(arr, low, high); if (p - low high - p) { quickSortTail(arr, low, p - 1); low p 1; } else { quickSortTail(arr, p 1, high); high p - 1; } } }每轮循环处理当前区间先分区再比较左右子区间的大小小的递归、大的进入下一轮循环。递归的区间始终不超过当前区间的一半因此递归深度被限制在O(log n)。这个技巧即使编译器不做尾调用优化我们也能手工实现。工程里我优先用它因为改动小、可读性强。如果线程栈实在小再退到显式栈方案。3.3 通用排序接口把快排封装成 qsort 风格要处理任意数据类型的数组就需要设计通用接口。C标准库的qsort就是现成的参考void*指针表示起始地址size表示元素大小比较器函数指针负责决定元素顺序。#include stdlib.h #include string.h void swapBytes(void *a, void *b, size_t size) { char tmp[64]; memcpy(tmp, a, size); memcpy(a, b, size); memcpy(b, tmp, size); } int partitionGeneric(void *base, int low, int high, size_t size, int (*cmp)(const void *, const void *)) { char *arr (char *)base; // 保存基准值到临时缓冲区避免交换操作污染基准 char *pivot malloc(size); memcpy(pivot, arr high * size, size); int i low - 1; for (int j low; j high; j) { if (cmp(arr j * size, pivot) 0) { i; swapBytes(arr i * size, arr j * size, size); } } swapBytes(arr (i 1) * size, arr high * size, size); memcpy(arr (i 1) * size, pivot, size); free(pivot); return i 1; } void quickSortGeneric(void *base, int low, int high, size_t size, int (*cmp)(const void *, const void *)) { if (low high) return; int p partitionGeneric(base, low, high, size, cmp); quickSortGeneric(base, low, p - 1, size, cmp); quickSortGeneric(base, p 1, high, size, cmp); }这里藏着一个非常容易踩的坑基准不能用“指向arr[high]的指针”一直参与比较。因为在交换过程中arr[high]的内容可能被覆盖基准值就变了。我把基准值memcpy到临时缓冲区比较时用缓冲区里的副本最后再把它放回正确位置这样才能保证分区逻辑正确。工程上写业务代码直接用标准库qsort最省心它经过高度优化还根据元素大小选择不同的交换策略。自己实现通用版更多是为了吃透原理或者在内存受限、需要精细控制的场景里定制。4. 排序实战中的常见问题与排查技巧4.1 分区边界写错导致死循环现场还原与定位方法我带过不少刚开始写排序的新人手写快排十有八九栽在边界上。典型错误有这么几类Lomuto 分区递归写成quickSort(arr, low, p)而不是p-1导致基准元素被反复包含进区间最终死循环。Hoare 分区递归写成[low, p-1]和[p1, high]会漏掉分割点上的元素。交换条件写成而不是遇到大量相等元素时分区点总在边界附近性能严重退化。死循环的典型表现是程序卡住CPU占用100%数组越长越明显。排查时我最喜欢用两个手段第一在分区入口加一个递归深度计数器超过数组长度就打印错误并退出第二打印当前区间的low、high、pivot、i、j构造一个长度为3或4的最小复现用例肉眼就能看出循环出在哪里。还有一个高效的自测思路同时实现 Hoare 和 Lomuto 两个版本用随机数组跑一千轮比较两个版本的输出是否完全一致。这种对拍测试能一次性抓出一大批边界bug比自己瞪着代码找快得多。4.2 栈溢出与性能退化先判断是算法问题还是工程问题场景排序二十万 int程序直接崩。第一反应不一定就是递归深度问题。我的排查顺序是固定随机种子打印递归深度峰值确认是否接近数组长度。如果深度接近 n优先加三数取中或随机化基准。如果深度正常仍然崩溃再检查线程栈大小、编译链接参数或者把递归改为显式栈。性能退化不一定表现为崩溃更多时候是“慢得不像快排”。我常用一个全局计数器在分区入口递增统计分区调用次数。对十万随机数据正常快排的分区次数应该在 n×log2(n) 量级大约一百多万次如果看到几千万甚至上亿基本可以断言分区严重失衡。加几句代码让数据说话比反复猜原因高效得多。测试数据里一定要包含三组杀手级用例严格升序、严格降序、全相同值。这三组能快速暴露快排的最坏情况。再加一组随机大数组验证平均性能就足够覆盖绝大多数工程场景了。4.3 稳定性、原地性与空间复杂度快排的“三笔账”关于快排的一些常见属性整理成一张速查表属性快速排序平均时间复杂度O(n log n)最坏时间复杂度O(n^2)平均空间复杂度O(log n)递归栈最坏空间复杂度O(n)递归栈 / 显式栈是否稳定否是否原地是不需要与原数组等大的外部数组为什么不稳定分区交换可能改变相等元素的相对顺序。比如两个值相同的元素本来前面的被换到了后面排序后相对位置就变了。所以需要稳定排序的场景通常优先归并或插入排序而不是快速排序。这也是 C 标准库stable_sort存在的原因之一。空间复杂度为什么不是O(1)因为函数递归需要压栈平均深度log n最坏深度n。用显式栈不改变空间复杂度量级只是把空间从系统调用栈转移到了程序员可控的数据结构里。原地性则是另一个维度它描述的是“不需要额外等大的外部存储”而不是“不需要任何额外空间”。最后分享一个我自己的习惯手写快排时我默认从“Lomuto分区 三数取中 小区间插入排序 尾递归优化”这套组合开始因为它最容易改对覆盖情况也最全。如果数据里重复元素极多再切换成三路快排如果线程栈空间紧张再换成显式栈。无论哪个版本我都会准备一组包含重复元素、严格升序、严格降序和随机大数组的测试数据一次全跑完。排序算法的bug藏得深光靠眼睛看代码不如让机器跑两秒钟来得实在。