如果你在真实代码里自己写过一遍快速排序大概率有过类似体验照着算法书上的伪码敲测试用例一跑没问题等把它放到几万、几十万条真实数据上结果比自己预期慢了太多甚至直接栈溢出。我当年第一次把快排用在生产脚本里就吃过这个亏。明明上学时考试都能默写怎么一到工程里就现原形这篇想聊的就是把“交换排序”这个大家庭里最能打的这位——快速排序从头到尾拆开看。它为什么能在冒泡、选择这类朴素的排序算法里跑出来平均能做到 O(n log n)它的分区函数、递归边界、基准选取是怎么影响实际性能的递归写法转成非递归要注意什么以及在 C、Java、Scratch 这些不同语言里它的落地形态又有什么差别。适合正在学算法的同学也适合写了多年代码但一直没认真抠过快排细节的工程师。快速排序本身不复杂真正复杂的是细节。1. 快速排序在交换排序家族里的地位与“快速”的本质1.1 交换排序的两条路线所谓交换排序核心动作就是“交换元素”通过不断消除序列中的逆序对让序列逐渐有序。冒泡排序是这条路线最朴素的代表它只会交换相邻的两个元素每一轮把一个最大的元素“冒”到最后面。因为每次只消除一个逆序对所以最坏情况需要 O(n²) 次比较和交换。快速排序同样依赖交换但它跳着换——不是只跟邻居换而是把某个元素放到一个位置使得它左侧的所有元素都不大于它、右侧的所有元素都不小于它这个过程叫分区。一次分区操作可能同时消除很多个逆序对这就是它“快”的根源。可以这样理解冒泡排序像是一个仓库管理员每次只挪动相邻的两箱货一箱一箱挪而快速排序像是先找个基准然后把比基准小的货全部甩到左边、大的全部甩到右边一次性完成大面积整理然后对左右两个区域再各自重复这套动作。1.2 分治框架的递归逻辑快速排序用的是典型的分治策略整体流程就三步从序列中选定一个基准值pivot。通过分区操作把小于基准的元素放到基准左边、大于基准的元素放到基准右边。对左右两个子区间分别递归执行同样操作。用一句话概括每次确定一个元素的最终位置然后递归处理剩余区间。这句话很关键——快排每次分区后基准元素已经落在了它排序完成后的最终下标上不需要再参与后续排序。这一点和归并排序有本质区别归并排序是先分后治排序过程是“自底向上”的合并快排则是“边分边排”基准元素的位置一次到位。这也是为什么快排的平均时间复杂度能达到 O(n log n)如果基准选得足够好每次分区都能把序列分成大致相等的两半递归树的深度是 log n每层处理的元素总数是 n所以是 n log n。而最坏情况——比如每次分区只把序列分成 1 和 n-1 两段——递归深度变成 n时间复杂度退化成 O(n²)。这个退化不是理论上的摆设实际工程里真的会碰到后面专门讲。1.3 稳定性问题为什么快排不稳定先回答一个面试常问的问题快速排序是稳定排序吗不是。稳定性的意思是对于键值相等的两个元素排序后它们的相对顺序保持原样。快排在分区过程中会把与基准大小比较后的元素直接交换到区间另一端这种远距离交换很可能改变相等元素的相对顺序。举个具体例子序列[3, 1, 3, 2]用 2 做基准Lomuto 分区后面会说的第一轮扫描完成后数组会变成[1, 2, 3, 3]。两个 3 在原始顺序里是 3 在前、3 在后排序后变成了 3 在前、3 在后相对顺序颠倒了。这就是不稳定的直观体现。如果业务上需要在“按成绩排序后再按姓名排序”这种多级排序里保持稳定快排不是好选择这时应该用归并排序。这也是为什么 Java 的Arrays.sort对对象数组用 TimSort归并排序的改进版、对基本类型数组才用双轴快排——因为基本类型本身没有“相等元素的相对顺序”这种语义需求可以用快排更快地排序。2. 分区函数快排的真正分水岭2.1 Lomuto分区与它的直观逻辑分区是实现快排最核心、最容易写错的函数。目前最常见的写法有两种Lomuto 分区方案和 Hoare 分区方案。Lomuto 方案思路直观选定最右边的元素作为基准维护一个指针 i表示“已经处理过的小于等于基准的元素边界”然后从左到右扫描遇到小于等于基准的元素就把 i 后移一位并交换。最后把基准换到 i1 的位置返回 i1。给一个 C 语言实现int partition_lomuto(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; }这里有两个细节值得单独说。第一个细节为什么用而不是如果用了等于基准的值会全部堆积在右边反而导致分区更不均匀用虽然也不保证严格均匀但至少把等于基准的值往左边分了一部分。第二个细节当 i j 时交换自己没有任何问题不用专门判断避免多写一个分支反而增加分支预测开销。递归调用时参照这个返回位置void quickSortRecursive(int arr[], int low, int high) { if (low high) { int pi partition_lomuto(arr, low, high); quickSortRecursive(arr, low, pi - 1); quickSortRecursive(arr, pi 1, high); } }因为 Lomuto 保证基准已经落位左右区间严格排除掉 pi 本身。2.2 Hoare分区交换次数更少但边界更隐蔽Hoare 分区是快排祖师爷 Tony Hoare 最初提出的版本。它的思路是把最左边的元素作为基准然后用两个指针从两端向中间扫描——左指针找大于等于基准的元素右指针找小于等于基准的元素找到就交换直到两个指针交错。int partition_hoare(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]); } }这版代码有三个非常容易踩的坑。第一返回的是 j 而不是 i。因为循环终止时 i 已经越过 j此时 j 才是“左区间的最后一个位置”。第二由于基准可能没有在最终位置递归时两个子区间是[low, pi]和[pi1, high]——注意左边包含 pi右边从 pi1 开始这和 Lomuto 的“pi-1 / pi1”完全不同。用错了边界就是死循环或者漏排。第三do-while 结构保证了 i 和 j 无论如何都会移动避免出现 arr[i]pivot 且 arr[j]pivot 时无限交换循环卡死。Hoare 分区的优势是每一轮交换发生在真正需要交换的元素之间等于基准的重复元素不会被多余交换整体交换次数通常比 Lomuto 少。很多优化过的快排实现都偏向 Hoare 风格。但它对理解能力的要求更高初学阶段如果求稳可以先写 Lomuto跑通了再换 Hoare。提示如果你用 Hoare 分区调试快排时发现某些元素消失了或重复了优先检查递归边界是不是写成了[low, pi-1]和[pi1, high]。Hoare 分区的返回值是“分界点”不是“基准最终位置”套用 Lomuto 的递归方式是头号错误来源。2.3 分区效率对比与实测感受两者时间复杂度都是 O(n)但常数因子不同。Lomuto 每遇到一个符合条件的元素就交换而 Hoare 只有当左右指针都找到“逆序对”时才交换。对于大量随机数据Hoare 通常要比 Lomuto 快一些对于全等值数组Lomuto 会退化成灾难——每轮分区只把最后一个基准放走递归深度 n而 Hoare 遇到全等值时 i 和 j 快速交错一次就能分完。所以如果你要写一个通用版的快排我更建议直接练 Hoare一次把边界问题吃透如果你只是为了考试手写、或者写一个逻辑最好讲清楚的版本Lomuto 更合适。知道两种方案的区别本身也是一种工程判断力。3. 递归边界与迭代版本工程实现中绕不开的两道坎3.1 递归写法里的终止条件和栈溢出风险递归版快排的终止条件就一句low high。但从工程角度递归有两个隐患。第一个是栈深度。平均情况下递归深度约 log n对于 100 万个元素也就是 20 层左右没压力但最坏情况下深度达到 n几十万层的函数调用直接把进程栈打爆。生产环境里的排序数据形状千奇百怪没人敢赌它永远不是有序的。第二个隐患是函数调用本身的开销。递归到小区间比如只剩十几个元素时快排的性能反而比不上插入排序这就是优化快排几乎必用“小区间插入排序”的原因。这两个问题在真实场景里都出现过。我之前处理一批从数据库导出的日志数据字段里带时间戳导出来基本就是有序的。我当时图省事直接用了固定选最后一个元素做基准的递归快排结果数据量一上到三十万程序直接崩了。排查半天才发现是递归深度炸掉了系统栈。这件事之后我养成了一个习惯凡是写排序第一件事先确认基准策略第二件事考虑是否需要迭代版本。3.2 非递归实现显式栈代替调用栈很多面试题会要求写“快速排序非递归版本”也有不少人误以为非递归就是用循环模拟整个排序过程。实际上快排的分治本质决定了它必然需要一个“待处理区间”的存储结构。递归版本依赖系统调用栈隐式保存非递归版本就是自己开一个栈显式保存待处理区间的上下界。C 语言非递归版void quickSortIterative(int arr[], int low, int high) { int stack[1024]; int top 0; stack[top] low; stack[top] high; while (top 0) { high stack[--top]; low stack[--top]; if (low high) continue; int pi partition_lomuto(arr, low, high); // 先处理小区间控制栈深度 if (pi - 1 - low high - (pi 1)) { stack[top] low; stack[top] pi - 1; stack[top] pi 1; stack[top] high; } else { stack[top] pi 1; stack[top] high; stack[top] low; stack[top] pi - 1; } } }这里有两点要说清楚。一是栈大小怎么估。最坏情况下栈里需要存放的区间数量级是 O(n)比如极端不平衡的每次分割。但如果你先处理小区间、再处理大区间栈的最大深度可以控制在 O(log n) 量级——因为大区间虽然晚处理但它的范围是有限的可以重复使用同一个栈空间。上面代码注释里做的就是这件事。工程上直接开一个固定大小比如 1024 的栈配合“先压大区间”策略足以应对正常数据真要较真可以动态扩容。提示非递归不等于空间 O(1)它只是把系统调用栈换成了程序自己管理的栈空间复杂度依然平均 O(log n)、最坏 O(n)。不要被“非递归”三个字误导成“迭代常量空间”。二是压栈顺序决定处理顺序。栈是后进先出你想先处理哪个区间就后压哪个区间。上面的代码用区间大小做判断是为了保证任何时刻栈里最大深度可控。如果你不在乎这一点简单地把两个区间按任意顺序压栈也能跑只是极端输入下栈会涨得很厉害。3.3 为什么工程标准库还要搞“内省排序”聊到非递归顺带提一个真实工程里的做法Java 的Arrays.sort部分版本、C 标准库的std::sort本质上都在快排之上套了一层保险。std::sort是内省排序IntroSort它先用快排同时记录递归深度一旦深度超过 2log n 就切换到堆排序兜底防止最坏情况下的 O(n²)区间小到一定阈值通常是 16时切换到插入排序。这个策略说明了一个事实快排的裸性能很猛但要安全地发布给所有用户用必须给它戴上防止退化的笼头。自己写排序代码的时候也可以借鉴这个思路。4. 输入不给你面子的时候性能退化与基准值优化4.1 最坏情况到底怎么产生的如果每次分区都把 pivot 选成了当前区间的最大或最小值那么 partition 返回的位置永远在区间端点左/右子区间分出去一个空区间另一部分还是 n-1 个元素。这样递归树变成一条链每一轮处理 n 个元素需要 n 轮总复杂度 O(n²)。什么数据最容易触发就是有序或近似有序的数据配合“固定选最右/最左做基准”的策略。比如一个已经升序排列的数组选最右做基准每轮 partition 扫描整个区间却发现所有元素都小于等于基准交换来交换去最后只把基准放到了正确位置——严格说每轮只排出 1 个元素跑完整个数组正好是 n²。这个场景在真实业务里太常见了。日志按时间排序、数据库导出结果按 ID 排序你以为自己是乱序数据其实早就有序了。所以“基准选取”不是锦上添花而是快排能否在真实数据里活下来的生死线。4.2 三种基准策略的取舍常见的有三种策略固定基准、随机基准、三数取中。固定基准实现最简单但被有序数据一击即中。随机基准随机选一个下标跟 low 交换后再分区能把最坏情况变成一个概率极低的事件期望复杂度回到 O(n log n)代价是每次分区都要调用一次随机数生成器常数开销不小。三数取中是在首个、中间、末尾三个位置取中位数作为基准它对有序数据的抵抗能力很强因为有序时中位数刚好接近真实中位数而且不需要随机数生成器开销小、可复现性强。实际工程里三数取中是性价比最高的选择。C 的实现片段int medianOfThree(int arr[], int low, int high) { 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[high]); // 把中位数放到最右方便复用Lomuto分区 return arr[high]; }取中位数本身只需要三次比较和少量交换这点开销换来的是把“有序输入”这个最常见的坏情况直接变成最优情况非常划算。4.3 重复元素杀手三路分区比有序更麻烦的是大量重复元素。比如对考试成绩排序90 分有几十万条80 分也有几十万条。普通分区对重复元素处理不好Lomuto 碰上全等值数组每轮只能挪走一个元素复杂度直接 O(n²)而三路分区也叫 Dutch National Flag 分区分法把数组分成三块——严格小于基准、等于基准、严格大于基准递归时只需要处理小于和大于两块等于的部分原地跳过。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) swap(arr[lt], arr[i]); else if (arr[i] pivot) swap(arr[i], arr[gt--]); else i; } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }三路分区最漂亮的地方在于如果数组全部是相同元素第一轮分区后 lt 和 gt 直接包住整个数组递归瞬间结束复杂度降到 O(n)。这对重复数据非常友好。写的时候要注意arr[i] pivot分支里 i 要自增因为左边交换过来的一定是小于 pivot 的、已经检查过的元素arr[i] pivot分支里 i 不自增因为从 gt 位置换过来的元素还没检查过下一轮还要再看一眼。这个细节写错就乱了。4.4 小数组切换插入排序前面提过快排递归到很小的区间时函数调用和分区的固定开销反而大于插入排序的工作量。工程标准做法是设定一个阈值比如 16、20区间长度小于阈值时直接改用插入排序。插入排序在接近有序的小数组上几乎是线性的比快排继续递归快得多。这个优化对整体性能的提升在数据量大时非常明显一个 15 万元素的数组实测经常能快 20%-30%。下面把基准优化策略整理成一张表方便对比策略优点缺点适用场景固定基准实现简单有序/逆序数据直接退化 O(n²)只做教学演示随机基准极难触发最坏情况随机数开销结果不可复现高频调用的库函数三数取中抵抗有序数据开销低可复现对病理构造数据仍可能退化通用工程首选三路分区高效处理大量重复元素代码更难常数略大重复数据多的业务数据阈值插入排序提升小数组效率阈值需要调参数据量大时的通用方案5. 从C到Java再到Scratch快排在不同语言里的落地形态5.1 C语言qsort不是快排但快排是它的祖师爷很多 C 语言学习者以为stdlib.h里的qsort就是快排。实际 glibc 的qsort实现更接近归并排序内存压力大时才退化到堆排序或插入排序并不是严格意义的快排。标准库保留“qsort”这个名字纯粹是历史习惯大家叫习惯了。C 语言版快排的价值在于它让你直面指针、数组下标、递归和栈这些底层概念写一遍等于把计算机内存模型摸了一遍。建议每个人至少手写一遍 C 版的快排不要只在 IDE 里背题。C 版还有一个好处是指针随时可以换成下标方便调试。我之前排查一个诡异的分区错误就是在写 C 版时用地址打印盯出来的printf(swap %d(%p) and %d(%p)\n, arr[i], arr[i], arr[j], arr[j])一眼就看出了两个指针越过数组边界。这种调试手段在高层语言里反而不容易用到。5.2 JavaArrays.sort背后的双轴快排Java 对基本类型数组排序用的是 Dual-Pivot QuickSort双轴快排。它跟经典快排的区别是选了 2 个基准把区间切成三段小于基准1、基准1和基准2之间、大于基准2一定程度上减少了递归深度和交换次数。Java 对对象数组却不用快排而是用 TimSort——因为对象排序需要考虑稳定性快排不稳定所以被排除。用 Java 写快排时最常见的坑是基本类型数组的 int 值比较、数组下标边界、以及用递归时对很大数组的栈溢出问题。这里给一个 Java 递归版参考public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } private static int 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; int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; }注意 Java 里比较两个 int 直接用即可但如果排序的是对象数组需要自己传Comparator并注意比较器返回值与第 0 个元素的语义。生产环境里如果只是为了给一批数字排序直接用Arrays.sort就好。提示如果你在生产代码里想“手写快排替代 Arrays.sort”我的建议是不要。JDK 开发组用了几十年打磨出的排序实现细节远超个人用几小时写的版本。自己写快排的合适场景是学习、面试、或者处理包含特殊分布的数据而不是和标准库较劲。5.3 Scratch让交换排序可视化最后说 Scratch。很多人以为 Scratch 只是少儿编程玩具但用 Scratch 实现快排/交换排序恰恰是理解算法最直观的方式之一。Scratch 里用列表存放数据、用变量模拟下标指针、用“交换列表的第 i 项和第 j 项”积木完成交换每一步都能看得清清楚楚。做排序可视化时通常还会在每次交换后加一段等待比如 0.1 秒把冒泡的“相邻交换”和快排的“跳着交换”放在同一组动画里对比非常有意思。Scratch 实现快排要处理两个难点。一个是“自制积木”支持递归调用但参数传递和局部变量要自己处理好递归深度太深时 Scratch 引擎也会变慢另一个是“交换列表项”积木需要一个临时变量来中转不能像 C 语言那样直接写 swap。写的过程中你会被迫把算法每一步的“数据流”想清楚这种训练对低龄学习者来说价值不比写出能跑的代码低。我见过不少老师用 Scratch 做排序教学先做冒泡再做快排让学生对比两种算法的“交换距离”。这个对比一旦做出来学生对“为什么快排快”的理解会比任何文字解释都深刻。5.4 三份实现的共性认知把三种语言的实现放在一起看会发现所谓“不同语言落地”其实只是表达层的差异C 让你看到内存Java 让你看到库的工程优化Scratch 让你看到过程本身。算法思想不变变的只是你手里表达它的工具箱。这也是我建议程序员多语言写同一个算法的原因——每换一种语言你被迫重新审视一遍之前跳过的细节。最后分享一个我自己的调试习惯学快排或者教快排时不要只盯着排序结果对不对而是打印每一轮分区后的数组状态——先打印原始数组再打印“基准值几分区后数组多少返回位置几”。盯着中间状态看几轮几乎所有边界错误都能一眼找到。我当年自己写 Hoare 分区时就是靠这个办法才想明白“为什么递归要用[low, pi]而不是[low, pi-1]”。快速排序不难难的是对它细节的尊重——基准怎么选、边界怎么切、重复元素怎么办以及最重要的一条别在生产环境盲目手写快排。