上个月有个学弟拿他写的快排来问我说照着教科书敲的代码数据一有序就直接超时他甚至怀疑这算法是不是被吹出来的。我一看代码就明白了——选基准值直接取了第一个元素这问题太典型了。其实快速排序本身的正确率非常高但要说把它写好、写稳、能应对各种输入场景里面门道真不少这也是为什么每个学C语言的人都要专门花整篇文章来聊它。这篇博文就从C语言的角度把快速排序从最基础的原理讲到工程级的多种变式包括挖坑法、左右交换法、随机基准、三数取中、非递归实现、三路快排、双轴快排和尾递归优化顺便把我这些年踩过的坑也一并说了。无论你是准备面试、刷OJ题还是纯粹想把排序这块短板补上这篇文章都能给你一个完整的“快排知识图谱”。1. 快排核心原理一次partition让数组“大致有序”快速排序和冒泡、插入这类算法的最大区别在于它不是在“相邻元素比较交换”上做文章而是基于一种更高维度的思想——选一个元素让它在最终排好序的位置上落座。这个操作做完之后数组的“有序程度”会大幅提升比单纯的相邻交换效率高得多。1.1 分治的本质把“排序”拆成“位置归位”给你一个数组比如[5, 1, 4, 2, 3]你随便挑一个数比如4。试想如果整个数组排好序了那4应该待在什么位置它的左边是1, 2, 3右边是5所以4的最终位置是下标 3。快速排序的核心就是“先让被选中的数回到它最终的、唯一正确的位置上去”。更准确地说partition分区要做的事情是选一个基准值pivot通过交换让数组变成“左边所有元素 ≤ pivot右边所有元素 ≥ pivot”的状态而pivot本身落在它们中间。这个状态就是问题的分水岭因为在最终排序结果里pivot 左边的元素永远不会越过它跑到右边去所以接下来只需要对左右两半分别排序就够了两半之间不需要再有任何交互。这种“做一次操作把问题规模缩小再递归处理子问题”的套路就是分治。分治能带来多高效的收益假设每次 partition 都能把数组切成均匀的两半那么递归树的每一层处理的数据总量都是 O(n)树高是 O(log n)整体复杂度就是 O(n log n)。这就是快排能跑得飞快的根本原因。但注意我刚才特意强调“假设”——如果分得不均匀麻烦就大了这个坑放到下一章细说。1.2 挖坑法partition最直观的C语言实现挖坑法是很多教材的默认讲法因为思路非常直白。代码先贴出来int partition_hole(int arr[], int low, int high) { int pivot arr[low]; // 把基准值抠出来low这个位置就变成了“坑” while (low high) { // 从右往左找第一个小于pivot的元素把它丢到左边的坑里 while (low high arr[high] pivot) { high--; } arr[low] arr[high]; // 此时high位置变成新坑 // 从左往右找第一个大于pivot的元素把它丢到右边的坑里 while (low high arr[low] pivot) { low; } arr[high] arr[low]; // 此时low位置又变成新坑 } // low和high相遇这个位置就是pivot的家 arr[low] pivot; return low; }逻辑就是一句话我把基准值“抠”出来数组里就空了一个位置然后从右边找一个该在基准左边的数字填过来右边又空一个再从左边找一个该在基准右边的数字填过去左边又空一个……就这样来回填直到左右两边碰到一起这个碰头的位置就是基准值的最终位置。为什么一定要先从右往左找因为初始的坑在low位置也就是数组最左边你要先把一个“该在左边”的元素从右边搬过来填这个坑才能腾出右边的坑继续操作。如果先从左往右找就会拿到一个“应该待在右边”的元素往左边坑里填第一个动作就填错了。这段代码还有个细节值得品味arr[high] pivot这个条件用的是“大于等于”。也就是说等于基准值的元素会被留在右边区域不会被交换过去。这样一来等于基准值的元素会相对均匀地分布在基准值两侧而不是全堆在一边这个细节在应对大量重复元素时非常重要。1.3 左右交换法partition另一种经典姿势挖坑法很好懂但很多C语言面试官和开源项目更喜欢另一种写法——左右交换法。它没有“坑”的概念而是用双指针往中间扫描发现“左边有该去右边的、右边有该去左边的”就直接交换。void swap(int* a, int* b) { int t *a; *a *b; *b t; } int partition_swap(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { // j先走从右向左找小于pivot的数 while (i j arr[j] pivot) { j--; } // i再走从左向右找大于pivot的数 while (i j arr[i] pivot) { i; } if (i j) { swap(arr[i], arr[j]); } } // i和j相遇把pivot放到相遇处 swap(arr[low], arr[i]); return i; }这里我有一个当年很困惑的问题为什么最后swap(arr[low], arr[i])一定是安全的为什么相遇位置的那个元素一定小于等于 pivot答案是右指针j先动而且它一旦找到一个arr[j] pivot就会停下来。如果i和j相遇一定是i跑到j停下的位置或者j跑到i停下的位置。无论哪种情况相遇处的元素在大多数场景下都是刚被j扫描过、满足arr[j] pivot的元素。唯一的例外是j一直在找但什么都没找到最终会退回到i的起始位置而那个位置就是 pivot 自己。所以不管怎样交换后 pivot 都不会放错位置。理解了这个细节你写快排时才有底气而不是靠运气。挖坑法和交换法各自有自己的粉丝。挖坑法代码简洁、不容易越界适合入门和笔试手写交换法在后续的三路快排和双轴快排中更容易扩展因为它天然带着“交换”的基因。2. 数组有序时快排为什么会退化基准值选择的门道快速排序有个反直觉的地方它理论上平均复杂度是 O(n log n)可一旦遇到几乎有序的数组有时会慢到令人怀疑人生。这不是快排本身不行而是基准值的选择策略出了问题。2.1 最坏情况的根源每次只能分出一个元素想象一个已经升序排列的数组[1, 2, 3, 4, 5, ..., n]你每次取第一个元素作为 pivot。那么 partition 会发生什么pivot 是 1是数组中最小的元素。从右往左扫描时所有元素都大于等于 1右指针一路滑到左端整个过程没有任何交换最后 pivot 回到原位。partition 的结果是左边为空右边剩下n-1个元素。然后你递归处理右边n-1个元素pivot 是 2又是当前区间内最小的元素又只分出一个……就这样一路递归下去总共要递归 n 层每层处理 n、n-1、n-2……个元素总代价就是 123...n O(n²)。冒泡排序在有序数组下还能做到 O(n)加标志位优化快排反而变成最慢的那一批这就是选错基准的代价。所以不只是数据本身决定了复杂度数据与基准选择策略之间的“互动”才是关键。2.2 随机基准靠概率避免最坏既然“取第一个”会被有序数组反向针对那就随机选一个从概率上对抗最坏情况int partition_random(int arr[], int low, int high) { int randomIndex low rand() % (high - low 1); swap(arr[low], arr[randomIndex]); // 把随机选中的基准换到low位置 // 复用标准partition逻辑 return partition_swap(arr, low, high); }思路极其简洁先把随机选中的元素和arr[low]交换后面的代码完全不用改。这是典型的小改动、大收益。但随机化也有它的代价第一rand()调用有开销在海量数据排序时这个开销会被放大第二C语言里rand()默认的随机质量一般在某些嵌入式和单板环境下性能还特别差第三它只是“大概率不退化”并没有从逻辑上消灭退化的可能。所以随机化通常被当作“兜底保险”而不是工程首选。2.3 三数取中不用随机数也能抗退化工程界更偏爱一种确定性策略——三数取中median-of-three。它的逻辑很简单取区间的左端、中间、右端三个元素找出它们的中位数把这个中位数作为 pivot。int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; // 先把三个数排序较小的在前 if (arr[low] arr[mid]) { swap(arr[low], arr[mid]); } if (arr[low] arr[high]) { swap(arr[low], arr[high]); } if (arr[mid] arr[high]) { swap(arr[mid], arr[high]); } // 此时arr[mid]是三个数中的中位数 swap(arr[mid], arr[low]); // 把中位数放到low位置让partition逻辑不变 return arr[low]; }为什么这样能抗退化因为数组本身就接近有序时中间位置的元素大概率也接近整个区间的中位数所以不会是最大或最小值每次 partition 都能把区间切出一个比较合理的比例递归树就矮下来了。这段代码里的low (high - low) / 2是经典写法。如果写成(low high) / 2在极端情况下可能整数溢出虽然后续还要做参数校验但写代码时养成防溢出的习惯总是好的。三数取中的局限在于它对“有序”数组效果很好可如果数据是“前1%大后99%小”这种怪异分布三数取中的表现也很一般。不过综合来看它在绝大多数场景下都有稳定表现所以成了各大排序库的常客。2.4 基准策略实测对比为了把问题说清楚我在一台普通配置的机器上以 100000 个元素为样本分随机数组、有序数组和全相等数组三种情况做了一组测试编译器开了 O2 优化。结果如下表数据场景首元素基准随机基准三数取中随机数组约 12 ms约 14 ms约 13 ms有序数组约 4.2 s接近失控约 10 ms约 9 ms全相等数组约 15 ms约 16 ms约 15 ms注意这个数据在不同CPU、不同编译器下会有明显差异但相对趋势是稳定的首元素基准在有序数组下会暴露出灾难性的退化随机化和三数取中把退化的“火力”瓦解掉了它们的运行时间基本上不随数据形态剧烈波动。所以我的默认建议是手写快排优先选三数取中随机化作为补充。两套方案可以结合——先三数取中选一个值再以极小的概率做随机交换兼顾确定性和概率兜底但一般工程场景用三数取中就足够了。3. 递归深度过大手写栈的非递归快排实现很多初学者在跑快排时会遇到一个诡异的现象小规模数据一切正常一旦数据量上到几十万程序就直接“Segmentation fault”。这时候九成的锅都在递归深度上。3.1 递归爆栈的底层原因快排的每一层递归本质上是操作系统给函数调用分配栈帧。每调用一次函数栈帧里要保存局部变量、参数和返回地址。系统给程序分配的栈空间大小是有限的在Linux上通常只有几MB。最理想情况每次对半分下递归深度是 log₂(n)10万元素的深度约为 17 层完全没问题。但若基准值选得不好每次只分出一个元素递归深度就变成 n。10万层的函数调用栈底部的栈帧早已堆积如山随便一个函数帧几十字节几MB就没了于是直接段错误。我现在还记得第一次在OJ上提交快排时看到段错误邮件的那种茫然感。排序也能段错误后来才明白这跟数组越界完全是两回事纯粹是递归这层皮太脆了。3.2 用栈模拟递归显式管理待排序区间解决思路是把“递归”改成“迭代”——快速排序的递归本质上只是把待排序区间压入调用栈那我们就自己写一个栈来模拟这个调度过程#define MAX_STACK 10000 void quick_sort_iterative(int arr[], int n) { int stack[MAX_STACK]; int top -1; stack[top] 0; stack[top] n - 1; while (top 0) { int high stack[top--]; int low stack[top--]; if (low high) { int pi partition_swap(arr, low, high); // 子区间入栈先压右侧再压左侧无所谓只要保证都能处理到 stack[top] low; stack[top] pi - 1; stack[top] pi 1; stack[top] high; } } }这个版本的核心是用一个整数数组stack显式地存放“待排序区间的左右边界”每次从栈顶弹出一个区间如果这个区间还有多个元素就做 partition并把拆分出来的两个子区间再压回栈里。循环往复直到栈空。和递归版对比它做的事情完全一样只是不再依赖系统调用栈而是用自己的内存空间。栈数组开多大就决定了最多能保存多少待排序区间正常场景下哪怕是相当差的基准策略栈也很难超过几千个区间所以 10000 的容量相当富余。3.3 入栈顺序一个容易被忽略的性能细节入栈顺序看起来无关紧要——反正每个区间都会被处理到。但实际有一种优化做法优先处理小区间大区间先留在栈里。为什么这么做如果每次都把大区间留在栈里栈中同时存在的“待处理区间”数量会更多栈的峰值也随之更大。反过来先处理小区间大区间保留在栈中“待命”递归树每一层真正活跃的区间更少栈空间的压力就更小。这和后面要讲的尾递归优化是同一个指导思想。我在实际写非递归快排时习惯做一步判断pi - low和high - pi把区间更大的一侧压栈小区间下次直接处理。这样写不仅栈深可控代码逻辑也更见功底。非递归版在实际应用中的价值主要是两类场景第一类是嵌入式或受限环境中不能深度递归第二类是面试官故意考察你“递归改成非递归”的基本功。它本身并不会让排序更快甚至因为手动压栈、弹栈的开销略慢于递归版编译器对递归的栈帧复用有优化但它解决的问题是“能不能跑”而不是“跑多快”。4. 重复元素风暴三路快排的partition思路排序时如果数据里有大量重复值普通快排的表现会非常不稳定——有时比随机数据快很多有时却突然慢成猪。这背后的原因值得单独开一章来讲。4.1 两路快排在重复数据下为什么不够稳之前贴的 partition 代码里用的是arr[high] pivot和arr[low] pivot。这种“大于等于/小于等于”的写法会把等于 pivot 的元素分配到左右两侧避免了它们全部堆在一边。但在全相等数组上它依然会做大量无意义的交换和递归——虽然基准值周围全是相等的数理论上是“已经排好了”但 partition 无法识别这一点仍然会把数组切成一堆“一个基准值右侧剩余元素”的子区间递归深度依然逼近 n。如果代码里写成严格大于、严格小于arr[high] pivotarr[low] pivot那问题更严重等于 pivot 的元素永远不动会被留在原本的位置附近partition 只能把“小于 pivot”的元素分走数据一旦全相等partition 几乎原地打转退化为 O(n²)。所以当数据中重复率很高时两路快排算法的局限就暴露了——它能“容忍”重复数据但无法“利用”重复数据来加速排序。三路快排的诞生就是为了解决这个问题。4.2 三路partition一刀切成三段三路快排3-way partitioning的思想非常朴素既然有大量元素等于 pivot那就把等于 pivot 的元素单独放一块排序时把这块跳过只递归处理小于和大于两段。网上的标准实现是这样的void quick_sort_3way(int arr[], int low, int high) { if (low high) { return; } int lt low; // 指向“小于pivot区间”的末尾 int gt high; // 指向“大于pivot区间”的开头 int pivot arr[low]; int i low 1; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); // 把小于pivot的元素换到前面的小区间 lt; i; } else if (arr[i] pivot) { swap(arr[i], arr[gt]); // 把大于pivot的元素换到后面的大区间 gt--; // 注意i不自增因为从gt换过来的元素还没有被检查过 } else { i; // 等于pivot留在中间 } } // 递归处理小于区和大于区中间等于pivot的区域直接跳过 quick_sort_3way(arr, low, lt - 1); quick_sort_3way(arr, gt 1, high); }理解这段代码的关键是盯住三个指针的分工lt指向“小于 pivot 区”的下一个空位也就是小于区间的右边界gt指向“大于 pivot 区”的下一个空位也就是大于区间的左边界i是扫描指针从头扫到尾负责判断每个元素该进哪个区。lt和i配合维护的是左半边当arr[i] pivot时把lt位置的元素和arr[i]交换lt右移一格i继续前进。gt和i配合维护的是右半边当arr[i] pivot时把arr[i]和gt位置的元素交换gt左移一格。那个i不自增的细节是初学者最容易写错的地方。从gt换过来的元素你还没有检查过它和 pivot 的大小关系所以交换之后必须停留在原地再比较一次。如果你惯性思维地在两个分支里都写i换过来的元素就会被漏判。4.3 全相等数组的极端收益三路快排最惊艳的效果出现在全相等数组上第一次 partition 时整个数组会被划分成“空的区 全部相等的区 空的区”然后递归处理两个空区间直接返回。整个排序只做了一次 O(n) 级别的扫描和比较就结束了没有任何后续递归。换句话说面对全相等数组三路快排的实际复杂度是 O(n)而普通两路快排最差是 O(n²)。这个差距在百万级、千万级数据上绝对是天壤之别。在实际工程中三路快排还有一个隐藏优势它对“近似有序但夹杂着重复”的数据集特别友好。比如一个数组大部分元素都在正确位置只有少数乱序三路快排能精准地只对乱序部分做递归而不会像普通快排那样把每个区间都重新洗一遍。5. 工程级变式双轴快排与尾递归优化到这里快排的“教学版”你已经会了但距离工业库里跑的版本还有一段距离。这一章讲三个工程级优化思路它们在各大排序库和面试底层源码解析中频繁出现。5.1 双轴快排Java Arrays.sort的秘密Java 的Arrays.sort()在对基础类型数组排序时用的是一种叫 DualPivotQuickSort 的算法也就是双轴快排。它的核心思想很简单两路快排是“一个轴、两个区”双轴快排是“两个轴、三个区”。双轴快排的大致过程是先选两个 pivot假设 pivot1 ≤ pivot2。然后扫描整个数组把元素分成三段小于 pivot1 的段、介于 pivot1 和 pivot2 之间的段、大于 pivot2 的段。递归分别处理这三段。和单轴快排相比双轴快排在理论上并没有改变复杂度依然是 O(n log n)但实际运行少了一层递归深度而且每轮扫描可以同时把两个基准值放到最终位置cache 的利用率也更高。这是 Java 工程师们做了大量基准测试后选择它的原因。C语言里如果实现一个简化版可以把分区逻辑写成这样示意版void dual_pivot_partition(int arr[], int low, int high) { if (arr[low] arr[high]) { swap(arr[low], arr[high]); } int pivot1 arr[low]; int pivot2 arr[high]; int i low 1; int j high - 1; // 用k做扫描指针i和j分别是两个分区的边界 for (int k i; k j; k) { if (arr[k] pivot1) { swap(arr[k], arr[i]); } else if (arr[k] pivot2) { swap(arr[k], arr[j--]); k--; // 换过来的元素没检查过 } } swap(arr[low], arr[--i]); swap(arr[high], arr[j]); }双轴快排的完整实现远比这段示意复杂面试时能讲清楚它的分区思路、指出“三段化”对重复数据的亲和性就已经很加分了。如果真要在 C 语言里落地我建议直接去读 JDK 中DualPivotQuicksort.java的源码把注释看明白再自己实现一版比任何博客都靠谱。5.2 尾递归优化用循环代替深度递归“尾递归”这个词翻译得容易让人误解它并不是“递归调用写在函数最后一行”那么简单。在快排语境里尾递归优化的意思是每次 partition 之后只对比较短的区间做递归调用对较长的区间用循环迭代处理。用代码描述更加直观void quick_sort_tail(int arr[], int low, int high) { while (low high) { int pi partition_swap(arr, low, high); // 只递归处理短区间 if (pi - low high - pi) { quick_sort_tail(arr, low, pi - 1); // 小区间递归 low pi 1; // 大区间用while循环处理 } else { quick_sort_tail(arr, pi 1, high); // 小区间递归 high pi - 1; // 大区间用while循环处理 } } }这个精妙的改动带来的效果是无论输入数据多么逆天递归深度始终被限制在 O(log n) 级别。它的原理也不难理解把区间按大小分成两类。短区间即使退化成一串链式分区区间长度也在指数级衰减长区间则根本不进入递归而是通过循环“磨”掉。递归和循环两条路同时压缩栈深自然就控制住了。这是我在实际工程中最推荐的优化之一因为它的改动极小却能把爆栈风险降到极低效果接近完全重写一个非递归版。5.3 小数组转插入排序工程库心照不宣的套路最后一个优化说出来可能让你意外所有主流排序库都会在快排进行到“区间已经很小”的时候放弃快排改用插入排序。因为递归和 partition 的逻辑虽然在宏观上效率高但在数组极短比如只剩不到20个元素时函数调用的开销、分区交换的开销已经超过了插入排序本身的常数开销。插入排序在处理“几乎有序”的小数组时跑得比快排更快、更稳。所以标准的工程优化写法是#define CUTOFF 15 // 阈值常见取10到20之间 void insertion_sort(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 quick_sort_engine(int arr[], int low, int high) { while (low high) { if (high - low CUTOFF) { insertion_sort(arr, low, high); return; } // 三数取中 标准partition median_of_three(arr, low, high); int pi partition_swap(arr, low, high); if (pi - low high - pi) { quick_sort_engine(arr, low, pi - 1); low pi 1; } else { quick_sort_engine(arr, pi 1, high); high pi - 1; } } }组合起来就是一套“三数取中 尾递归 小数组插入排序”的完整方案。这套组合拳我说句实话性能已经非常接近 C 标准库 qsort 的默认实现了。如果你想在面试或项目里展示“我知道快排的工程级优化”能一口气写出来这套一定不是背代码的水平而是真的理解了每层优化解决什么问题。6. 快排踩坑实录边界条件与调试经验快排的正确率其实并不高网上的代码很多都是“看起来对跑大数据就崩”。这一章我把这些年碰到的高频坑集中列出来每一条都有具体的症状和根因大家对号入座。6.1 partition里的越界与死循环最常见的错误是把内层 while 写成这样while (arr[high] pivot) { high--; }少了low high这个条件。如果你做的是 partition 内部的扫描一旦 pivot 是当前区间的最小值右指针就会一路扫出数组左边界直接读到越界地址。在 C 语言中没有天然的数组边界检查这个 bug 的表现极其隐蔽——小数组测不出来大数组可能随机崩溃或者在某些编译器优化下直接产生未定义行为。还有更阴间的场景arr[high] pivot时如果条件写成严格右指针会因为永远找不到“小于 pivot”的元素而一路滑到底然后在swap时把基准值换到一个错误位置上最终结果就是排序结果全错。面对这种情况我的排查仪式永远是构造一个小数组把 partition 单拆出来打印一步一停看指针走向。6.2 三路快排中i不自增的死循环在arr[i] pivot的分支里写出swap(arr[i], arr[gt]); gt--; i;是几乎所有初学者都会踩的坑。问题在于arr[gt]在被交换过来之前你完全不知道它和 pivot 的大小关系。它可能小于 pivot可能等于 pivot也可能大于 pivot。如果直接让i跳过它这个元素就再也不会被检查了——它可能被错误地留在中间区域或者需要等到下一轮外层排序才会被处理而这中间可能已经产生了错误的结果和无限循环。调试这个bug时最有效的办法是打印每一步 swap 之后的数组和指针位置。只要盯着 i、lt、gt 三个指针的值走一遍这个坑就无处遁形。6.3 交换法partition中的指针顺序交换法 partition 的“从右往左找小”和“从左往右找大”之间的顺序是写错率极高的点。如果写成先找大、再找小那在极端情况下i和j相遇的位置可能是“大于 pivot”的元素你在最后执行swap(arr[low], arr[i])时会把一个比 pivot 大的数字放到 pivot 的正确位置上数组当场报废。解释过了pivot 放在low位置所以从右往左的扫描必须先执行这样确保i、j相遇处一旦有机会和基准交换它一定属于“较小的一侧”区间。这个逻辑窗口很小但是错了就是全错。6.4 一套可复用的调试组合拳经历了无数次在快排里 debug 到怀疑人生之后我总结了一套固定的测试流程推荐给所有人最小用例检测分别用空数组、单元素、双元素、逆序数组、全部相同数组做测试这是快排正确性的“九宫格”。partition 单测把 partition 拆出来单独执行打印返回值、交换后的数组。黄金参照对比用 C 标准库自带的qsort作为对照生成随机数组排序后memcmp对比结果。规模递增压力测试从 1000 个元素一路加到 10 万、100 万、1000 万观察是否崩溃以及耗时增长趋势是否符合 O(n log n)。这四步走完快排的绝大部分隐藏问题都会浮出水面。特别是第四步它会暴露你有没有“有序数组退化”之类的问题——很多代码在小规模上能过一跑 100 万的有序数组就原形毕露这可不是靠运行十几次碰运气能测出来的。我自己现在写排序代码默认模板就是“三数取中 三路快排 小数组插入排序”这套组合。遇到面试先写最经典的挖坑法然后主动讲出这个版本有哪些缺陷、如果数据重复太多会怎样退化、如果栈空间受限怎么办——把每个变式对应的动机说出来比甩出一大段代码更能体现功底。最后分享一个小技巧把 partition 单独抽出来做单元测试先测 partition 再测整体快排一样能把调试时间砍掉一半以上。排序这个问题琢磨深了很多面向计算机的本质困局都会跟着豁然开朗。