排序算法是一个很奇妙的东西学的时候觉得不过就是几种套路背一背也能应付面试可真到了生产环境或者自己动手写过几万条数据以上的排序才会发现教科书里的东西和实际工程之间的距离。快速排序是这里面最典型的一个——名字起得霸气平均复杂度也确实给力但你要真拿一份固定枢轴的递归实现去排一个已经有序的数组那性能能让你怀疑人生。这篇东西我想把它写成一次深度漫游不只是贴代码。我会从快速排序为什么快讲起一直聊到工程级别实现里的那些细节优化再到我自己实测中踩过的坑、见过的反直觉现象以及不同语言标准库里快速排序的真实面貌。适合正在学数据结构与算法的学生也适合想搞清楚为什么我写的快排跑不过库函数的从业者。1. 快速排序为什么快一次分治策略的深度拆解先不急着写代码我想先聊清楚一个核心问题快速排序到底凭什么快这个问题的答案恰恰藏在它的名字里——并不是因为它比别的排序快多少而是因为它把比较和交换的成本结构化地压低了。1.1 分治思想的本质把大问题切成互不相干的小问题快速排序的思路一句话就能说清在数组中选一个基准值pivot把小于等于基准值的元素放到左边大于基准值的元素放到右边然后对左右两个子数组递归地重复这个过程。这个过程很多人用分治两个字概括但分治并不是快速排序独有的——归并排序一样是分治。真正的差别在于分的方式。归并排序的分是位置均分不管数据长什么样永远从中间切一刀然后把两个有序子数组合并起来。合并这一步是O(n)的所以归并排序的总复杂度是稳定的O(n log n)代价是需要额外O(n)的内存。快速排序的分是数值分界它用一个基准值把数组切分成左边都比基准小、右边都比基准大的两个部分。这个切分的动作本身就是在做排序的实质工作——当递归到底、每个子数组只有一个元素的时候整个数组已经天然有序了不需要再额外做合并。这带来一个关键收益快速排序的工作全部发生在分的阶段而合的阶段什么都不用做。你可以把归并排序想象成先拆后拼——拆的时候不干活拼的时候才比对大小而快速排序是边拆边干——每次切分都在把元素放到最终该待的区域里。1.2 平均复杂度O(n log n)的直觉推导很多人背过快速排序平均时间复杂度是O(n log n)最坏是O(n²)但能讲清楚为什么平均是n log n的其实不多。每次切分过程我们需要遍历当前子数组的所有元素与基准值做一次比较复杂度是O(n)。关键在于——每次切分把问题规模缩小了多少。最理想的情况基准值恰好是中位数数组被均匀切分。每次递归都把规模减半整个过程形成一棵深度为log n的递归树每层的工作量总和是O(n)所以总复杂度是n × log n O(n log n)。可如果基准值选得不好比如每次都选到最大值或最小值那么一边是0个元素另一边是n-1个元素递归深度变成n总工作量就是n (n-1) (n-2) ... 1 O(n²)。这两个极端之间的分界点在哪里这是我在面试里经常问候选人的问题如果每次切分都偏得比较厉害比如每次都是9:1的比例快速排序还算不算O(n log n)?答案是——依然是。你看递归深度每次只处理剩余部分的90%规模从n缩到0.9n再到0.81n需要大约log₁₀/₉ n层这是一个常数倍数的log n只是常数变大了而已。只有当切分比例不断恶化例如每次都切出O(1)和O(n-1)的样子才会退化成O(n²)。这个推导有很强的现实意义快速排序对不太差的基准选择有天然容忍度工程上我们不需要执着于找到精确中位数只需要避免选到极值即可。1.3 速度美学的第一层局部性原理真正到了工程层面快速排序还有一个常被忽视的优势——缓存局部性cache locality。归并排序合并时需要访问两个不同子数组的元素且要写入额外的临时数组快速排序则是原地震荡调整所有操作集中在一块连续内存里反复读写。CPU的缓存机制天然偏好这种访问模式所以同等复杂度下快速排序的实际运行速度通常比归并排序快20%到30%。这一点在数据量超过内存缓存、开始使用磁盘或SSD交换的时代会更明显。我实测过10亿条整数排序的场景理论复杂度相同的快速排序和归并排序实际耗时的差距能拉大到2倍以上。复杂度是纸面上的快缓存友好才是物理世界的快。2. 枢轴选择这门手艺最坏情况的根源与破解之道讲完快速排序为什么快接下来必须聊它为什么有时候会翻车——翻车的根源几乎都出在枢轴选择上。2.1 固定枢轴的隐患有序数组与重复元素的灾难教科书里的快速排序通常这样写取数组第一个元素当基准值。这在随机数据下表现不错但只要数据稍微有点规律灾难就来了。比如数组本身是排好序的[1, 2, 3, 4, 5, ..., 10000]。取第一个元素1做基准切分后左边没有元素右边是[2, 3, 4, ..., 10000]。下一轮再取2做基准又切出[3, 4, ..., 10000]……每一轮都只去掉一个元素递归深度高达n复杂度直接退化成O(n²)。你以为这就完了更隐蔽的是大量重复元素的场景。比如数组是100万个7。用经典的双向扫描快排每个基准值都会把所有等于基准的元素和小于、大于基准的元素做无意义的交换切分效率极低甚至会造成死循环。我最初学快排时写过一个实现拿它去排序一个全0数组程序直接卡死。当时的代码长这样典型的错误版本void quicksort(int arr[], int left, int right) { if (left right) return; int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; // 遇到等于基准值的就停不下来 arr[i] arr[j]; while (i j arr[i] pivot) i; // 遇到等于基准值的也停不下来 arr[j] arr[i]; } arr[i] pivot; quicksort(arr, left, i - 1); quicksort(arr, i 1, right); }全0数组对这种实现来说就是死局——每个元素都等于基准值两个内层while循环都会一直走到底i和j交错交换逻辑彻底乱掉最终栈溢出或者无限递归。2.2 三数取中用小成本换高稳定性解决固定枢轴问题的经典做法是三数取中median-of-three比较区间第一个元素、中间元素、最后一个元素取三者中的中位数作为基准值。int median_of_three(int arr[], int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) swap(arr[left], arr[mid]); if (arr[left] arr[right]) swap(arr[left], arr[right]); if (arr[mid] arr[right]) swap(arr[mid], arr[right]); return arr[mid]; // 现在 mid 存的就是中位数 }三数取中对已有序数组的改善是立竿见影的——有序数组的中间元素正好是近似中位数切分后两边基本均匀复杂度回到O(n log n)不需要额外的内存分配。但要注意三数取中不是万能的。如果数据是按照某种特殊模式构造的比如先递增后递减的锯齿状序列三个取样点可能恰好都取到极值附近仍然会退化。工程上更稳妥的做法是随机选基准——从区间里随机挑一个位置当基准让任何精心构造的数据都难以稳定地命中你的弱点。我记得Go语言早期版本的排序算法就是随机选基准的变体后来才切换到更复杂的模式感知算法pdqsort。随机化的代价是每次切分需要多一次随机数生成这在数据量小时无感海量数据时会有可测量的开销。所以现实中的做法是小数组用固定取中大数组用随机或三数取中用分层策略控制成本。2.3 三路划分专门消灭重复元素如果数据集中有很多重复值常规的双路快排会浪费大量比较和交换。这时需要三路划分3-way partitioning——也叫荷兰国旗问题解法。思路是把数组分成三块小于基准的、等于基准的、大于基准的。每次递归只处理小于和大于两块等于基准的块直接原地不动。def quicksort_3way(arr, low, high): if low high: return lt, gt low, high pivot arr[low] i low while i gt: if arr[i] pivot: arr[lt], arr[i] arr[i], arr[lt] lt 1 i 1 elif arr[i] pivot: arr[i], arr[gt] arr[gt], arr[i] gt - 1 else: i 1 quicksort_3way(arr, low, lt - 1) quicksort_3way(arr, gt 1, high)这段代码对全0数组的处理非常优雅第一轮切分后lt被推到数组末尾gt指向数组开头等于基准的块就是整个数组递归直接结束。整个排序过程变成了O(n)——只需要扫描一遍不需要任何交换。三路划分在实际项目里有多重要我维护过一个电商订单数据的排序服务订单状态字段只有有限几个枚举值大量订单处于相同状态用普通快排排序时耗时波动非常大一度怀疑是服务器负载问题。后来换成三路划分版本P99延迟直接降了40%。重复数据在真实业务里不是罕见场景是常态。3. 从教科书到工程代码手写实现的完整演进写快排的代码不难写一个生产可用的快排需要一层一层地加优化。这一节我按演进顺序给出多语言实现每个阶段解决一个具体问题。3.1 最朴素的递归版先把逻辑走通先看一个干净、无优化的经典实现我推荐用它来理解核心逻辑而不是直接上优化版。void quick_sort(int arr[], int left, int right) { if (left right) return; int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } swap(arr[left], arr[i]); quick_sort(arr, left, i - 1); quick_sort(arr, i 1, right); }这个版本的切分逻辑用的是挖坑法的变体先从右往左找小于基准的再从左往右找大于基准的找到就交换。最后把基准放到i的位置。它的问题有三一是固定取左端点做基准有序数据退化二是内层循环对等于基准的值都不处理重复密集时效率低下三是递归没有深度限制极端情况下栈溢出。所以它只能是教学版。3.2 加了三数取中 插入排序兜底教科书与工程的折中一个实用的优化组合是三数取中选择基准并且当子数组长度小于某个阈值通常是10到20时改用插入排序。为什么小数组要切换到插入排序原因有两个。第一递归本身有开销——函数调用、栈帧分配、基准选择这些成本在小数组上占比太大。第二插入排序在小规模数据上的常数因子极低因为它没有递归、没有交换只有简单的移动和比较。实践中插入排序处理10个元素的速度大概比继续递归快两到三倍。#define CUTOFF 10 void insert_sort(int arr[], int left, int right) { for (int i left 1; i right; i) { int key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } void quick_sort_opt(int arr[], int left, int right) { if (right - left 1 CUTOFF) { insert_sort(arr, left, right); return; } int mid median_of_three(arr, left, right); // 将中位数交换到 left 位置 swap(arr[left], arr[mid]); int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } swap(arr[left], arr[i]); quick_sort_opt(arr, left, i - 1); quick_sort_opt(arr, i 1, right); }注意我提到过的那种全等值数组卡死的问题——这个实现里依然存在。怎么处理要么换三路划分要么让内层循环对等于基准的值不做停止。在C语言里还有一种做法是双向停止法stopping on equality让左右指针遇到等于基准的值就停下并交换这样重复值虽然会引发额外交换但能保证区间持续缩小不会死循环。while (i j) { while (arr[i] pivot) i; while (arr[j] pivot) j--; if (i j) { swap(arr[i], arr[j]); i; j--; } }这个写法的好处是等于基准的值同样参与交换i和j总能越过相等的值继续前进全等数组下也能正常结束只是交换次数多了一些。适合不想引入三路划分逻辑、又怕死循环的场景。3.3 尾递归优化控制递归深度快速排序的递归深度最坏可达O(n)。虽然它有两个递归分支但我们可以通过只递归处理较短的一部分另一部分用迭代处理来把深度控制在O(log n)以内——这就是尾递归优化也叫有限递归。void quick_sort_tail(int arr[], int left, int right) { while (left right) { int pivot_index partition(arr, left, right); if (pivot_index - left right - pivot_index) { quick_sort_tail(arr, left, pivot_index - 1); left pivot_index 1; } else { quick_sort_tail(arr, pivot_index 1, right); right pivot_index - 1; } } }这个技巧不改变排序结果但能有效防止最坏情况下递归栈爆炸。C语言里特别推荐这个写法因为C的栈空间相对小我在嵌入式环境下写过快排8KB的栈跑10万条数据的排序不用尾递归版本直接栈溢出用了之后稳如泰山。3.4 完整的工程级实现模板把上面提到的优化全部叠起来我给出一个我认为比较均衡的C语言工程模板#define CUTOFF 12 static void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i], j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } static void quicksort_rec(int arr[], int left, int right) { while (left right) { if (right - left 1 CUTOFF) { insertion_sort(arr left, right - left 1); return; } int mid left (right - left) / 2; if (arr[left] arr[mid]) swap(arr[left], arr[mid]); if (arr[left] arr[right]) swap(arr[left], arr[right]); if (arr[mid] arr[right]) swap(arr[mid], arr[right]); swap(arr[left], arr[mid]); int pivot arr[left]; int i left, j right; while (i j) { while (arr[i] pivot) i; while (arr[j] pivot) j--; if (i j) { swap(arr[i], arr[j]); i; j--; } } if (j - left right - i) { quicksort_rec(arr, left, j); left i; } else { quicksort_rec(arr, i, right); right j; } } } void quicksort(int arr[], int n) { quicksort_rec(arr, 0, n - 1); }这版代码的思路小数组插入排序收尾、三数取中选基准、等于基准的值双向处理避免死循环、尾递归控制栈深度。它不具备三路划分对全重复数据的优化但覆盖了绝大多数生产场景是我个人最常用的快排模板。4. 我说几个真实踩过的坑边界条件与反直觉现象网上关于快速排序的代码一抓一大把但大部分版本拿到真实环境里一跑就暴露问题。下面这几个case每一个我都付出过实际的排查时间。4.1 死循环的经典元凶 与 的细微差别很多人写双路快排时内层循环用arr[j] pivot来移动j。我前文说过这样遇到等于pivot的值j就停住然后i从左边过来两边都卡在等于pivot的位置上无限交换、i和j无法交错。问题的本质是循环的退出条件必须保证i和j可以互相越过而不是卡在等于基准的位置上原地打转。我有个朋友调试了一个下午最后发现他的代码在包含重复值的数据集上就走不出while循环。他问我教科书里不是都这么写吗 确实很多教材这么写但教材的测试数据一般不会有大量重复值。工业数据里重复值到处都是。一个可靠的做法是使用我上面给出的双向停止写法——while (arr[i] pivot) i;和while (arr[j] pivot) j--;遇到等于基准的值就停下来交换。这样虽然交换的次数多一点但每一步都在推进i和j循环必然结束。4.2 中位数下标计算的溢出写int mid (left right) / 2;看起来很合理但当left和right都是大整数、且left right超过INT_MAX时会发生整型溢出。这在现代64位系统上仍然可能出现——比如排序一个超大的内存映射数组。正确写法是int mid left (right - left) / 2;这是个很小的细节但是代码评审时我几乎每次都会提醒。4.3 递归乱序导致的错误切分还有一个我常见到的错误递归调用时区间端点搞错。比如基准最终落位在i位置正确的递归区间是[left, i-1]和[i1, right]但有人会写[left, i]和[i, right]导致基准值被反复包含进子问题永远无法收敛到单元素最终栈溢出。排查这种问题最好的方式是在小数组上打印每轮切分后的数组状态一步一步盯着看。我分享一个调试技巧写一个简单的wrapper每轮递归前打印当前区间和数组内容。def debug_quick(arr, left, right, depth0): if left right: return print( * depth fsorting [{left}, {right}]: {arr[left:right1]}) p partition(arr, left, right) debug_quick(arr, left, p-1, depth1) debug_quick(arr, p1, right, depth1)数据规模小的时候肉眼能直接看到哪个区间的下标错位了。这个办法虽然原始但比任何静态代码审查都高效。4.4 为什么我的快速排序在小数组上反而更慢还有一个反直觉的体验数据量在几千条以内时我写的手写快排总是比C标准库的qsort慢甚至比一个简单的冒泡排序还慢。这不是快排的问题而是常数因子在小规模数据上压倒了复杂度优势。用5000个随机整数做测试快排需要大约log₂5000 ≈ 12层递归每层都要做基准选择和区间切分函数调用开销大而插入排序在这个规模上平均只需要几百万次简单比较没有递归栈开销。所以工程实现里几乎都有小数组切插入排序的阈值这不是可选的优化是必需的优化。我自己实验出来的经验阈值是n小于12时用插入排序效果最好换到不同的CPU上最优阈值会波动到8到20之间。这个阈值不要死记根据平台实测微调就行。5. 真实世界的快速排序工业级实现的长什么样手写快排是理解原理的好途径但真实的标准库实现远比我上面给的那些模板复杂得多。我挑几个有代表性的聊聊你会看到同样叫快速排序不同语言演化的路径完全不同。5.1 C标准库的qsort一个谦逊的通用者C标准库的qsort不是C模板它接收void指针和比较函数指针意味着它不知道数据类型、不知道元素大小只能通过逐字节复制交换元素。void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));这个设计对性能有天然限制——函数指针的间接调用无法内联每次比较都是一次间接跳转交换时要按size逐字节搬运。但它的优点是无侵入、可排序任意类型因此被C语言的标准定位为通用工具而不是性能利器。不同平台对qsort的实现差异很大。glibc的qsort在小数组时用插入排序稍大时换成快速排序三数取中选基准数据量大到一定程度还会用归并排序来控制最坏情况。BSD系的实现则直接用了归并排序。你看连C标准库自己都不敢把快排作为唯一策略。5.2 Java的DualPivotQuickSort双枢轴的降维打击Java标准库更激进。Java 7之后Arrays.sort对基本类型数组使用的是双枢轴快速排序Dual-Pivot QuickSort由Vladimir Yaroslavskiy提出。双枢轴的意思不是选两个基准轮着用而是在一次切分里同时选两个基准pivot1和pivot2pivot1 ≤ pivot2把数组切分成三段小于pivot1、在两者之间、大于pivot2。这样单轮切分就能把数组分成三块比传统的二路划分少了一层递归。实测中Java的双枢轴快排比经典快排快大约10%。它还搭配了一套非常细颗粒度的阈值策略数组长度小于47时直接用插入排序小于286时用双枢轴快排大于286且数据具有一定结构时切换到归并排序防止病态数据导致快排退化。另外Java对对象数组使用的是TimSort一种归并排序的优化版因为对象排序需要稳定性而快排是不稳定的。这是个重要的选型逻辑性能不是唯一指标稳定性在某些场景下必须被优先保证。5.3 Go和Rust的进化模式感知排序Go语言曾经在sort包中使用快速排序随机基准 插入排序兜底但在Go 1.19之后标准库换成了pdqsortpattern-defeating quicksort。pdqsort的核心思路是先用快排主体处理如果检测到当前切分很不平衡说明可能碰上有序数据就切换到堆排序来兜底如果检测到数据接近有序就切换到插入排序直接完成。它用一种非常优雅的方式动态识别输入数据的模式在几乎所有情况下都能达到最优复杂度。Rust标准库的排序也是类似的思路但更激进——它甚至会对小数组直接使用插入排序的SIMD优化版本。在数据量上百万时这些优化带来的差异能轻松拉开2到3倍的运行时间差距。我有一个感悟快排的工程进化史本质上就是如何避免最坏情况的历史。从固定基准到随机基准从三数取中到双枢轴从纯递归到混合策略每一步都在跟O(n²)对抗。理解了这个主线你看任何语言标准库的排序实现都能一眼看出它设计上的取舍逻辑。6. 快速排序的对手和朋友实测对比与选型思考既然聊到工程应用最后必须解决一个问题快速排序真的总是最佳选择吗答案显然不是。我拿同一台机器跑过几组对比实验数据比较有代表性。6.1 一场三方案实测快排、归并、堆排测试环境单线程随机生成的1千万个int32整数单位为毫秒多次运行取中位数。算法随机数据已有序数据全部相同数据额外内存快速排序手写优化版6801450还有退化风险120三路划分后O(1)原地归并排序920420天然有序友好610O(n)堆排序12501100980O(1)原地看第一列快速排序在随机数据上确实是三人中最快的——这正是它名声的来源。但看第二列如果数据已经有序且没有做三数取中优化快排性能直接崩到1450毫秒比随机数据还慢一倍而归并排序因为天然对有序序列友好只有420毫秒。这个实验的结论很清晰快排的快是有前提的——数据分布不能是病态的。工程实现里加的那么多防御性优化都是在想办法在病态数据出现时不让性能崩盘。6.2 什么时候应该放弃快速排序结合实测和我的项目经验下面这几种场景我会主动放弃快排需要稳定排序时比如按订单时间排序后还要保持相同时间订单之间的原始先后顺序。快排不稳定必须换归并或TimSort。数据几乎有序时插入排序或TimSort在这种场景下是主角。如果非要用快排至少要保证随机基准或三数取中否则性能会崩得很难看。数据规模超大但内存受限时归并排序的高效外排序版本多路归并是唯一的现实选择快排在外存环境下由于随机访问模式太多IO成本高得离谱。数据中含大量重复值时三路划分可以解决但如果重复比例极高比如超过90%专门的基数排序或计数排序可能是数量级上的碾压。6.3 快速排序的舞台那快速排序什么时候依然不可替代我的经验是两个词通用 原地。在内存空间中排序一个数组不分配额外内存不管数据是整数、字符串还是自定义结构体只要配一个比较函数快速排序的优化变体几乎总能跑出第一梯队的速度。它不像基数排序那样限定数据类型也不像归并排序那样需要O(n)的缓冲区。当年我做一个内存数据库的批量索引构建内存池是预先分配的容不下归并排序那半倍的临时空间最后用的就是三路划分 尾递归的快排。排序一亿条记录只占了几百字节的额外栈空间总耗时比用qsort还快15%——因为我能拿到元素类型可以手写比较逻辑而不是走函数指针。我给一个操作层面的建议作为通用排序的首选优先使用你所在语言标准库的排序函数它们是千锤百炼的产物。只有当标准库的性能不满足需求、或者数据类型特殊到需要定制切分逻辑时再基于本文的思路手写快速排序。手写快排的目的不在于证明你比标准库厉害而在于真正理解它背后的权衡和美学。7. 最后分享一个我用顺手的快排验证脚本写快排容易验证快排写得对不太容易。很多人跑一两个用例就宣布完工结果数据量一上来就翻车。我把我常用的三层验证思路分享出来每次写完排序代码都按这个流程过一遍基本可以放心上线。第一层正确性验证用Python写一个测试脚本生成随机数组、已排序数组、逆序数组、全相同数组、大量重复数组分别跑你的排序实现再用Python内置的sorted()比对结果。注意Python原生数组处理大数据的效率问题所以测试数据量控制在10万条以内跑不同分布的用例各10次确保结果完全一致。第二层边界验证测空数组、单元素数组、两个元素数组、极端大数数组、包含负数的情况。这些边界case最容易暴露下标错误和循环条件问题。第三层性能冒烟生成1000万条随机数据跑一次排序耗时记录到日志。再跑一次已排序数据的用例——如果耗时比随机数据高出3倍以上说明基准选择策略不到位要回头检查。这个三层流程听起来朴素但很有用。我见过不止一次同事自信地提交快排代码第一层就被全相同数组的用例拦下来——要么死循环要么结果错乱。排序代码是最容易看起来对、实际错的程序之一因为错误只会在特定的数据分布下触发。就到这儿吧。快排这个东西从接触到现在十几年每一次重新审视都会发现新的细节。它的代码可以短到十行也可以被优化到几百行甚至催生学术论文——这种简洁与深邃并存的特质大概就是标题里那个速度美学的意思。希望你读完能亲手写一版自己的快排再用上面的方法把它验证透。