C语言快速排序从原理到工程级优化：基准选择、递归与非递归实现全解析

上个月有个学弟拿他写的快排来问我，说照着教科书敲的代码，数据一有序就直接超时，他甚至怀疑这算法是不是被吹出来的。我一看代码就明白了——选基准值直接取了第一个元素，这问题太典型了。其实快速排序本身的正确率非常高，但要说把它写好、写稳、能应对各种输入场景，里面门道真不少，这也是为什么每个学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……个元素，总代价就是 1+2+3+...+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 优化）。结果如下表：

注意，这个数据在不同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] > pivot，arr[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 到怀疑人生之后，我总结了一套固定的测试流程，推荐给所有人：

1. 最小用例检测：分别用空数组、单元素、双元素、逆序数组、全部相同数组做测试，这是快排正确性的“九宫格”。
2. partition 单测：把 partition 拆出来单独执行，打印返回值、交换后的数组。
3. 黄金参照对比：用 C 标准库自带的qsort作为对照，生成随机数组，排序后memcmp对比结果。
4. 规模递增压力测试：从 1000 个元素一路加到 10 万、100 万、1000 万，观察是否崩溃，以及耗时增长趋势是否符合 O(n log n)。

这四步走完，快排的绝大部分隐藏问题都会浮出水面。特别是第四步，它会暴露你有没有“有序数组退化”之类的问题——很多代码在小规模上能过，一跑 100 万的有序数组就原形毕露，这可不是靠运行十几次碰运气能测出来的。

我自己现在写排序代码，默认模板就是“三数取中 + 三路快排 + 小数组插入排序”这套组合。遇到面试先写最经典的挖坑法，然后主动讲出：这个版本有哪些缺陷、如果数据重复太多会怎样退化、如果栈空间受限怎么办——把每个变式对应的动机说出来，比甩出一大段代码更能体现功底。最后分享一个小技巧：把 partition 单独抽出来做单元测试，先测 partition 再测整体快排，一样能把调试时间砍掉一半以上。排序这个问题琢磨深了，很多面向计算机的本质困局，都会跟着豁然开朗。