1. 快速排序为什么几乎所有排序场景都有它的身影如果你刷过面试题、写过业务代码里的排序需求或者研究过标准库的排序源码大概率绕不开这个名字快速排序。它由 Tony Hoare 在 1960 年提出六十多年过去依然是使用最广泛的排序算法之一。C 语言qsort、JavaArrays.sort的原生类型排序、Cstd::sort的混合策略底层都能看到快排的影子。快速排序能解决什么问题一句话在绝大多数场景下用最少的时间把无序数据变成有序序列。它的平均时间复杂度是 O(n log n)虽然理论上最坏会退化到 O(n²)但通过随机化选取基准、三数取中、三路切分等工程优化实际使用中几乎不会触碰最坏情况。相比冒泡排序的 O(n²)、选择排序的 O(n²)快排在大数据量下的优势是碾压性的。这段实现也非常适合学习“分治 递归 双指针 原地交换”这几组经典技巧的组合运用。这篇文章适合谁看第一类是想彻底搞懂快排原理的初学者我会从分治思想开始讲把基准选择、分区过程、递归终止条件拆开揉碎第二类是要应付笔试面试的求职者后面专门有一章整理高频考点和手写模板第三类是写工程代码的开发者想了解为什么标准库排序不是单纯用快排而是混合了插入排序、堆排序。我尽量用实际项目里踩过的坑来说明问题而不是照着教科书复述定义。先给一个整体的认知框架快排一共分两步分和排。“分”是选定一个元素作为基准把数组切成左右两半左半全部小于等于基准右半全部大于等于基准“排”是对左右两半分别递归执行同样的切分直到每个子区间只剩一个元素或为空。核心难点不在递归而在那个“切分”过程——也就是 partition 函数怎么写才既高效又不容易出错。2. 分治思路与 partition 的核心拆解2.1 用一句人话理解快排策略想象一下学校食堂窗口排队你作为管理员想让学生按身高从低到高站好。一种做法是随便拉一个人出来比如小明然后让所有比他矮的站到他左边所有比他高的站到他右边。此时小明的位置就正确了因为他左边的人都比他矮右边的人都比他高。接下来你只需要对左边那堆人、右边那堆人分别重复这件事直到每堆只剩一个人队伍就自然排好了。这就是典型的“分治”思想把大问题拆成规模更小、结构相同的子问题分别解决后再合并。快排的巧妙之处在于它不需要额外的合并步骤——因为每次 partition 之后基准元素已经落在它最终该在的位置。递归处理完左右两侧整个数组就全局有序了。对比归并排序归并的难点在于“合”快排的难点则在“分”。从更数学一点的视角看快排每次 partition 都在解决“找到基准元素的最终索引”这样一个子问题。假设数组长度为 n我们选择一个元素 x 作为基准做一次扫描后所有小于 x 的都在左边所有大于 x 的都在右边于是 x 的位置就是最终有序数组中的位置。这个过程把长度为 n 的问题变成了两个长度大约为 n/2 的子问题。2.2 partition 的两种主流实现风格在工程实践里partition 写法的选择至关重要不同写法不仅影响代码美观度也直接影响性能和对重复元素的处理能力。最常见的两种风格是Lomuto 分区和Hoare 分区。Lomuto 分区的逻辑非常直观选择最后一个元素作为基准用两个指针 i 和 j 从头扫描j 负责遍历数组遇到小于基准的元素就把 i 前移一位并交换 i 和 j 的位置等 j 遍历完整个数组后把基准元素与 i1 位置的元素交换。这样左边全部小于基准右边全部大于基准。int lomuto_partition(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; }Hoare 分区则是从数组两端向中间扫描左指针找到大于基准的元素停下右指针找到小于基准的元素停下然后交换两者直到两指针相遇。它比 Lomuto 的交换次数更少效率也更高但代码的边界条件更隐蔽。int hoare_partition(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]); } }我自己更推荐初学者先掌握 Lomuto因为它边界清晰、逻辑容易验证做工程优化或追求极致性能时改用 Hoare。两种风格在递归代码里的返回值和边界处理有微妙差别后面专门用一节讲这个问题。2.3 基准选择的三种常见方案基准选得好不好几乎是快排性能的分水岭。如果每次都能选中数据的中位数递归树是平衡的时间复杂度稳定在 O(n log n)如果每次选中最大值或最小值递归树退化成链表时间复杂度变成 O(n²)。第一种是固定选第一个或最后一个元素。最简单但弱点也最明显如果待排序数组已经有序或接近有序这种选法必然触发最坏情况。面试时如果只写“固定选最后一个”的版本很容易给自己埋雷。第二种是随机选基准。每次在执行 partition 之前随机生成一个 [low, high] 范围内的下标把该位置的元素与 low 位置交换再按固定位置策略分区。这种方式从概率上保证了最坏情况几乎不可能出现是算法竞赛和工程中常见的兜底方案。int random_index low rand() % (high - low 1); swap(arr[low], arr[random_index]); // 然后使用 arr[low] 作为基准第三种是三数取中。取 low、mid、high 三个位置的值选出中间大小的那个作为基准并与 low 交换。这样既能规避有序数组的极端情况又能比纯随机方案获得更稳定的划分。Cstd::sort在深度退化之前也采用类似思想配合堆排序作为堡垒形成内省排序。三种方案实测下来随机化最省心三数取中在接近有序的数据上表现更好。如果是嵌入式或实时系统随机数生成有额外开销三数取中是更可控的选择。3. 从伪代码到可用代码一段能直接跑的 C 语言快排3.1 递归版完整实现先给出一个完整可运行的 C 语言版本采用随机选取基准 Lomuto 分区。这段代码可以直接用于自己的项目或者作为面试手写题的起点#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 random_index low rand() % (high - low 1); swap(arr[random_index], arr[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 quick_sort(int arr[], int low, int high) { if (low high) { int pivot_index partition(arr, low, high); quick_sort(arr, low, pivot_index - 1); quick_sort(arr, pivot_index 1, high); } } int main() { srand(time(NULL)); int arr[] {5, 2, 9, 1, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); quick_sort(arr, 0, n - 1); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }这段代码的关键点有三个第一random_index必须在每次分区时重新生成不能放在外层第二循环条件用的是j high不要写成避免重复交换基准元素自身第三递归退出条件是low high实际上当区间里只剩一个元素时low high继续递归没有意义。3.2 边界条件到底为什么这么写很多初学者会在 partition 的返回值和递归调用范围上犯迷糊。我逐个解释。Lomuto 分区返回的是基准元素最终所在的索引记为 p。因为基准左边的元素都小于等于基准右边的都大于等于基准所以递归左侧是[low, p-1]右侧是[p1, high]基准本身不需要参与后续排序。注意不是[low, p]否则基准元素会反复出现在子问题里虽然排序结果仍然正确但会产生大量无效比较性能严重下降。Hoare 分区则不同它返回的是右半区间的起始边界 j不是基准的最终位置。递归调用是quick_sort(arr, low, j)和quick_sort(arr, j1, high)。如果照抄 Lomuto 的递归范围去配 Hoare 的 partition必然出现死循环或数组越界。我建议初学者认准一套组合Lomuto 配 p-1/p1Hoare 配 j/j1不要混用。再看 partition 循环里的边界。Lomuto 以high为基准位置循环扫描[low, high-1]最后一步把基准换到i1的位置。这里隐含一个前提数组至少有两个元素。如果low high外层递归早已结束partition 根本不会被调用。所以在递归函数里用if (low high)做保护是最稳妥的写法。3.3 Java 版本的模板Java 写快排的思路上没有区别只是数组是引用类型swap 操作直接作用在原数组上不需要返回新数组。这里给一个泛型友好的模板适合面试时快速手写public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low high) { int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } } private static int partition(int[] arr, int low, int high) { int randomIndex low (int)(Math.random() * (high - low 1)); swap(arr, randomIndex, high); int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这个模板有几个细节值得注意Math.random()生成的是 [0.0, 1.0) 的浮点数乘上区间长度再加 low可以保证下标不越界循环条件里的arr[j] pivot用的是小于等于这个“等于”非常重要。如果只写大量重复元素会被分到右侧导致递归树严重失衡。4. 复杂度分析为什么平均 O(n log n)最坏却是 O(n²)4.1 递归树视角看复杂度要理解快排的时间复杂度最直观的办法是从递归树入手。假设每次 partition 都能把数组近似分成两半那么第一层递归处理 n 个元素第二层两个子问题各处理 n/2 个元素第三层四个子问题各处理 n/4 个元素。每一层的总工作量都是 O(n)一共有 log n 层所以总复杂度是 O(n log n)。这个“每层 O(n)”是怎么来的关键是 partition 函数每调用一次就要扫描当前区间内的全部元素比较并交换一次。不管数组中元素怎么分布扫描一个长度为 k 的区间需要 O(k) 时间。把每一层的所有区间长度加起来就是 n。最坏情况发生在每次 partition 都选到最大或最小元素当基准。此时一个长度为 n 的问题被分成一个长度为 n-1 的问题和一个长度为 0 的问题递归树变成一条直线第一层 O(n)第二层 O(n-1)第三层 O(n-2)总和是 O(n²)。4.2 空间复杂度和递归栈的取舍快排是原地排序算法它不需要额外数组来存放中间结果空间复杂度理论上只需要 O(log n) 的递归调用栈空间。但这个 O(log n) 是平均情况最坏情况下递归深度达 O(n)栈空间也会变成 O(n)。在实际工程里这个空间开销值得严肃对待。我有一个嵌入式项目单片机的栈空间只有几十 KB数组规模到几千个元素时裸写递归版快排直接爆栈。后来改成非递归版用显式的栈结构模拟递归调用这个问题就解决了。后面专门有一节讲迭代版实现。另外快排是不稳定排序。所谓“稳定”是指值相等的元素在排序后的相对顺序和排序前一致。快排由于分区时会跨越交换元素无法保证相对顺序所以如果你需要对对象数组按多个字段排序且要求保持字典序结构先考虑稳定的归并排序否则可以直接快排。4.3 与归并排序、堆排序的核心差异这三者都是 O(n log n) 级别的排序算法但在工程中各有优劣。我列一个实际选型对照表算法平均时间最坏时间空间稳定性优势场景快速排序O(n log n)O(n²)O(log n)不稳定通用排序、内存充足、随机访问型数组归并排序O(n log n)O(n log n)O(n)稳定链表排序、大数据外排序、稳定性要求高堆排序O(n log n)O(n log n)O(1)不稳定内存极受限、不需要稳定性、Top-K 问题如果看 Java 的Arrays.sort源码你会发现基本类型数组用的是快排对象类型数组用的是归并或 TimSort。因为基本类型的“相等”没有相对顺序概念不需要稳定快排更快对象类型排序往往希望保持原有顺序所以选择稳定排序。Cstd::sort用的是内省排序第一层是快排检测到递归深度超过阈值时切换堆排序小规模区间切换插入排序这也是前面提到的“混合策略”。5. 工程级快排优化手段与实战变体5.1 小数组切换到插入排序快排的递归开销在数据量很小时反而比简单排序更费。原因在于递归调用、函数栈帧、随机数生成都有固定成本当子区间长度小于某个阈值时这些固定成本摊派到每个元素上就不划算了。实际测试中区间长度小于 10~16 时插入排序通常比继续递归快排更快。行业内普遍的做法是在快排内部加一个阈值判断void quick_sort_optimized(int arr[], int low, int high) { if (high - low 1 THRESHOLD) { insertion_sort(arr, low, high); return; } if (low high) { int pivot_index partition(arr, low, high); quick_sort_optimized(arr, low, pivot_index - 1); quick_sort_optimized(arr, pivot_index 1, high); } }这个阈值不是拍脑袋定的而是和缓存命中率、递归栈深度有关。不同的 CPU 架构上最优阈值略有浮动我一般从 8 开始测逐步调大看耗时曲线。注意这里的插入排序是给子区间排序不是对整个数组排序排序完成后这些小区间也都是整体有序的一部分。5.2 三路快排处理大量重复元素如果数组中大量元素的值相同比如性别字段、状态码、布尔值普通快排会非常低效。因为默认的 partition 把所有等于基准的元素只分到某一侧导致递归树严重偏斜。处理这个问题的方法是三路切分将数组分成小于基准、等于基准、大于基准三个部分递归时只需要排序小于和大于两侧等于基准的区间直接跳过。三路快排的实现思路是维护三个指针lt、i、gt。lt 指向小于区间的末尾gt 指向大于区间的开头i 从 low 向 high 扫描。遇到小于基准的元素就与 lt 位置交换并把 lt 和 i 都右移遇到大于基准的元素就与 gt 位置交换并把 gt 左移遇到等于基准的元素直接把 i 右移。void quick_sort_3way(int arr[], int low, int high) { if (low high) return; int lt low; int i low 1; int gt high; int pivot arr[low]; while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); lt; i; } else if (arr[i] pivot) { swap(arr[gt], arr[i]); gt--; } else { i; } } quick_sort_3way(arr, low, lt - 1); quick_sort_3way(arr, gt 1, high); }三路快排特别适合大规模统计类数据。我之前处理过一批几百万用户的年龄数据大量年龄集中在中位数附近普通快排跑了将近一秒钟三路快排直接缩短到一百毫秒左右效果非常明显。5.3 迭代版快排避开递归栈工程中遇到极端数据分布时即使加了随机化递归深度依然可能超过系统栈限制。迭代版用显式的栈保存待处理区间彻底摆脱系统递归栈的深度限制。空间复杂度依然接近 O(log n)但栈是分配在堆上的可以动态扩展。void quick_sort_iterative(int arr[], int low, int high) { int stack[1024]; int top -1; stack[top] low; stack[top] high; while (top 0) { high stack[top--]; low stack[top--]; int pivot_index partition(arr, low, high); if (low pivot_index - 1) { stack[top] low; stack[top] pivot_index - 1; } if (pivot_index 1 high) { stack[top] pivot_index 1; stack[top] high; } } }注意这里的栈数组大小需要根据数据量评估。最坏情况下栈可能存储全部区间需要 O(n) 的空间如果排序前无法估算数据量建议用链表实现的动态栈。迭代版的另一个优势是便于并行化多个区间可以分配给不同线程处理互不干扰。5.4 双轴快排Java 标准库的方案Java 的Arrays.sort在 JDK 7 之后对基本类型用的是双轴快排。核心思想是选两个基准元素 pivot1 和 pivot2把数组分成三部分小于 pivot1、介于 pivot1 与 pivot2 之间、大于 pivot2。一次 partition 可以比单轴版本多切出一个子区间实测在绝大多数分布下性能优于单轴快排。双轴快排不是考试必须掌握的内容但理解它对读标准库源码有帮助。它的实现细节非常讲究先对两个基准排序保证 pivot1 pivot2然后扫描数组并把元素归入三段区间。由于逻辑复杂度高工程中很少有人从头手写基本都是直接调用库函数。如果面试被问到“Java 的排序为什么快”能说出双轴快排 插入排序降级 TimSort 这套组合就已经超过大多数候选人了。6. 笔试面试中的高频考法与手写技巧6.1 手写快排的几种不同问法面试考快排最常见的问法是“写一个排序算法”。很多候选人上来就写冒泡排序或者调Arrays.sort这是错误策略。手写快排不仅能展示你了解分治思想还能展示你对边界条件和性能优化的深入理解。第一种追问是写出 partition 的每一步执行过程。面试官会给一个具体数组比如[5, 1, 4, 2, 8]让你模拟以最后一个元素为基准的分区过程画出示意图。这个环节考察你是否真正理解指针移动顺序而不是死记模板。我的建议是在纸上画一个表格每一行记录当前 i、j 的位置和数组状态能有效避免逻辑混乱。第二种追问是如何处理最坏情况。如果你最初写的是固定选最后一个元素为基准面试官多半会追问“如果数组已经有序怎么办”。这时你应主动改进为随机选基准或三数取中。这比被动等待提问更能加分。第三种追问是如何取第 K 大的元素。这是快排最重要的变体应用快速选择QuickSelect。思路是执行一次 partition 后如果基准元素的索引恰好是目标位置就直接返回如果 K 在左侧就去左侧递归否则去右侧递归。平均时间复杂度 O(n)不需要排完整数组int quick_select(int arr[], int low, int high, int k) { if (low high) return arr[low]; int pivot_index partition(arr, low, high); int left_size pivot_index - low 1; if (k left_size) return arr[pivot_index]; else if (k left_size) return quick_select(arr, low, pivot_index - 1, k); else return quick_select(arr, pivot_index 1, high, k - left_size); }6.2 现场推导复杂度的方法面试时手写快排后面试官几乎必问“时间复杂度是多少为什么”。如果只知道结论不会推导印象分会大打折扣。最简单有效的推导方式是用主定理。假设数组被分成两个规模分别为 n/2 的子问题每次 partition 扫描代价为 O(n)。递推公式为 T(n) 2T(n/2) O(n)。根据主定理a2b2f(n)O(n)满足第二种情况结果是 O(n log n)。这就是平均情况的数学表达。最坏情况递推公式是 T(n) T(n-1) O(n)也就是每次只消掉一个元素。展开得到 T(n) n (n-1) (n-2) ... 1 O(n²)。面试时可以画一个简单的递归树辅助说明只要你能把这个推导过程讲清楚基本就过关了。6.3 快排相关的常见笔试题型排序稳定性判断给一个数组要求输出快排第一趟之后的结果形态。解法是模拟一次 partition 全过程注意基准元素的最终位置。与二分算法的组合应用先快排再二分是“查找数组中是否存在某个元素”的标准解法。我遇到过的问题是在几百万个整数中找是否存在重复值快排后扫描一遍即可。逆序数计算虽然归并排序更容易实现逆序数统计但基于快排的变体也能做核心思想是分区时统计跨区间的逆序对。排序算法对比题把快排、冒泡、堆排、归并放在一个表里让候选人写复杂度并解释实际应用场景。准备面试时可以自己画表强化记忆。我在面试候选人时最常看到的问题不是不会写快排而是写完之后说不清楚“为什么这里用小于等于而不是小于”或者“随机选基准的意义是什么”。这些细节恰恰是区分背模板和理解算法的分水岭。7. 常见问题与排查技巧实录7.1 递归爆栈症状、原因与解决症状数据规模稍大程序直接崩溃报 Stack Overflow 错误。如果你用的是 Windows可能表现为程序无响应后退出。原因有两种一是数组恰好有序固定选第一个或最后一个元素做基准递归深度达到 O(n)二是栈空间本身分配得小比如嵌入式环境或某些线程栈只有默认的 1~2 MB。排查方法是加日志输出递归深度或者用调试器观察调用栈。如果确认是数据分布导致的退化优先改随机基准如果是环境限制改用 5.3 节的迭代版实现。另外编译器优化级别也可能影响栈帧大小把-O0改成-O2有时能显著减少栈空间占用。7.2 partition 返回位置导致的死循环症状程序运行卡住或者排序结果错误但数据量小的时候偶尔正常。这是递归区间划分写错导致的典型症状。我之前排查过一起问题使用 Hoare 分区但递归范围写了p-1和p1而 p 是右半区间的边界不是基准位置。结果有两个元素被反复交换程序进入死循环。排查口诀是Lomuto 返回基准下标侧边基准不参与Hoare 返回切分边界边界两边递归处理。如果不确定当前分区函数属于哪种风格可以在 partition 里临时打印返回值再对照递归区间检查。7.3 大量重复元素导致的性能雪崩症状排序几万个元素时消耗时间异常长甚至比冒泡还慢。原因前面提过普通快排把相等的元素全部分到一侧递归树严重失衡。排查方法是统计输入数据的值分布。如果重复率非常高直接换成三路快排。我之前处理用户日志数据时按状态码排序只有成功和失败两种值普通快排实测慢到不可接受。替换成三路快排后排几百万条数据只需几十毫秒。这个案例也说明没有万能的排序算法数据特征决定算法选型。7.4 随机选基准的测试不可复现问题如果在 partition 里用了rand()你会发现每次运行结果不同虽然排序结果正确但性能测试每次耗时都有差异难以复现问题。解决办法是在测试环境使用固定种子srand(42)。这样每次运行分区过程完全一致便于对比不同优化手段的效果。如果有单元测试固定种子也能让回归测试更稳定。不过要注意固定种子只适合测试环境生产环境还是要用真正的随机种子否则某些固定输入会再次触发最坏情况。8. 从快排延伸出去对整个算法学习路径的启示写完快排的实现和优化我有一个挺深的体会一个算法真正吃透不是会背代码而是能讲清楚每个细节为什么这么设计。快排恰好是这样一个完美的学习样本——它难度适中却包含了分治、递归、指针操作、复杂度分析、工程优化、数据特征感知等几乎全部核心要素。学完快排之后你其实已经获得了一张算法地图归并排序的“分治合并”技巧、堆排序的“优先队列”思想、二分查找的“区间收缩”思路、Top-K 问题里的“快速选择”变体都可以和快排串联起来。很多看似无关的算法比如 NSGA-II 这类多目标优化算法里也用到了快排的变体非支配排序需要对多个目标分别做排序底层排序模块选型就直接影响整个算法的性能。再比如粒子群算法、模拟退火算法里对适应度值的排名计算排序算法的效率也会成为整体性能的瓶颈。我个人在实际项目中养成的习惯是先分析数据规模和数据分布再决定排序方案。几万条以内、重复元素多三路快排几十万条以上且内存充足优先调用标准库的混合排序数据分布在多个链表中归并只需要找 Top-KQuickSelect。排序算法没有银弹但这个选择过程本身就是经验的积累。最后再分享一个经验没事可以自己写个小测试程序对比不同数据特征下各种排序算法的耗时曲线。我建议用三种数据测试随机数据、接近有序数据、大量重复数据各测一轮。你很快会发现教科书上的复杂度结论只是理论起点真实的工程优化远比那张表复杂。这也是为什么快排这样“朴素”的算法经过六十多年演进依然被各大标准库视为排序的中流砥柱。