如果你和我一样是靠刷 LeetCode 硬啃基础算法过来的那“快速排序”这四个字你绝对不陌生。很多人在基础算法集训里把它当成一道“背模板题”——敲一遍快排代码、跑通几个用例就觉得自己会了。但真到了手撕代码、处理大数据量、甚至面试被追问“为什么这里要这样写”的时候才发现自己只是把代码抄了一遍并没有理解快排背后的分治逻辑和边界细节。这篇文章就从我自己的集训记录出发把“基础算法集训第08天快速排序”这节内容展开成一份完整的实战笔记。我会从核心思路、代码实现、边界讨论、优化方案到问题排查一条链路讲透适合正在刷题准备面试、复习算法基础或者工作中需要对数据排序做性能调优的同学。你完全可以把它当作一份能直接落地的手册而不是又一篇“教科书复读机”。1. 快速排序的整体设计与核心思路1.1 为什么叫“快速”排序排序算法有很多种冒泡排序、选择排序、插入排序都是 O(n²) 级别归并排序稳定但需要额外 O(n) 的空间。快速排序之所以被冠以“快速”二字是因为它在绝大多数情况下能把平均时间复杂度做到 O(n log n)而且是在原地排序几乎不消耗额外内存。它厉害在哪举个生活中的例子你有一个乱糟糟的书架想按书名首字母排好。最常见的笨办法是把所有书两两比较并交换位置冒泡排序就是这么干的而快排的思路是随手抽一本书当“基准”把比它“小”的书放到左边比它“大”的放到右边然后再分别对左边和右边的书堆做同样的操作。每抽一次基准问题规模就缩小了一半左右整个过程像极了把大任务切成两个小任务这就是分治思想。这种分治思路放到计算机里有一个非常现实的收益排序不需要额外的临时大数组所有交换都在同一个数组内完成内存占用约等于零。对于动辄上百万条记录的数据量来说内存开销优势非常明显。1.2 快速排序的三个核心步骤快速排序的执行逻辑可以分解为三个动作选择基准元素pivot一般取区间第一个、最后一个或中间位置的元素。分区partition将数组重新排列成三个区域——小于基准、等于基准、大于基准然后返回基准元素最终落位的位置。递归地对基准元素左侧区间和右侧区间重复上述过程直到每个子区间只剩一个或零个元素。这里面最核心、也最容易出错的环节是第二步“分区”。分区的目标不是“排好序”而是“让基准元素回家”即确保基准左边的元素都不大于它右边的元素都不小于它。至于左右两边内部的顺序暂时乱着也没关系交给递归去处理。这里必须明确一个容易混淆的点分区不是一次性把所有元素都排好只保证基准元素待在它最终排序后的位置上。也就是说每一趟递归结束后至少有一个元素基准的位置是确定的不会再改变。这是理解快排递归层数和总时间复杂度的关键。1.3 分区策略以左右指针交替腾挪为例初学者建议先掌握最容易想清楚的分区方式左右指针交替腾挪法。思路很直白选取区间左端点作为基准值 pivot。设置两个指针 i 指向左边界j 指向右边界。j 先从右向左找第一个小于 pivot 的元素停下来。i 再从左向右找第一个大于 pivot 的元素停下来。如果 i 仍然在 j 左边就交换 a[i] 和 a[j]然后继续扫描直到 i 和 j 相遇。相遇位置和基准位置交换这样基准值就落到了正确位置。用一组测试数据推演一下初始数组 [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]取最左边 6 为基准。j 从右往左找到第一个小于 6 的数是 5停在 index 7i 从左往右找到第一个大于 6 的数是 7停在 index 3。交换后数组变成 [6, 1, 2, 5, 9, 3, 4, 7, 10, 8]。继续扫j 又找到 4i 找到 9交换……最终 i 和 j 在某个位置相遇把该位置与 index 0 的 6 交换6 就严格要求左边的数都不比它大右边的数都不比它小。第一趟分治结束之后对 [6 左边的区间] 和 [6 右边的区间] 再递归调用即可。这个分区的直观理解是每一轮都在“修正”一个数的位置同时把比它小的和比它大的分到两侧。很多教材里称为“挖坑填数”法本质上是一个思路。2. 完整代码实现与关键细节讲解2.1 C 实现从零手写快排这里给出一份可以直接编译运行的 C 快速排序实现。它不是最简短的版本但边界和意图写得非常清晰适合初学阶段照着敲。#include iostream #include vector using namespace std; int partition(vectorint nums, int left, int right) { int pivot nums[left]; // 选区间左端点为基准 int i left, j right; while (i j) { // 从右往左找第一个小于 pivot 的数 while (i j nums[j] pivot) j--; // 从左往右找第一个大于 pivot 的数 while (i j nums[i] pivot) i; if (i j) { swap(nums[i], nums[j]); } } // i 和 j 相遇时把基准换到中间位置 swap(nums[left], nums[i]); return i; } void quickSort(vectorint nums, int left, int right) { if (left right) return; // 区间无效或只有一个元素递归终止 int pivotIndex partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); // 递归排序左半部分 quickSort(nums, pivotIndex 1, right); // 递归排序右半部分 } int main() { vectorint nums {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}; quickSort(nums, 0, nums.size() - 1); for (int x : nums) cout x ; return 0; }细节一while (i j nums[j] pivot)里的特别重要。如果写成遇到与基准相等的元素时j 指针会卡住不动导致死循环。同理右边的也不能少它保证了与基准相等的元素不会被左右反复扫描。细节二partition最后一步swap(nums[left], nums[i])是基准值归位。为什么是 nums[i] 而不是 nums[j]因为在双指针相遇时 i 和 j 相等所以写哪个都行。但要注意基准取左端点时必须保证最后交换的位置上的元素小于等于基准值。这个性质由右侧扫描保证——j 先移动所以最终相遇点时如果是有 j 找到的那相遇点元素一定小于 pivot。这是选左端点为基准时的固定写法不建议调换扫描顺序否则会出 bug。如果想写得更短也可以用 Lomuto 分区法用单指针记录小于基准的区域边界。这种实现更简洁很多教科书和 LeetCode 题解采用它。int partitionLomuto(vectorint nums, int left, int right) { int pivot nums[right]; // 选右端点为基准 int i left; // i 表示小于 pivot 区域的右边界 for (int j left; j right; j) { if (nums[j] pivot) { swap(nums[i], nums[j]); i; } } swap(nums[i], nums[right]); return i; }Lomuto 版本的代码量少理解起来更容易整个扫描过程维护一个“小于基准”的前缀区每次发现比基准小的元素就把它挪到前缀区末尾最后基准与前缀区末尾元素交换。它的缺点是交换次数比左右指针法多但现代 CPU 上差异不大做题和写工程代码都够用。2.2 Java 实现把快排写进业务代码如果面试要用 Java 手撕快排建议写 Lomuto 版本因为代码量少、不易出错。这里给出一份带泛型的写法方便在处理对象数组时直接使用。public class QuickSort { public static T extends Comparable? super T void quickSort(T[] arr, int left, int right) { if (left right) return; int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static T extends Comparable? super T int partition(T[] arr, int left, int right) { T pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j].compareTo(pivot) 0) { T tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; } } T tmp arr[i]; arr[i] arr[right]; arr[right] tmp; return i; } public static void main(String[] args) { Integer[] nums {9, 3, 7, 1, 5, 6, 8, 2, 4}; quickSort(nums, 0, nums.length - 1); for (int x : nums) System.out.print(x ); } }用 Java 写的时候要注意compareTo的语义对象数组的排序依赖于泛型边界T extends Comparable? super T这样既能排序字符串、自定义对象又不会在编译期埋雷。实际业务里很少直接手写排序因为Arrays.sort内部已经对基本类型用双轴快排、对对象用归并排序做了优化但手写的意义在于理解底层原理遇到需要定制排序规则、或者数据规模可控的嵌入式场景时能自己掌控性能。2.3 边界条件检查清单快速排序的代码看似很短但边界条件一旦写错轻则排序错误重则栈溢出、死循环。我整理了一份自查清单写完代码后逐一对照检查检查项正确写法常见错误递归终止条件left right写成left right区间为left right时漏判右指针查找方向nums[j] pivot改成后与基准相等元素死循环左指针查找方向nums[i] pivot改成后与基准相等元素死循环指针越界内层 while 必须加i j不加会一路扫描到数组外基准归位swap(nums[left], nums[i])归位错误导致分区失效递归区间[left, pivotIndex-1]和[pivotIndex1, right]把pivotIndex再次包含进去造成无限递归2.4 一个必须理解的性能模型为什么最坏情况是 O(n²)很多人背下了快排的时间复杂度是 O(n log n)却说不清为什么会退化到 O(n²)。原因藏在分区的“平衡度”里。每次 partition 后如果基准元素恰好落在区间中部那么两个子区间大小接近 n/2递归深度是 log₂n而每层 partition 要扫描 n 个元素所以总时间是 O(n log n)。这是快排的理想状态。但如果每次选到的基准都是当前区间的最小值或最大值比如对已经有序的数组每次取最后一个元素作基准那么每次只能排出最大数左区间永远是 n-1递归深度就变成 n每层依然扫描 n 个元素总时间退化到 O(n²)。这也是为什么“有序数组 固定选取边界基准”是快排最经典的陷阱组合。明白了这个模型后续的优化方向就很清晰让基准尽量接近中位数。这也引出了下一章的三种优化策略。3. 三种可落地的优化方案与工程实践3.1 三数取中法选基准最简单有效的抗退化手段不再固定选左端点或右端点而是取当前区间最左侧、中间、最右侧三个元素的中位数作为基准值然后把它交换到区间端点。为什么是三数而不是全部元素的中位数因为找出真正的全区间中位数本身需要 O(n) 时间做完之后再分区整个算法的常数因子会变大得不偿失。而三数取中是 O(1) 的代价却能显著降低选中最大或最小值作基准的概率尤其对“几乎有序”的输入非常有效。int getMedianIndex(vectorint nums, int left, int right) { int mid left (right - left) / 2; // 简单比较三个位置返回中间值的下标 if ((nums[left] - nums[mid]) * (nums[left] - nums[right]) 0) return left; if ((nums[mid] - nums[left]) * (nums[mid] - nums[right]) 0) return mid; return right; }在 partition 开头先取出中位数下标与 left 位置交换后面的逻辑完全不变。这段代码用下差判断中间值不需要额外的复杂排序能跑就行。3.2 随机化基准防御恶意输入三数取中处理“有序输入”很有效但面对精心构造的攻击数据仍然可能退化比如故意让三数取中判断出相同的区间端点值。更稳妥的工程做法是随机化选基准——在left到right之间随机选一个下标与 left 交换然后执行标准分区。随机化的意义在于无论输入本身多么“有序”只要基准是随机选出来的出现极端不平衡分区的概率就变得非常低。这在实际工程中是一种典型的自防护措施。比如处理外部传入的排序请求时数据可能是升序、降序、全相等、或者藏着一组最大值随机化能让算法在统计意义上保证 O(n log n) 的期望复杂度。用 C 实现时注意别用古老的rand()它在某些编译环境下生成的随机数序列并不理想。推荐用random库或chrono::steady_clock种子生成均匀分布的随机下标。#include random int randomIndex(int left, int right) { static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distributionint dist(left, right); return dist(gen); }3.3 小区间插入排序与递归深度限制递归快排在数据量很小的时候函数调用开销占比会变大反过来不如简单的插入排序快。经典的工程优化是设定一个阈值比如 16 或 32当子区间长度小于阈值时改用插入排序不再继续递归。void quickSortOpt(vectorint nums, int left, int right) { if (left right) return; if (right - left 16) { // 插入排序 for (int i left 1; i right; i) { int key nums[i]; int j i - 1; while (j left nums[j] key) { nums[j 1] nums[j]; j--; } nums[j 1] key; } return; } int pivotIndex partition(nums, left, right); quickSortOpt(nums, left, pivotIndex - 1); quickSortOpt(nums, pivotIndex 1, right); }这个阈值不是玄学它是基于实测的权衡结果当子区间小于 16 时插入排序的常数小、且天然利用 CPU 缓存局部性整体耗时往往比继续划分快。不同硬件环境下的最优阈值可能有波动日常写代码时取 16 即可。工程界对快排的优化远不止这几点。C STL 的std::sort就是一个混合排序快排 堆排序 插入排序。当递归深度超过某个阈值通常是 2×log₂n时自动切换为堆排序防止极端情况退化当区间小于阈值时切换到插入排序降低常数。Java 的Arrays.sort对基本类型使用双轴快速排序对引用类型使用 TimSort。理解这些底层实现的逻辑对你做技术选型很有帮助。4. 常见问题与排查技巧实录4.1 死循环指针扫描条件写错我刚开始写快排时最喜欢犯的死循环错误是把nums[j] pivot写成nums[j] pivot。场景是这样数组里出现了多个与基准相同的值j 指针想找“小于基准”的数但扫描了一圈全是等于基准的于是 j 一直停在原地外层while (i j)永远满足代码就卡住了。排查手段很简单打印每一轮 partition 结束后的数组重点观察是否有两个相邻交换卡死。有效规避方法是在写内层循环时始终保留等号只在指针相遇后退出让相等元素用最后一步交换归位。4.2 分区后基准不在正确位置理论上partition 完成时基准元素的下标就是它最终在有序数组中的位置。但如果你实现的版本返回的是 i 而实际基准没有落到这个位置排序结果就会出问题。一个很隐蔽的原因是分区时基准选的是 left但内部扫描选择了 Lomuto 分区最后交换 swap(nums[i], nums[right]) 时 right 不再是基准下标导致基准放到了错误位置。不同分区策略的基准归位写法不能混用这是代码移植时最容易踩的坑。4.3 全相等数组的性能退化如果输入是 [5, 5, 5, 5, ...]普通快排在 partition 时会出现什么情况j 从右往左找小于基准的值找不到一路跌到 lefti 从左往右走也一路碰不到大于基准的值直到和 j 汇合。最终基准和自身交换左右子区间是 n-1 和 0递归深度变成 O(n)。解决思路有两个方向一是三路快排把数组分成“小于基准、等于基准、大于基准”三块每次递归只处理小于和大于两块等于块全跳过二是用随机化基准但这只能降低退化概率不能根除。如果面试或业务中出现大量重复数据优先写三路快排。用三路快排处理 [5, 5, 5, 5] 时等于区会占满整个区间递归直接结束时间复杂度骤降到 O(n)。代码逻辑可以基于现有 partition 扩展维护lt、gt两个边界即可。void quickSort3Way(vectorint nums, int left, int right) { if (left right) return; int pivot nums[left]; int lt left; // lt 左边都是小于 pivot 的 int i left 1; int gt right; // gt 右边都是大于 pivot 的 while (i gt) { if (nums[i] pivot) { swap(nums[lt], nums[i]); lt; i; } else if (nums[i] pivot) { swap(nums[i], nums[gt]); gt--; } else { i; } } quickSort3Way(nums, left, lt - 1); quickSort3Way(nums, gt 1, right); }4.4 递归栈溢出数据量太大怎么办快排是递归算法栈深度取决于递归层数。最坏情况 O(n) 的递归深度在数据量达到百万级时函数调用栈极有可能溢出。解决思路是改用“尾递归优化”把递归改成循环形式每次 partition 后只管递归调用更短的区间对更长的区间重复循环处理。这样可以保证递归深度不超过 O(log n)因为每次只对一个子区间递归另一个子区间在本轮循环内被继续缩小处理。很多教科书把这种优化称为“尾递归快排”它不能降低时间复杂度但能显著降低栈空间占用是处理大规模数组时的保命技巧。4.5 手撕快排的面试与刷题实用技巧LeetCode 上很多题目其实不直接考快排但需要用到快排思路比如“数组中的第 K 个最大元素”“最小 K 个数”。这些题的推荐解法是“快速选择”本质是快排分区后只递归一侧平均复杂度降到 O(n)。如果已经熟练掌握快排的 partition做这些题会非常顺手。再分享一个刷题测试的小技巧写完快排后不要只跑题目给的样例自己构造至少三组对比测试数据——一组升序、一组降序、一组全部相等。用标准库的std::sort或Arrays.sort排序结果做基准和你自己的实现逐元素比对。这种“对拍”模式能在五分钟内暴露绝大多数实现 bug。我曾经在一次线上问题中排查数据乱序最后发现不是排序算法的问题而是业务代码把排序结果强行合并到未排序的分片中。所以做任何排序优化前先确认数据到底是在哪个环节发生变化的是算法问题的可能性并没有那么高。写在最后的个人体会我做了很多年算法面试官和一线开发见过大量候选人能把快排代码背诵得一字不差但被问到“如果输入已经有序你的代码性能如何”时却说不出所以然。反倒是那些会从分治思想出发、边写边解释分区策略和相等元素处理的人让我觉得真正掌握了快排。基础算法集训的意义恰恰在此熟记模板只是起点理解每一次交换背后的动机、每一种退化场景触发的原因你才算真正把这个算法内化成自己的工具。等你养成了对拍测试、边界自查、复杂度推演的习惯后后面学堆排序、Timsort、桶排序都会轻松很多。