快速排序这个话题我其实想聊很久了。不管你是刚接触 C 的初学者还是已经写了几年业务代码的开发者快速排序算法Quick Sort工程里也常称 Qsort基本是绕不过去的一道坎。我最早接触它还是大学算法课当时老师给了十几行递归代码我盯着 partition 函数看了半天也没完全搞懂它到底怎么保证排序正确的。后来在真实项目里处理几十万甚至上千万条业务数据排序时才慢慢意识到当年那些没讲透的细节——分区边界怎么处理、基准值怎么选、递归层数会不会爆炸、重复元素会不会让性能崩掉——才是决定这个算法到底能不能用的关键。这篇文章我不想给你一份标准答案式的教科书讲解而是把它拆开揉碎分区函数怎么写、基准值怎么选、尾递归和显式栈怎么解决爆栈问题、三路划分怎么应对海量重复数据每个环节都给出能直接跑的 C 代码和实测数据参考。这篇文章适合想把快排真正吃透的学生、准备算法面试的求职者以及在工程里被排序性能坑过的开发者。看完你不仅能手写一个工程级快排还能在面试里讲清楚每一个设计背后的 Why。1. 快速排序的整体设计与思路拆解1.1 快速排序到底在解决什么问题排序是几乎所有程序里出现频率最高的基础操作之一。日志按时间排序、排行榜按分数排序、数据库索引要排序、订单列表要排序。面对一堆无序数据我们最朴素的想法是冒泡排序挨个比较、交换把大的往右推。这个算法好理解但数据量一旦过万冒泡的平方级复杂度就会让程序卡得让人抓狂。快速排序的价值在于它能在绝大多数实际场景里做到 O(n log n) 的平均时间复杂度而且是原地排序不需要像归并排序那样额外开辟一个等长数组。这意味着它既快又省内存。再加上它对 CPU 缓存比较友好访问模式比较连续所以在通用排序这个赛道上快排往往是默认选择。我用一个生活中的例子来帮你建立直觉想象你手头有几十份试卷需要按照分数从低到高整理。你随手抽出一份试卷作为“标准”比如 78 分。然后你把所有低于 78 分的试卷放到左边高于 78 分的放到右边。这一轮下来那份 78 分的试卷的最终位置就确定了——左边都比它低右边都比它高。接下来你只要对左边那一堆和右边那一堆分别重复同样的操作就行。这个“抽取标准、划清左右、递归处理”的过程就是快速排序的全部秘密。1.2 为什么是快速排序而不是冒泡或归并很多人第一反应是冒泡排序也能排序啊代码还更简单。没错但冒泡排序每一轮只能把最大值“冒”到末尾每一轮比较几乎都是全量扫描整体复杂度稳定在 O(n²)。数据量一上 10 万冒泡和快排的时间差距就是几分钟和几毫秒的差别。归并排序复杂度稳定在 O(n log n)而且稳定排序但它的致命伤是需要额外的 O(n) 空间。对于海量数据来说这可能直接把内存吃满。快速排序的平均性能与归并同级但空间只要 O(log n) 的递归栈是真正的原地排序。下面这张表我做了个直观对比方便你理解各个排序算法的定位排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定特点冒泡排序O(n²)O(n²)O(1)是实现简单适合教学与小数据归并排序O(n log n)O(n log n)O(n)是稳定但吃内存堆排序O(n log n)O(n log n)O(1)否最坏也好但常数较大快速排序O(n log n)O(n²)O(log n)否平均最快原地排序可见快速排序的最大卖点就是在不需要稳定性的通用场景下它通常是最快的通用比较排序。这也是为什么 C 标准库的 qsort 和 C 标准库 sort 的基础内核都基于快速排序的思想。1.3 快速排序的核心思想分而治之快速排序的思路可以拆成三步选基准pivot从待排序区间里挑一个元素作为“分割线”。分区partition把小于基准的元素移到左边、大于基准的移到右边。这一步做完基准元素就落在了它最终该待的位置上。递归排序对基准左侧和右侧的子区间分别重复以上步骤直到子区间长度为 0 或 1。这个递归终止条件很重要当区间只有一个元素或者为空的时候天然有序不需要再处理。这也是很多人写快排时最容易忽略的地方——递归边界处理不好轻则死循环重则栈溢出。“分而治之”的精髓在于每一次分区操作都能确定至少一个元素的最终位置。如果每次分区都比较均匀问题规模就会指数级缩小最终总代价是 O(n log n)。如果每次分区都很不均匀比如每次只把基准放到位、剩下的都在一侧那问题规模每次只减一复杂度就退化成 O(n²)。2. 核心细节解析与实操要点2.1 分区函数快排的灵魂所在分区函数是快速排序的心脏。不同写法的分区函数直接决定了算法的效率、边界条件复杂度和出错概率。我见过最多的是 Lomuto 分区。它的思路是选定最后一个元素作为基准用一个慢指针 i 维护“小于基准的区域”的末尾遍历整个数组遇到小于基准的元素就把 i 往后移动并交换。代码非常简洁适合入门教学。// Lomuto 分区返回基准最终下标 int lomutoPartition(int arr[], int low, int high) { int pivot arr[high]; // 固定取最后一个元素 int i low - 1; // i 指向小于基准区域的最后一个位置 for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); // 把基准放回正确位置 return i 1; }Lomuto 分区的好处是边界条件简单for 循环里j high不会越界最后 swap 一步到位。但它有一个明显的缺点交换次数相对较多在大量数据场景下常数较大。我更推荐在实际工程中使用 Hoare 分区。这个版本由快排发明者托尼·霍尔提出思路是用两个指针分别从左右两端向中间逼近。左指针向右找比基准大的元素右指针向左找比基准小的元素找到后交换两者。两个指针相遇时分区完成。// Hoare 分区依赖外部递归处理左右两侧 int hoarePartition(int arr[], int low, int high) { int pivot arr[low (high - low) / 2]; // 取中间元素为基准避免有序数组退化 int i low - 1; int j high 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } }Hoare 分区的优点是交换次数少而且最终返回的 j 并不是基准的最终位置而是左右子区间的分割点。这意味着递归调用时要小心处理边界通常递归的是[low, j]和[j 1, high]。我一开始写这个版本时总是忘记返回的是分割点而不是基准下标导致排序结果错乱。后来养成了一个习惯Hoare 分区配合递归时一定在纸上走一遍小数组把指针移动和交换轨迹画出来。2.2 基准值选取的三个层次基准值选得好不好对性能影响极大。最糟糕的情况是数据已经有序或近乎有序而我们又固定选择第一个或最后一个元素作为基准。这种情况下每次分区只能确定一个元素的最终位置剩下的元素全部在基准的一侧递归深度直接变成 n时间复杂度退化成 O(n²)。怎么破基准选取有三个层次层次一随机选择。在[low, high]里随机选一个下标作为基准然后和区间末尾或开头元素交换再走标准的单边分区。随机化从概率上消除了“最坏输入被构造”的风险因为攻击者无法预知你这次选的基准是谁。代价是每次要生成一次随机数时间复杂度增加一个很小的常数。// 随机选基准并交换到区间末尾配合 Lomuto 使用 int randomIndex low rand() % (high - low 1); std::swap(arr[randomIndex], arr[high]);层次二三数取中。取区间第一个元素、中间元素、最后一个元素比较它们的大小把中间值作为基准。这种方法在工程中比随机化更常用因为它不需要调用随机数生成器只需要三次比较和两次交换同时能有效避免有序数组导致的退化。我自己实测下来对于几乎有序的大数组三数取中能让快排从“灾难级”的 O(n²) 回到 O(n log n) 的正常水平。int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) std::swap(arr[mid], arr[low]); if (arr[high] arr[low]) std::swap(arr[high], arr[low]); if (arr[high] arr[mid]) std::swap(arr[high], arr[mid]); return arr[mid]; }层次三小数组切换插入排序。递归到小区间时快排的优势会被函数调用开销和分区开销抵消。业界惯例是当区间长度小于 16 或 24 时直接用插入排序收尾。C 标准库里的std::sort就是这么干的。这个优化效果非常显著因为插入排序在小数组上常数极小而且对近乎有序的数据格外友好。2.3 递归的代价与非递归实现快排天然用递归写起来最顺但递归不是免费的。每一次递归调用都会在调用栈上压入一个栈帧栈帧里保存着局部变量、参数和返回地址。当数据规模达到几十万甚至上百万时如果分区极端不平衡递归深度可能等于数组长度 n直接导致调用栈溢出。处理这个问题的常用手段有两个。第一是限制递归方向每次分区后比较左右两个子区间的长度只对较短的子区间递归调用较长的子区间用循环继续处理。这样能保证递归深度被限制在 O(log n) 级别。这其实就是尾递归优化的手动版本。第二种更彻底的方案是用显式栈模拟递归自己维护一个栈把待排序的区间压入栈中循环弹出、分区、再压入子区间。// 非递归快排用显式栈模拟系统调用栈 void quickSortIterative(int arr[], int n) { if (n 1) return; int* stack new int[n]; int top -1; stack[top] 0; stack[top] n - 1; while (top 0) { int high stack[top--]; int low stack[top--]; if (low high) continue; int p hoarePartition(arr, low, high); // 先压入较短的区间控制栈的最大深度 if (p - low high - p - 1) { stack[top] low; stack[top] p; stack[top] p 1; stack[top] high; } else { stack[top] p 1; stack[top] high; stack[top] low; stack[top] p; } } delete[] stack; }有人可能会问既然显式栈这么麻烦直接用递归不就行了我的经验是数据量在万级以下递归完全没问题数据量到百万级且担心极端输入非递归或限制递归方向是更稳的选择。面试时如果能主动写出“限制递归深度”的版本绝对是个加分项。3. 实操过程与核心环节实现3.1 从零手写一个工程级快排把前面几节提到的优化点组合起来我给出一个我平时项目里会用的完整实现。它包含三数取中选基准、Hoare 分区、小数组切换插入排序、以及对外统一的简洁接口。#include iostream #include vector #include chrono #include algorithm 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; } } int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) std::swap(arr[mid], arr[low]); if (arr[high] arr[low]) std::swap(arr[high], arr[low]); if (arr[high] arr[mid]) std::swap(arr[high], arr[mid]); std::swap(arr[mid], arr[high]); // 把基准移到末尾 return arr[high]; } int hoarePartition(int arr[], int low, int high) { int pivot medianOfThree(arr, low, high); int i low - 1; int j high 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } } void quickSortInternal(int arr[], int low, int high) { while (low high) { if (high - low 16) { insertionSort(arr, low, high); return; } int p hoarePartition(arr, low, high); // 递归处理较短的子区间循环处理较长的区间 if (p - low high - p - 1) { quickSortInternal(arr, low, p); low p 1; } else { quickSortInternal(arr, p 1, high); high p; } } } void quickSort(int arr[], int n) { quickSortInternal(arr, 0, n - 1); }这里有几个细节值得说清楚medianOfThree最后把基准交换到 high 位置是为了配合 Hoare 分区的写法。Hoare 分区在 pivot 被交换到数组内部任何位置时都能工作但统一放到末尾更可预期。quickSortInternal里的while (low high)实现了“只递归短区间、循环处理长区间”这个写法非常经典。它把最坏递归深度压缩到 O(log n)。小数组阈值 16 是我试过比较舒服的值。不同机器上 8 到 24 之间差异都不大你可以自己调。下面用随机数据做一个简单测试看看它到底跑得多快int main() { const int N 1000000; std::vectorint data(N); srand(2025); for (int i 0; i N; i) data[i] rand() % 1000000; auto copy1 data; auto start std::chrono::high_resolution_clock::now(); quickSort(copy1.data(), N); auto end std::chrono::high_resolution_clock::now(); std::chrono::durationdouble, std::milli elapsed end - start; std::cout QuickSort 100万随机数耗时: elapsed.count() ms\n; // 验证排序是否正确 auto copy2 data; std::sort(copy2.begin(), copy2.end()); std::cout 排序结果正确: (copy1 copy2 ? Yes : No) std::endl; return 0; }我在自己机器上跑出来的结果大概是100 万随机整数约 70 到 90 毫秒。不同 CPU 和编译器会有差异但量级不会差太多。这个性能对于通用排序来说是相当能打的。3.2 三路划分让海量重复元素不再卡死普通快排在元素大量重复的场景下有一个隐藏的性能杀手。因为标准的单路分区把等于基准的元素都算作“大于”或“小于”一侧当重复元素特别多时分区结果可能严重失衡递归退化到 O(n²)。解决思路是把这个“等于基准”的区域单独切出来这就是三路划分3-way partition也叫荷兰国旗问题的解法。三路划分维护三个指针lt表示小于基准区域的右边界gt表示大于基准区域的左边界i是当前扫描指针。遍历过程中arr[i] pivot交换arr[lt]和arr[i]然后lt、iarr[i] pivot交换arr[gt]和arr[i]然后gt--但i不动因为换过来的新元素还没比较过arr[i] pivot直接i。// 三路划分快速排序一次性处理等于基准的所有元素 void quickSort3Way(int arr[], int low, int high) { if (high low) return; int lt low, i low 1, gt high; int pivot arr[low]; // 这里用第一个元素做基准三路划分对基准选取不那么敏感 while (i gt) { if (arr[i] pivot) { std::swap(arr[lt], arr[i]); } else if (arr[i] pivot) { std::swap(arr[i], arr[gt--]); } else { i; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }我对比测试过当数组里有大量重复元素比如只有 0 和 1 两种值的二值数组时普通快排需要几百毫秒甚至上秒级而三路划分几乎在 10 毫秒以内完成。这个版本在面试中聊到“如何优化重复元素场景”时可以直接甩出来。3.3 复杂度的推导不靠死记硬背很多人面试时把快排复杂度背得很熟但一问为什么就卡壳。这里我给你一个能当场推导出来的思路。假设每次分区后基准把区间分成大小接近的两半。那么规模为 n 的问题被拆成两个规模约为 n/2 的子问题再加上一次分区需要 O(n) 次比较可以写出递推式T(n) 2T(n/2) O(n)用主定理或者递归树展开都能得到 T(n) O(n log n)。直观理解递归树有 log n 层因为每次规模减半每一层总的比较次数是 O(n)因此总代价是 O(n log n)。最坏情况是基准每次都非常“不走运”区间被分成 1 和 n-1 两半递推式变成T(n) T(n-1) O(n)展开后就是 O(n²)跟冒泡排序一个级别。这就是为什么不处理基准选取问题快排在工程上不可用。空间复杂度上递归版的快排需要调用栈。理想情况下每次递归深度是 O(log n)所以空间复杂度是 O(log n)。最坏退化到 O(n)这就是为什么前面要强调控制递归深度。平均时间复杂度的严格论证涉及数学期望但你只需要抓住直觉随机选择基准时任何固定数据被分成“极端不均”的概率很低而“比较均衡”的概率很高最终期望复杂度是 O(n log n)。3.4 qsort 与 C sort 的工程选择在 C 语言时代我们用的是标准库的qsort函数。它的原型是void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));这个设计比较古老需要传函数指针而且函数指针间接调用会有一定开销。compar回调的参数是const void*写起来也比较痛苦。但在纯 C 项目里它是唯一选择。C 里我强烈建议直接用std::sort。它基于内省排序以快速排序为主体递归深度超过阈值时切换到堆排序兜底区间小于一定长度时切换到插入排序。这种混合策略能同时解决快排的最坏退化和递归过深问题。在性能上std::sort通常比手写快排还快因为它能利用编译器的内联优化而且泛型模板针对不同类型有更好的特化。#include algorithm #include vector std::sort(data.begin(), data.end());排序完之后如果需要快速查找配合std::binary_search、std::lower_bound等二分查找函数就是经典的有序数组查询组合。这也是为什么面试时快排和二分查找经常成对出现——它们天然是一条技术链路。4. 常见问题与排查技巧实录4.1 排序结果不对分区边界是罪魁祸首我见过太多人写快排时死循环或者结果错乱几乎都能归结为分区边界问题。最常见的两个坑坑一递归时把基准又带进去了。Lomuto 分区返回的是基准最终下标 p基准左侧是[low, p-1]右侧是[p1, high]。有人图省事写成了[low, p]和[p, high]结果基准元素被反复参与排序虽然最终也可能正确但很可能出现死递归或者无限循环因为某个子区间的大小根本没有减小。坑二Hoare 分区返回值是分割点 j不是基准下标。我第一次用 Hoare 分区时递归写的是quickSort(arr, low, p-1)和quickSort(arr, p1, high)结果排序完发现有一小块始终是乱的。后来仔细走了一遍才意识到Hoare 分区返回的 j 是右半区间的起点它并不保证 arr[j] 就是基准的最终位置。正确写法是递归[low, p]和[p1, high]。如果你发现自己排序结果总是差一两个元素别怀疑算法思想先用长度 4 或 5 的小数组把每次分区后的中间状态打印出来一眼就能看到问题。4.2 数据一多就栈溢出要么换基准要么上非递归在面试或者做算法题时可能会遇到“数据量极大且已经有序”的测试用例。如果你的基准固定取第一个或者最后一个快排就会退化成 O(n²)而且递归深度等于 n。我实测过10 万级有序数据可能就会把系统栈干爆程序直接崩溃。解决办法优先级从低到高是加三数取中或随机选基准从根源上避免有序数组退化。限制递归方向只递归短区间长区间循环处理把递归深度压到 O(log n)。彻底改成显式栈模拟的非递归写法。我个人建议至少做到第 2 步因为它代码改动量小收益却很大。第 3 步更适合作为面试加分项展示你的底层理解。4.3 快排为什么会慢数据分布的秘密有时候快排不会崩溃但就是慢得离谱。这时候你要怀疑两件事数据是不是接近有序重复元素是不是特别多因为快排性能对输入分布极端敏感。接近有序的数据配合固定基准每次分区几乎都是“一个元素归位其余原封不动”复杂度稳定在 O(n²)。这种情况下调试一两百个数据感觉不出来但百万级数据会让你怀疑人生。重复元素过多则是因为等于基准的元素被重复比较和交换白白浪费大量操作。如果你还会从汇编或者内存层面看问题会发现快排慢还有一个隐藏原因随机访问模式导致缓存未命中率升高。相比之下归并排序虽然空间吃不消但它的连续访问模式在缓存层面其实更友好。这就是为什么工程上的std::sort要做混合策略而不仅仅是快排一条路走到黑。4.4 常见问题速查表我把平时大家问得最多的问题整理成一张速查表方便你排查症状可能原因解决办法排序结果是乱的分区边界处理错误基准被重复递归回到 4.1打印小数组中间状态程序栈溢出崩溃基准选取固定数据有序导致递归深度 O(n)三数取中 / 随机基准 / 限制递归深度数据量大时极慢重复元素过多使用三路划分结果少一个元素Hoare 分区递归区间写错递归[low, p]和[p1, high]大量数据排序很慢但没用栈小数组仍走快排递归区间小于 16 时切换插入排序C 编译报错找不到 sort/qsort没包含头文件或命名空间问题#include algorithm、#include cstdlib另外提醒一个 C 新手常犯的错如果你直接写qsort(..., compare)但 compare 函数没有按 C 约定导出也就是没加extern C或没写对函数签名在某些编译器上会报奇怪的编译错误。这个在工程里很坑建议 C 程序里别用qsort直接用std::sort。4.5 面试中如何展示你真正理解快排快排是算法面试的高频考点但大部分候选人只会默写 Lomuto 分区版本。如果你想在面试官面前展示深度我建议按下面这个顺序表达先说思想。用分治三句话概括选基准、分区、递归处理左右。然后主动提一句“这个算法最怕的是基准选取不当导致递归深度退化到 O(n)所以工程实现里我会用三数取中或随机化”。再写代码。我一般先写一个干净的 Lomuto 版本作为交流基础然后补充一个 Hoare 版本并说明两者的差异Hoare 交换次数更少、常数更小但边界处理更微妙。最后讲优化。提到三路划分应对重复数据、插入排序收尾小数组、限制递归深度避免爆栈。这三板斧一亮出来面试官基本就知道你是真写过而不是背题。还有一个经常被追问的点快排是稳定的吗答案是否定的。至于为什么因为分区过程中相等的元素相对顺序可能被打乱。如果你追问“那怎么改成稳定快排”那就要牺牲原地性用额外数组来做稳定分区工程上不划算所以在需要稳定排序的场景直接选归并。最后再分享一个小技巧我自己在写快排时最常踩的一个坑就是分区函数写完、测试了几组随机数据全过就以为万事大吉了。后来有一次在线上系统里处理极端分布数据时突然崩了排查半天才发现是基准选取得太粗糙。从那以后我给自己定了一个规矩任何排序算法写完必须额外测试三组数据——完全有序的、完全逆序的、全部元素相等的。这三组数据能把排序算法的绝大多数边界情况都提前暴露出来。如果你现在正在刷题或者准备面试我建议你把 Lomuto 版本、Hoare 版本、三路划分版本、非递归版本这四种写法都手写过一遍。每一种写法踩过的坑都会变成你回答追问时的底气。快排这东西看着简单真正到了工程环境里基准选择、递归深度、重复元素、小数组优化每一步都有讲究。把这些细节吃透了你就不只是在“用算法”而是真的在“理解算法”了。
