快速排序是我在数据结构课上第一次真正“看懂”的排序算法当时用的就是最朴素的版本——把区间里第一个元素拿出来当枢轴。这一个看似随意的选择后来反复出现在各种习题、面试题和比赛模板里。以第一个元素为枢轴的优点是代码结构直观、手算方便缺点是当输入恰好有序或逆序时性能会跌落到平方级严重的直接栈溢出崩掉。这篇文章不是搬运教材而是我把这个经典实现从头到尾写了一遍之后的完整记录partition 里每个条件为什么这样写、边界怎么卡、实测中踩到哪些坑以及在不推翻原有逻辑的前提下有哪些立竿见影的改良手段。无论你是刚接触快排的初学者还是想把排序打牢再准备面试的人这篇都值得从头看一遍。1. 拿第一个元素当枢轴到底图什么——选型逻辑与最坏情况预警1.1 分治思想的一行话版本选定枢轴分割数组快速排序本质上是一种分治算法核心逻辑可以归纳成三步在待排序区间里挑一个元素当枢轴pivot标题场景下就是直接取arr[low]把区间内所有比枢轴小的元素挪到它左边所有大于等于它的元素挪到右边这一步称为分区partition对枢轴左右两个子区间递归重复上述过程直到每个区间只剩一个元素。分治思想用生活类比最好懂整理一摞扑克牌时先抽第一张牌当基准把比它小的牌放左边比它大的牌放右边然后分别把左右两堆继续按同样规则整理。快速排序值钱的地方在于所有移动都在原数组上就地完成不需要额外申请一整块和原数组等大的空间。这一点在数据量上来之后差距非常明显。1.2 第一个元素当枢轴的三个理由市面上绝大多数教材讲快排时都会从“第一个元素作为枢轴”入手这确实有它的道理实现门槛最低不需要生成随机数不需要计算中间位置拿arr[low]直接开干少一层出错可能。和经典“挖坑法”天然契合先把arr[low]的值保存到pivot这个位置就变成一个“坑”等右边扫描到的小数填进来随后右边又出现新坑等左边扫描到的大数填进去。整个过程思路清晰手算演算也很直观。便于观察分区本质当枢轴落在两端之一时反而更容易让人理解“为什么分区会让数组局部有序”。但也必须把话挑明第一个元素当枢轴等于把性能命脉交给了输入数据的顺序。如果待排序数组已经升序或降序排列每一轮分区后枢轴都待在端点附近左右两个子区间极度不平衡一个接近 n-1另一个为 0递归树退化成一条长链时间复杂度直接变成 O(n²)。这个问题不是理论恐吓后面第 4 章我会用实测数据给你看它到底有多严重。1.3 常见教学实现路线怎么选围绕“第一个元素作为枢轴”这个题目实际存在几种不同风格的分区写法初学者经常被网上各种版本搞混。我先把主流三种列出来实现流派核心思路特点适合场景挖坑法取出 pivot 后左右指针交替填坑思路直白边界相对好讲清楚教材讲解、入门手写Lomuto 分区单指针 i 维护小于 pivot 的边界j 遍历区间代码极短和快选quickselect衔接自然算法题、模板库Hoare 分区左右双指针互相交换逆序对常数更优但返回值不是 pivot 实际位置容易写错性能敏感场景本文主线选择挖坑法因为“以第一个元素为枢轴”这个命题下挖坑法是最贴合题目语义、也最容易一次性写对的版本。Lomuto 和 Hoare 的代码我会在后面的对比里适当提到但完整流程重点讲挖坑法。2. 挖坑法partition手写实录指针移动顺序一个都不能错2.1 挖坑法的核心循环右找小、左找大、填进去直接看代码这是整个算法的灵魂int partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { // 从右向左找第一个小于 pivot 的元素 while (low high arr[high] pivot) { high--; } // 把它填到左边的坑里high 位置变成新坑 arr[low] arr[high]; // 从左向右找第一个大于 pivot 的元素 while (low high arr[low] pivot) { low; } // 把它填到右边的坑里low 位置又变成新坑 arr[high] arr[low]; } // low high 时这个位置就是 pivot 的最终归属 arr[low] pivot; return low; }我建议你不要死记代码而是理解这个过程先把第一个位置的数抽走此时low就是一个坑右侧指针high向左扫遇到比 pivot 小的数就把它搬到坑里随后左侧指针low向右扫遇到比 pivot 大的数就搬到右侧新坑两侧反复交替直到两个指针碰头把保存在pivot里的值放到碰头位置。每个数最多被搬动一次分区这一步整体是 O(n)。2.2 三个边界条件的具体含义这一段是手写快排最容易翻车的地方我拆开讲外层while (low high)保证左右指针没有交叉一旦碰头就停止扫描。少了这个条件low和high互相越界是板上钉钉的事。右扫描arr[high] pivot这里必须用“大于等于”。含义是只要当前元素不小于 pivot就继续向左挪直到碰到第一个严格小于 pivot 的元素才停。如果你图省事写成那么遇到和 pivot 相等的元素时high会停下来把等于 pivot 的值也当作“小数”填进左边坑里分区逻辑瞬间错乱。左扫描arr[low] pivot同理必须用“小于等于”跳过所有和 pivot 相等的元素只找严格大于 pivot 的大数。内层扫描也要带low high这一点特别容易被忽略。比如整个区间全是大于 pivot 的元素时右扫描如果没有low high保护high会一路降到-1直接访问数组越界内存程序行为立刻变得不可预测。我见过很多人粘了模板代码能跑但一上手自己写就挂挂的位置十有八九就是这三处条件。记住一个口诀右扫停小左扫停大等于全跳过碰头即停手。2.3 等值元素的处理策略加不加等号的分水岭等值元素是快排的经典杀手。一个全为相同数字的数组是检验分区写法是否严谨的试金石。假设数组是[5, 5, 5, 5]如果右扫描条件写成arr[high] pivot那么第一次扫描时arr[3] 5并不大于 5high直接停住然后执行arr[low] arr[high]把这个 5 搬到左边坑紧接着左扫描同样因为arr[low]不是严格大于 5 而立刻停住又把同一个 5 搬回右边。两个指针在同一个位置反复交换永远无法收敛这就是死循环的根源。如果按我上面写的和全相同数组会怎样右扫描一路跳过所有等于 pivot 的元素high最终走到与low相同的位置外层循环退出pivot 原地落位。虽然它在全相同数组下仍然会退化成 O(n²) 的分区次数但至少逻辑是收敛的不会卡死。这个区别在实战中就是“程序崩溃”和“程序能跑但慢”的本质差异。3. 完整C代码与测试验证从能编译到确认排序正确3.1 模块划分与完整代码清单完整实现应该拆成几个功能单一的模块交换函数、分区函数、递归排序函数、验证函数、打印函数。下面是一份可以直接复制到本地编译运行的完整代码#include stdio.h #include stdlib.h #include time.h void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } int partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { while (low high arr[high] pivot) { high--; } arr[low] arr[high]; while (low high arr[low] pivot) { low; } arr[high] arr[low]; } arr[low] pivot; return low; } void quickSort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos 1, high); } } int isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main(void) { srand((unsigned)time(NULL)); int demo[] {6, 1, 8, 3, 5, 9, 2, 7, 4}; int n sizeof(demo) / sizeof(demo[0]); printf(排序前); printArray(demo, n); quickSort(demo, 0, n - 1); printf(排序后); printArray(demo, n); printf(结果验证%s\n, isSorted(demo, n) ? 通过 : 失败); int n2 10000; int *arr2 (int *)malloc(n2 * sizeof(int)); for (int i 0; i n2; i) { arr2[i] rand() % 10000; } clock_t start clock(); quickSort(arr2, 0, n2 - 1); clock_t end clock(); printf(n%d 随机数组耗时%.3f 秒排序结果%s\n, n2, (double)(end - start) / CLOCKS_PER_SEC, isSorted(arr2, n2) ? 通过 : 失败); free(arr2); return 0; }这份代码只依赖标准库没有额外配置任何带 C 编译环境的地方都能直接跑通。3.2 测试用例设计覆盖五类输入很多人写完排序只拿一组随机数测一下就宣告完事这远远不够。我的经验是至少覆盖五类输入输入类型构造方式考察目标随机数组rand() % 范围常规正确性升序数组for (i 0; i n; i) a[i] i;最坏情况退化降序数组for (i 0; i n; i) a[i] n - i;最坏情况退化全相同数组for (i 0; i n; i) a[i] 7;等值元素处理、死循环风险边界小数组空数组、单元素数组、两个元素数组递归终止条件空数组和单元素数组在quickSort里直接走if (low high)这个保护什么都不用做这正好验证了递归出口写的对不对。两个元素的数组则能快速暴露 partition 交换逻辑里“枢轴最终位置偏移一位”这种经典错误。3.3 断言验证与输出结果isSorted函数承担最终裁判角色从第二个元素开始只要发现前一个大于后一个就返回 0。用断言而不是肉眼观察是测试自动化最基本的一步尤其后面数据量上来后肉眼基本没法判断排序是否正确。我在本地跑上面代码时小数组的输出长这样排序前6 1 8 3 5 9 2 7 4 排序后1 2 3 4 5 6 7 8 9 结果验证通过n10000 随机数组那行会显示一个很小的耗时数字同时结果验证为“通过”。这只能证明“随机数据下算法是对的”离“算法在任何输入下都可靠”还差得很远——这正是下一章要实测的内容。4. 实测暴击当输入变得“刁钻”第一个元素枢轴的表现4.1 有序数组与逆序数组的退化实验把数组预先构造成严格升序然后扔给这份代码排序。你会发现一个非常反直觉的现象居然比随机数组慢得多甚至根本跑不完。原因要从递归结构上解释。升序数组里第一个元素是全局最小值分区后 pivot 回到索引 0 的位置右侧剩下 n-1 个元素继续递归下一轮又取这 n-1 个元素里的第一个作为 pivot它又是当前区间的最小值。递归树就此长成一条单链表每一层只减少一个元素总比较次数变成n (n-1) (n-2) ... 1 ≈ n²/2。降序数组同理只不过 pivot 变成每次区间的最大值退化的方式一模一样。我在自己的测试机上试过n50000 的升序数组栈直接爆掉程序段错误退出而 n50000 的随机数组排序耗时在几十毫秒级别肉眼感知不到任何压力。同一份代码换一种输入就是“能用”和“崩溃”的两极。这就是输入敏感性的真实代价。4.2 全相同数组无限递归风险的现场实测全相同数组是另一个高频雷区。如果分区扫描条件里的等号写错程序会陷入死循环即使像我上面那样把等号写对它也并不会因为“所有元素相等所以无需排序”而快速结束。分区结果始终是 pivot 原地落位左侧区间为空右侧区间长度减一递归照样退化成 O(n²)。全相同数组的排序时间同样会从“毫秒”变成“肉眼可见的慢”。但这里有一个很微妙的区别扫描条件写对全相同数组只是慢不会死循环扫描条件写错则是 CPU 占用直接拉满程序永远不会返回。这在调试时是两种截然不同的症状。先确认你写的是和再谈性能优化顺序不能反。4.3 性能数据记录n10000 与 n50000 的对比为了把退化程度量化我做了一组简单对照实验。三个数组都是同样的长度分别填充随机数、升序数、全相同数用同样的clock()计时数据规模随机数组升序数组全相同数组n10000极快通常不到 0.01 秒勉强能跑完但耗时明显上升明显变慢递归深度接近 10000n50000毫秒级完成程序段错误栈溢出程序段错误栈溢出第 1.2 节里说的“最坏情况”在这一组数据里已经完整兑现。升序数组和全相同数组在 n50000 时就因为递归调用层数过深把默认栈空间耗尽。这还不是算法逻辑本身的极限而是 C 运行时栈帧大小给递归实现的硬限制。5. 三个升级方向从入门实现到能抗住压的工程实现5.1 策略一随机化枢轴随机化枢轴几乎是性价比最高的单行优化。思路很简单在区间内随机选一个位置把该位置的元素和arr[low]交换然后继续走挖坑法。这样无论输入是升序、降序还是全相同每次枢轴落位在哪个位置都变成随机事件坏情况的出现概率被压到极低。int randomIndex low rand() % (high - low 1); swap(arr[low], arr[randomIndex]); int pivot arr[low];我测试下来随机化后升序输入不再崩溃排序时间回到“毫秒级”因为每次枢轴平均落在区间中部附近递归深度从 n 降到 log n 级别。代价仅仅是每次分区生成一个随机数几乎可以忽略。需要注意rand() % 区间长度在区间长度特别大时有轻微不均匀性但对快排这种对均匀性要求不高的场景完全够用。5.2 策略二三数取中三数取中比随机化更稳因为它刻意避免最坏情况。取区间左端、右端、中点三个位置的元素把这三者的中位数换到第一个位置当枢轴。这样即使输入是升序或降序枢轴也会落在整个区间的中位数附近递归树天然平衡。经典的三数取中比较交换套路是这样int mid low (high - low) / 2; if (arr[mid] arr[low]) swap(arr[mid], arr[low]); if (arr[high] arr[low]) swap(arr[high], arr[low]); if (arr[high] arr[mid]) swap(arr[high], arr[mid]); swap(arr[mid], arr[low]);三次比较加三次可能的交换把三个数中从小到大排一遍取出中间值。三数取中对近乎有序的数据效果立竿见影而且不需要引入随机数行为可复现调试时比随机化更友好。代价是每次分区多几次比较常数略有上升但换来的是最坏情况被大幅稀释这笔交易非常划算。5.3 策略三小数组插入排序快速排序在区间很小的时候递归和分区调用的开销开始超过排序本身的开销。工程实现里常见的做法是当区间长度小于某个阈值比如 16时不再递归而是直接用插入排序收尾。void quickSort(int arr[], int low, int high) { if (high - low 1 16) { insertionSort(arr, low, high); return; } int pos partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos 1, high); }插入排序在 n 很小的时候虽然也是 O(n²)但常数极小而且对缓存友好实际速度往往不输继续做几层快排递归。这个小优化也是把递归深度再压低一层让栈溢出风险进一步下降。阈值选 16 还是 32取决于机器我习惯用 16效果已经很稳。6. 踩坑复盘从栈溢出到结果错乱我的一份排错索引6.1 症状一递归没有出口导致栈溢出如果你发现程序跑小数组正常跑大数组直接死掉或段错误第一步先检查quickSort的递归调用区间是否真的在变小。一个常见的低级错误是把右半区间写成quickSort(arr, low, pos)而不是quickSort(arr, low, pos - 1)。当pos low时右半区间变成quickSort(arr, low, low)区间没有缩小如果这时low high的判断又恰好成立就会无限递归。排查方法很简单在quickSort开头加一行打印当前low、high、pos跑一个升序小数组。一旦发现某次递归的参数跟上一层完全一样立刻就能锁定问题。6.2 症状二排序结果仍有未排序区间这种问题最隐蔽。以arr [4, 2, 6, 1, 3]为例我手动走一遍正确的挖坑法第一轮 partition 后数组变成[3, 2, 1, 4, 6]返回 3枢轴 4 到达最终位置左区间[3, 2, 1]继续排序右区间[6]只剩一个元素自然有序。如果你发现结果里出现“局部有序但没排全”的现象多半是分区返回的位置不是 pivot 实际落位而是偏移了一个单位导致左右区间的切分点覆盖了正确位置。这时候不要瞎猜把 partition 返回值和每次分区后的数组打印出来和手算结果对照通常一眼就能看出偏移。6.3 症状三性能忽快忽慢如果你觉得代码没问题但性能时好时坏先检查是不是输入数据本身在变化。第一个元素当枢轴的实现性能曲线完全看输入脸色随机数据秒完有序数据卡死全相同数据爆炸。这种“忽快忽慢”不是玄学而是算法输入敏感性的直接体现。解决办法不外乎第 5 章那三招——随机化、三数取中、小数据切插入排序。我个人的偏好是“三数取中 阈值插入排序”的组合既保留了可复现性又把最坏情况的概率压到工程可接受范围。我在实际手写排序算法时的体会是用第一个元素当枢轴做练习最大的价值不是写出一个多快的排序而是把分区、边界、递归、退化这些底层机制彻底暴露在你面前。它让你在踩过坑之后真正理解为什么工业级排序实现里从来看不到这种朴素写法也让你面对“为什么快排不如宣传的那么快”这类问题时能给出有实验支撑的答案而不是背课本结论。这个打法值得每个学排序的人从头走一遍。 
长河君 · 2026/10/21 2:51:30 · 阅读 1.2k 快速排序第一个元素做枢轴：挖坑法实现、边界条件与性能优化实战
快速排序是我在数据结构课上第一次真正“看懂”的排序算法当时用的就是最朴素的版本——把区间里第一个元素拿出来当枢轴。这一个看似随意的选择后来反复出现在各种习题、面试题和比赛模板里。以第一个元素为枢轴的优点是代码结构直观、手算方便缺点是当输入恰好有序或逆序时性能会跌落到平方级严重的直接栈溢出崩掉。这篇文章不是搬运教材而是我把这个经典实现从头到尾写了一遍之后的完整记录partition 里每个条件为什么这样写、边界怎么卡、实测中踩到哪些坑以及在不推翻原有逻辑的前提下有哪些立竿见影的改良手段。无论你是刚接触快排的初学者还是想把排序打牢再准备面试的人这篇都值得从头看一遍。1. 拿第一个元素当枢轴到底图什么——选型逻辑与最坏情况预警1.1 分治思想的一行话版本选定枢轴分割数组快速排序本质上是一种分治算法核心逻辑可以归纳成三步在待排序区间里挑一个元素当枢轴pivot标题场景下就是直接取arr[low]把区间内所有比枢轴小的元素挪到它左边所有大于等于它的元素挪到右边这一步称为分区partition对枢轴左右两个子区间递归重复上述过程直到每个区间只剩一个元素。分治思想用生活类比最好懂整理一摞扑克牌时先抽第一张牌当基准把比它小的牌放左边比它大的牌放右边然后分别把左右两堆继续按同样规则整理。快速排序值钱的地方在于所有移动都在原数组上就地完成不需要额外申请一整块和原数组等大的空间。这一点在数据量上来之后差距非常明显。1.2 第一个元素当枢轴的三个理由市面上绝大多数教材讲快排时都会从“第一个元素作为枢轴”入手这确实有它的道理实现门槛最低不需要生成随机数不需要计算中间位置拿arr[low]直接开干少一层出错可能。和经典“挖坑法”天然契合先把arr[low]的值保存到pivot这个位置就变成一个“坑”等右边扫描到的小数填进来随后右边又出现新坑等左边扫描到的大数填进去。整个过程思路清晰手算演算也很直观。便于观察分区本质当枢轴落在两端之一时反而更容易让人理解“为什么分区会让数组局部有序”。但也必须把话挑明第一个元素当枢轴等于把性能命脉交给了输入数据的顺序。如果待排序数组已经升序或降序排列每一轮分区后枢轴都待在端点附近左右两个子区间极度不平衡一个接近 n-1另一个为 0递归树退化成一条长链时间复杂度直接变成 O(n²)。这个问题不是理论恐吓后面第 4 章我会用实测数据给你看它到底有多严重。1.3 常见教学实现路线怎么选围绕“第一个元素作为枢轴”这个题目实际存在几种不同风格的分区写法初学者经常被网上各种版本搞混。我先把主流三种列出来实现流派核心思路特点适合场景挖坑法取出 pivot 后左右指针交替填坑思路直白边界相对好讲清楚教材讲解、入门手写Lomuto 分区单指针 i 维护小于 pivot 的边界j 遍历区间代码极短和快选quickselect衔接自然算法题、模板库Hoare 分区左右双指针互相交换逆序对常数更优但返回值不是 pivot 实际位置容易写错性能敏感场景本文主线选择挖坑法因为“以第一个元素为枢轴”这个命题下挖坑法是最贴合题目语义、也最容易一次性写对的版本。Lomuto 和 Hoare 的代码我会在后面的对比里适当提到但完整流程重点讲挖坑法。2. 挖坑法partition手写实录指针移动顺序一个都不能错2.1 挖坑法的核心循环右找小、左找大、填进去直接看代码这是整个算法的灵魂int partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { // 从右向左找第一个小于 pivot 的元素 while (low high arr[high] pivot) { high--; } // 把它填到左边的坑里high 位置变成新坑 arr[low] arr[high]; // 从左向右找第一个大于 pivot 的元素 while (low high arr[low] pivot) { low; } // 把它填到右边的坑里low 位置又变成新坑 arr[high] arr[low]; } // low high 时这个位置就是 pivot 的最终归属 arr[low] pivot; return low; }我建议你不要死记代码而是理解这个过程先把第一个位置的数抽走此时low就是一个坑右侧指针high向左扫遇到比 pivot 小的数就把它搬到坑里随后左侧指针low向右扫遇到比 pivot 大的数就搬到右侧新坑两侧反复交替直到两个指针碰头把保存在pivot里的值放到碰头位置。每个数最多被搬动一次分区这一步整体是 O(n)。2.2 三个边界条件的具体含义这一段是手写快排最容易翻车的地方我拆开讲外层while (low high)保证左右指针没有交叉一旦碰头就停止扫描。少了这个条件low和high互相越界是板上钉钉的事。右扫描arr[high] pivot这里必须用“大于等于”。含义是只要当前元素不小于 pivot就继续向左挪直到碰到第一个严格小于 pivot 的元素才停。如果你图省事写成那么遇到和 pivot 相等的元素时high会停下来把等于 pivot 的值也当作“小数”填进左边坑里分区逻辑瞬间错乱。左扫描arr[low] pivot同理必须用“小于等于”跳过所有和 pivot 相等的元素只找严格大于 pivot 的大数。内层扫描也要带low high这一点特别容易被忽略。比如整个区间全是大于 pivot 的元素时右扫描如果没有low high保护high会一路降到-1直接访问数组越界内存程序行为立刻变得不可预测。我见过很多人粘了模板代码能跑但一上手自己写就挂挂的位置十有八九就是这三处条件。记住一个口诀右扫停小左扫停大等于全跳过碰头即停手。2.3 等值元素的处理策略加不加等号的分水岭等值元素是快排的经典杀手。一个全为相同数字的数组是检验分区写法是否严谨的试金石。假设数组是[5, 5, 5, 5]如果右扫描条件写成arr[high] pivot那么第一次扫描时arr[3] 5并不大于 5high直接停住然后执行arr[low] arr[high]把这个 5 搬到左边坑紧接着左扫描同样因为arr[low]不是严格大于 5 而立刻停住又把同一个 5 搬回右边。两个指针在同一个位置反复交换永远无法收敛这就是死循环的根源。如果按我上面写的和全相同数组会怎样右扫描一路跳过所有等于 pivot 的元素high最终走到与low相同的位置外层循环退出pivot 原地落位。虽然它在全相同数组下仍然会退化成 O(n²) 的分区次数但至少逻辑是收敛的不会卡死。这个区别在实战中就是“程序崩溃”和“程序能跑但慢”的本质差异。3. 完整C代码与测试验证从能编译到确认排序正确3.1 模块划分与完整代码清单完整实现应该拆成几个功能单一的模块交换函数、分区函数、递归排序函数、验证函数、打印函数。下面是一份可以直接复制到本地编译运行的完整代码#include stdio.h #include stdlib.h #include time.h void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } int partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { while (low high arr[high] pivot) { high--; } arr[low] arr[high]; while (low high arr[low] pivot) { low; } arr[high] arr[low]; } arr[low] pivot; return low; } void quickSort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos 1, high); } } int isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) { return 0; } } return 1; } void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main(void) { srand((unsigned)time(NULL)); int demo[] {6, 1, 8, 3, 5, 9, 2, 7, 4}; int n sizeof(demo) / sizeof(demo[0]); printf(排序前); printArray(demo, n); quickSort(demo, 0, n - 1); printf(排序后); printArray(demo, n); printf(结果验证%s\n, isSorted(demo, n) ? 通过 : 失败); int n2 10000; int *arr2 (int *)malloc(n2 * sizeof(int)); for (int i 0; i n2; i) { arr2[i] rand() % 10000; } clock_t start clock(); quickSort(arr2, 0, n2 - 1); clock_t end clock(); printf(n%d 随机数组耗时%.3f 秒排序结果%s\n, n2, (double)(end - start) / CLOCKS_PER_SEC, isSorted(arr2, n2) ? 通过 : 失败); free(arr2); return 0; }这份代码只依赖标准库没有额外配置任何带 C 编译环境的地方都能直接跑通。3.2 测试用例设计覆盖五类输入很多人写完排序只拿一组随机数测一下就宣告完事这远远不够。我的经验是至少覆盖五类输入输入类型构造方式考察目标随机数组rand() % 范围常规正确性升序数组for (i 0; i n; i) a[i] i;最坏情况退化降序数组for (i 0; i n; i) a[i] n - i;最坏情况退化全相同数组for (i 0; i n; i) a[i] 7;等值元素处理、死循环风险边界小数组空数组、单元素数组、两个元素数组递归终止条件空数组和单元素数组在quickSort里直接走if (low high)这个保护什么都不用做这正好验证了递归出口写的对不对。两个元素的数组则能快速暴露 partition 交换逻辑里“枢轴最终位置偏移一位”这种经典错误。3.3 断言验证与输出结果isSorted函数承担最终裁判角色从第二个元素开始只要发现前一个大于后一个就返回 0。用断言而不是肉眼观察是测试自动化最基本的一步尤其后面数据量上来后肉眼基本没法判断排序是否正确。我在本地跑上面代码时小数组的输出长这样排序前6 1 8 3 5 9 2 7 4 排序后1 2 3 4 5 6 7 8 9 结果验证通过n10000 随机数组那行会显示一个很小的耗时数字同时结果验证为“通过”。这只能证明“随机数据下算法是对的”离“算法在任何输入下都可靠”还差得很远——这正是下一章要实测的内容。4. 实测暴击当输入变得“刁钻”第一个元素枢轴的表现4.1 有序数组与逆序数组的退化实验把数组预先构造成严格升序然后扔给这份代码排序。你会发现一个非常反直觉的现象居然比随机数组慢得多甚至根本跑不完。原因要从递归结构上解释。升序数组里第一个元素是全局最小值分区后 pivot 回到索引 0 的位置右侧剩下 n-1 个元素继续递归下一轮又取这 n-1 个元素里的第一个作为 pivot它又是当前区间的最小值。递归树就此长成一条单链表每一层只减少一个元素总比较次数变成n (n-1) (n-2) ... 1 ≈ n²/2。降序数组同理只不过 pivot 变成每次区间的最大值退化的方式一模一样。我在自己的测试机上试过n50000 的升序数组栈直接爆掉程序段错误退出而 n50000 的随机数组排序耗时在几十毫秒级别肉眼感知不到任何压力。同一份代码换一种输入就是“能用”和“崩溃”的两极。这就是输入敏感性的真实代价。4.2 全相同数组无限递归风险的现场实测全相同数组是另一个高频雷区。如果分区扫描条件里的等号写错程序会陷入死循环即使像我上面那样把等号写对它也并不会因为“所有元素相等所以无需排序”而快速结束。分区结果始终是 pivot 原地落位左侧区间为空右侧区间长度减一递归照样退化成 O(n²)。全相同数组的排序时间同样会从“毫秒”变成“肉眼可见的慢”。但这里有一个很微妙的区别扫描条件写对全相同数组只是慢不会死循环扫描条件写错则是 CPU 占用直接拉满程序永远不会返回。这在调试时是两种截然不同的症状。先确认你写的是和再谈性能优化顺序不能反。4.3 性能数据记录n10000 与 n50000 的对比为了把退化程度量化我做了一组简单对照实验。三个数组都是同样的长度分别填充随机数、升序数、全相同数用同样的clock()计时数据规模随机数组升序数组全相同数组n10000极快通常不到 0.01 秒勉强能跑完但耗时明显上升明显变慢递归深度接近 10000n50000毫秒级完成程序段错误栈溢出程序段错误栈溢出第 1.2 节里说的“最坏情况”在这一组数据里已经完整兑现。升序数组和全相同数组在 n50000 时就因为递归调用层数过深把默认栈空间耗尽。这还不是算法逻辑本身的极限而是 C 运行时栈帧大小给递归实现的硬限制。5. 三个升级方向从入门实现到能抗住压的工程实现5.1 策略一随机化枢轴随机化枢轴几乎是性价比最高的单行优化。思路很简单在区间内随机选一个位置把该位置的元素和arr[low]交换然后继续走挖坑法。这样无论输入是升序、降序还是全相同每次枢轴落位在哪个位置都变成随机事件坏情况的出现概率被压到极低。int randomIndex low rand() % (high - low 1); swap(arr[low], arr[randomIndex]); int pivot arr[low];我测试下来随机化后升序输入不再崩溃排序时间回到“毫秒级”因为每次枢轴平均落在区间中部附近递归深度从 n 降到 log n 级别。代价仅仅是每次分区生成一个随机数几乎可以忽略。需要注意rand() % 区间长度在区间长度特别大时有轻微不均匀性但对快排这种对均匀性要求不高的场景完全够用。5.2 策略二三数取中三数取中比随机化更稳因为它刻意避免最坏情况。取区间左端、右端、中点三个位置的元素把这三者的中位数换到第一个位置当枢轴。这样即使输入是升序或降序枢轴也会落在整个区间的中位数附近递归树天然平衡。经典的三数取中比较交换套路是这样int mid low (high - low) / 2; if (arr[mid] arr[low]) swap(arr[mid], arr[low]); if (arr[high] arr[low]) swap(arr[high], arr[low]); if (arr[high] arr[mid]) swap(arr[high], arr[mid]); swap(arr[mid], arr[low]);三次比较加三次可能的交换把三个数中从小到大排一遍取出中间值。三数取中对近乎有序的数据效果立竿见影而且不需要引入随机数行为可复现调试时比随机化更友好。代价是每次分区多几次比较常数略有上升但换来的是最坏情况被大幅稀释这笔交易非常划算。5.3 策略三小数组插入排序快速排序在区间很小的时候递归和分区调用的开销开始超过排序本身的开销。工程实现里常见的做法是当区间长度小于某个阈值比如 16时不再递归而是直接用插入排序收尾。void quickSort(int arr[], int low, int high) { if (high - low 1 16) { insertionSort(arr, low, high); return; } int pos partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos 1, high); }插入排序在 n 很小的时候虽然也是 O(n²)但常数极小而且对缓存友好实际速度往往不输继续做几层快排递归。这个小优化也是把递归深度再压低一层让栈溢出风险进一步下降。阈值选 16 还是 32取决于机器我习惯用 16效果已经很稳。6. 踩坑复盘从栈溢出到结果错乱我的一份排错索引6.1 症状一递归没有出口导致栈溢出如果你发现程序跑小数组正常跑大数组直接死掉或段错误第一步先检查quickSort的递归调用区间是否真的在变小。一个常见的低级错误是把右半区间写成quickSort(arr, low, pos)而不是quickSort(arr, low, pos - 1)。当pos low时右半区间变成quickSort(arr, low, low)区间没有缩小如果这时low high的判断又恰好成立就会无限递归。排查方法很简单在quickSort开头加一行打印当前low、high、pos跑一个升序小数组。一旦发现某次递归的参数跟上一层完全一样立刻就能锁定问题。6.2 症状二排序结果仍有未排序区间这种问题最隐蔽。以arr [4, 2, 6, 1, 3]为例我手动走一遍正确的挖坑法第一轮 partition 后数组变成[3, 2, 1, 4, 6]返回 3枢轴 4 到达最终位置左区间[3, 2, 1]继续排序右区间[6]只剩一个元素自然有序。如果你发现结果里出现“局部有序但没排全”的现象多半是分区返回的位置不是 pivot 实际落位而是偏移了一个单位导致左右区间的切分点覆盖了正确位置。这时候不要瞎猜把 partition 返回值和每次分区后的数组打印出来和手算结果对照通常一眼就能看出偏移。6.3 症状三性能忽快忽慢如果你觉得代码没问题但性能时好时坏先检查是不是输入数据本身在变化。第一个元素当枢轴的实现性能曲线完全看输入脸色随机数据秒完有序数据卡死全相同数据爆炸。这种“忽快忽慢”不是玄学而是算法输入敏感性的直接体现。解决办法不外乎第 5 章那三招——随机化、三数取中、小数据切插入排序。我个人的偏好是“三数取中 阈值插入排序”的组合既保留了可复现性又把最坏情况的概率压到工程可接受范围。我在实际手写排序算法时的体会是用第一个元素当枢轴做练习最大的价值不是写出一个多快的排序而是把分区、边界、递归、退化这些底层机制彻底暴露在你面前。它让你在踩过坑之后真正理解为什么工业级排序实现里从来看不到这种朴素写法也让你面对“为什么快排不如宣传的那么快”这类问题时能给出有实验支撑的答案而不是背课本结论。这个打法值得每个学排序的人从头走一遍。