我最早学C语言排序算法时最先上手的是冒泡排序能写通不难但真正让我意识到“同样的排序工程实现可以天差地别”的是快速排序。工作这些年面试、笔试包括实际项目里的数据预处理快排的出现频率高得吓人。它平均复杂度O(n log n)原地排序内存开销小是大多数通用排序库的首选。但快排也很“狡猾”朴素写法遇到有序数组会退化成O(n^2)重复元素多时性能暴跌。这篇文章把快速排序从原理到多种变式完整拆开既有可直接抄的C语言代码也解释为什么这么改帮你在不同数据场景下作出选择。1. 快速排序的分治思想不只排比大小而是划分阵营1.1 一次分区只做一件事快速排序的核心是分治。从数组里选一个“基准”把小于基准的放左边大于基准的放右边等于基准的放中间或任意一侧。一次分区之后基准已经落在最终位置。剩下只要对左侧和右侧递归执行相同操作整个数组就排序完成。这个思路很像组织一个会议先定一个主持人让意见激进和保守的分别站两边主持人位置固定再对两边内部继续细分。排序结果自然而然出来。快排不是一次把所有顺序排完而是每次确定一个元素的正确位置靠递归铺开。很多人刚学时觉得partition很绕其实你只要盯住“基准最后放到哪个位置”这一点整段代码就清晰了。1.2 分治背后的复杂度直觉递归树的深度与划分是否均匀相关。理想情况下每次分区把数组折半递归树高度是log n每一层需要扫描大约n个元素总代价接近n log n。如果每次分区都极端倾斜递归树退化成一条链高度变成n每一层还要扫描当前区间总代价就是12...(n-1)n接近O(n^2)。所以快排的“快”不是绝对的它依赖基准能不能把数据切得均匀。这也是为什么后面所有变式都在围绕“选一个更接近中位数的基准”做文章。理解了这一点你就不难明白为什么固定取最左边或最右边作为基准会让有序数组变成灾难。1.3 快速排序与归并、冒泡的定位排序算法平均时间最坏时间是否原地排序是否稳定冒泡排序O(n^2)O(n^2)是稳定归并排序O(n log n)O(n log n)否需要额外O(n)空间稳定快速排序O(n log n)O(n^2)是不稳定从表格里看快排的最大优势是原地排序几乎不用额外内存。同时partition过程访问的是连续内存区域缓存命中率比归并排序好。对于百万级int数组快排在大多数随机数据场景下是性能之王。它不稳定这个后面会专门讲。快排的适用场景很明确C语言嵌入式环境内存紧缺排序基本元素如int、double、结构体主键时常用快排对链表排序则更适合归并因为链表无法原地随机访问快排的优势发挥不出来。2. 基础版快速排序C语言手写把每个细节掰开2.1 Lomuto分区方案最容易理解的partitionLomuto分区维护慢指针i和快指针j。i指向下一个小于基准的位置j遍历数组。遇到小于基准的元素就与i位置交换i。最后把基准换到i处。这个写法最直观很适合教学和面试讲解。void swap(int *a, int *b) { int t *a; *a *b; *b t; } int partition_lomuto(int arr[], int low, int high) { int pivot arr[high]; // 取最右侧作为基准 int i low; // i是较小元素区域的右边界 for (int j low; j high; j) { if (arr[j] pivot) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[high]); // 基准归位 return i; } void quick_sort_lomuto(int arr[], int low, int high) { if (low high) return; int pi partition_lomuto(arr, low, high); quick_sort_lomuto(arr, low, pi - 1); quick_sort_lomuto(arr, pi 1, high); }这里pivot取的是arr[high]循环只到high-1避免基准自己和自己比较。最后arr[i]一定是不小于pivot的值所以交换之后基准落在正确位置。判断条件是arr[j] pivot而不是这样等于基准的元素会留在右侧避免一次交换产生大量重复元素向一侧堆积但这个问题只靠Lomuto是解决不彻底的后面三路快排再处理。2.2 Hoare分区方案双指针对撞少交换Lomuto写法简单但交换次数偏多。Hoare分区从两端向中间扫描左边找大于等于基准的右边找小于等于基准的找到一对就交换。它把等于基准的元素分散到两侧在随机数据下效率通常优于Lomuto。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]); } } void quick_sort_hoare(int arr[], int low, int high) { if (low high) return; int pi partition_hoare(arr, low, high); quick_sort_hoare(arr, low, pi); quick_sort_hoare(arr, pi 1, high); }注意这里返回j递归左边界是[low, pi]右边界是[pi1, high]。Hoare的返回值是分界位置基准不一定在pi上这和Lomuto完全不同。很多初学者把Lomuto的递归写法[low, pi-1]照搬到Hoare上结果漏排元素甚至死循环。我自己就踩过这个坑调试了半天才发现分区返回值含义不一样。2.3 递归框架的边界条件所有快排递归版本都必须有base caselow high返回。为什么是当区间只有一个元素或空区间时不需要排序。分区返回的pi必须落在[low, high]内否则递归参数会越界。还有一个小细节Lomuto里pivot取自arr[high]分区后arr[i]就是pivot。如果数组中有多个值与pivot相等等于的值会进入右侧区间不影响正确性因为左侧区间严格小于pivot右侧区间包含等于和大于pivot的元素它们仍然满足分区性质。快排只要求左区间元素不超过右区间不要求严格把等于独立出来所以这种写法是对的。3. 为什么朴素快排不够用退化路径分析3.1 已有序数组的噩梦Lomuto固定取最右侧为基准当输入数组已经升序时每次partition都扫描整个区间只有一个元素被归位。递归树退化成链比较次数接近n(n-1)...1 O(n^2)。实际排序100000个升序整数朴素快排会比冒泡还慢甚至因为递归深度过深导致栈溢出。很多教程只讲代码不讲退化导致新手以为快排就是万能算法。工程中大部分数据并不是完全随机比如数据库导出的结果常常有序或近似有序。所以工程排序库不会直接用这个朴素版本。面试问快排最常追问的就是“已排序数组会怎样”如果你答不出退化基本就凉了。3.2 退化方向三个核心变量快排性能取决于三个点基准选取得好不好是否接近中位数决定划分是否均匀。重复元素多不多普通partition遇到大量相等元素时可能把相等的元素来回交换浪费大量时间。递归深度大不大最坏情况下深度是n系统调用栈可能爆掉。后面介绍的变式基本都围绕这三个方向优化。随机化和三数取中解决基准选择问题双路和三路解决重复元素问题非递归和深度限制解决递归深度问题。可以说快排的整个进化史就是这三个变量的优化史。4. 多种变式的原理与C语言实现4.1 随机化快速排序让最坏情况变成概率事件在partition前随机选一个下标与high位置交换再执行原来的单路分区。这样输入有序也无法稳定触发最坏情况因为基准是随机选的。随机化期望时间复杂度O(n log n)最坏情况概率极低连续n次都抽到极偏基准的概率近乎为0。#include stdlib.h #include time.h void quick_sort_random(int arr[], int low, int high) { if (low high) return; int rand_idx low rand() % (high - low 1); swap(arr[rand_idx], arr[high]); int pi partition_lomuto(arr, low, high); quick_sort_random(arr, low, pi - 1); quick_sort_random(arr, pi 1, high); }调用之前一定要在main里只设置一次种子srand((unsigned)time(NULL));。如果每次递归都srand短时间连续调用会生成相同种子随机化就失去意义。随机化还有一个额外价值你无法构造恶意输入让程序稳定变慢这在应对极限测试时很有用。4.2 三数取中法工程里用得最多的基准选择随机化不错但rand调用本身有成本而且结果不可控。更稳的办法是从low、mid、high三个位置取中间大小的值作为基准。数组接近有序时三数取中能选出靠近中位数的值退化概率大幅降低。C语言实现int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; int a arr[low], b arr[mid], c arr[high]; if ((a b) ! (a c)) return low; else if ((b a) ! (b c)) return mid; else return high; }分区时把选中的下标对应值与high交换后续逻辑复用Lomutoint pi_idx median_of_three(arr, low, high); swap(arr[pi_idx], arr[high]); int pi partition_lomuto(arr, low, high);三数取中比随机化更“确定”在有序和逆序输入上表现很好是很多排序库的默认策略。缺点是三个指针访问增加了少量比较但这点开销换来的是分区稳定性非常划算。4.3 双路快速排序解决大量重复元素的交换浪费普通单路快排在全部元素相同时会怎样Lomuto的i会一直停在low位置j扫完整个数组最后基准与arr[low]交换形成左侧为空、右侧长度为n-1的极端划分直接退化为O(n^2)。双路快排通过两边对撞查找把等于基准的元素分散到两侧避免全部堆积在同一侧。void quick_sort_dual(int arr[], int low, int high) { if (low high) return; 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) break; swap(arr[i], arr[j]); } quick_sort_dual(arr, low, j); quick_sort_dual(arr, j 1, high); }这段代码实际上就是Hoare分区但它额外的价值在于处理重复元素。当所有元素相同时左指针i向右走一步就停在第一个元素上右指针j向左走一步也停在最后一个元素上然后swap接着两个指针继续向中间移动。每次划分都能把数组大致分成两半不会退化。双路快排是很多高性能排序实现的基础。4.4 三路快速排序荷兰国旗思想处理重复双路快排已经缓解了重复但还没有做到“等于区”隔离。三路快排用lt、gt两个指针划分出小于区、等于区、大于区。只有小于区和大于区递归排序等于区直接跳过。重复元素极多时这是显著优化。void quick_sort_3way(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; int lt low; // arr[low..lt-1] pivot int i low; // 扫描指针 int gt high; // arr[gt1..high] pivot while (i gt) { if (arr[i] pivot) { swap(arr[lt], arr[i]); lt; i; } else if (arr[i] pivot) { swap(arr[i], arr[gt]); gt--; // i不增加因为换过来的arr[gt]还没比较 } else { i; } } quick_sort_3way(arr, low, lt - 1); quick_sort_3way(arr, gt 1, high); }三个指针的写法很容易乱。我建议在纸上画一个例子pivot2数组[1,2,2,3]逐步跟踪i、lt、gt变化。核心记忆点遇到比基准小的交换到左边去然后lt和i都前进遇到比基准大的交换到右边去gt后退i不动遇到等于基准的i直接前进。所有元素相同时i一路走到底lt和gt不移动只递归空区间几毫秒就能排完百万级数据。4.5 小数组切入插入排序降低递归尾部开销当待排序区间长度很小时递归调用和分区开销比直接插入排序更高。插入排序在短数组上且基本有序时非常快。工程实现通常会设置阈值比如10到30区间长度小于等于阈值时切到插入排序。void insertion_sort(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; } } void quick_sort_cutoff(int arr[], int low, int high) { if (high - low 15) { insertion_sort(arr, low, high); return; } int pi partition_lomuto(arr, low, high); quick_sort_cutoff(arr, low, pi - 1); quick_sort_cutoff(arr, pi 1, high); }注意这个切换要放在递归函数顶部而不是在main里先对整个数组做插入排序。整体插入排序是O(n^2)救不了大局。它只是在递归到底层区间变小时减少调用和分区消耗。阈值不是越大越好过大的阈值会让插入排序的O(n^2)特性反过来拖慢性能一般10到30是平衡点。4.6 非递归快排用显式栈替代call stack极端输入下快排递归深度可能等于n系统调用栈会崩。C语言自带的递归栈容量有限工程上可以自己维护一个显式栈保存待处理区间。思路很直接把[low, high]先压栈每次弹出区间分区后把左右区间压栈直到栈空。typedef struct { int low, high; } Range; #define MAX_STACK 1024 void quick_sort_iterative(int arr[], int n) { if (n 1) return; Range stack[MAX_STACK]; int top 0; stack[top] (Range){0, n - 1}; while (top 0) { Range r stack[--top]; int low r.low; int high r.high; if (low high) continue; int pi partition_lomuto(arr, low, high); // 先压入较大的区间可以更稳定地控制栈大小 if (pi - low high - pi) { stack[top] (Range){pi 1, high}; stack[top] (Range){low, pi - 1}; } else { stack[top] (Range){low, pi - 1}; stack[top] (Range){pi 1, high}; } if (top MAX_STACK) { fprintf(stderr, stack overflow\n); exit(1); } } }注压栈顺序不影响排序正确性后压的先处理也没关系。上面为了演示用了固定大小数组真正工程中最好用动态数组或者链表实现栈。显式栈比系统调用栈更容易控制也能避免递归爆栈适合在资源受限的嵌入式环境里使用。4.7 内省排序给快排系上安全绳C std::sort使用的introsort思路是快排为主同时记录递归深度。当深度超过2*log2(n)时说明分区严重失衡切换为堆排序兜底保证最坏情况O(n log n)。C语言实现完整版需要写堆排序这里展示简化框架void quick_sort_intro(int arr[], int low, int high, int depth) { if (low high) return; if (depth 0) { heap_sort(arr low, high - low 1); return; } int pi partition_lomuto(arr, low, high); quick_sort_intro(arr, low, pi - 1, depth - 1); quick_sort_intro(arr, pi 1, high, depth - 1); }调用时depth可以先用int depth 2 * (int)(log2(n));近似计算。这个变式把快排的灵活性和堆排序的最坏情况保证结合在一起是工业界最成熟的优化组合。C语言里如果不想自己写全可以直接调qsort不过qsort内部实现取决于编译器你依然需要知道这些原理才能决定是否替换。5. 实战中的常见坑与排查记录5.1 越界访问数组长度计算错误我见过一个很典型的错误把快排函数设计成只接收数组指针不接收长度然后在函数内部用sizeof(arr)/sizeof(arr[0])计算长度。数组作为函数参数传入时退化为指针sizeof(arr)得到的是指针大小不是数组大小计算结果完全错误。正确做法是显式传入长度或者像上面代码一样用low、high区间控制。还有一种坑是把数组当作字符串用strlen计算长度。int数组里可能包含0值strlen遇到0就停了排序范围直接截断。所以我建议对整型数组统一用显式长度n不要依赖终止符。5.2 递归死循环分区返回值用错Lomuto返回基准位置递归用[low, pi-1]和[pi1, high]Hoare返回分界位置递归用[low, pi]和[pi1, high]。如果混用基准元素会被漏掉或重复处理轻则排序结果错重则无限递归直到栈溢出。排查方法在partition函数里打印返回值和当前区间或者设置一个最大递归次数用来中断。还可以在排序结束后加一道断言检查arr[i] arr[i1]如果失败重点怀疑分区边界。很多拿到手写的快排不稳定的同学九成都是边界问题。5.3 稳定性到底影响什么快排不稳定意思是相同关键字的元素排序后相对顺序可能改变。对纯数字数组来说无所谓但如果排序的是结构体并且需要按多个字段依次排序不稳定可能会破坏前一个字段已排好的顺序。比如先按姓名排序再按分数排序如果第二个排序用快排分数相同的同学可能出现姓名顺序错乱。这种场景必须用稳定排序算法比如归并排序。所以在选排序算法时不要只看速度还要问自己一个问题“这些数据有没有需要保持的相对顺序”5.4 性能数据不同变式在三种输入上的表现我在普通PC上用100万个int做了个简单对照结果大致如下场景基础Lomuto三数取中随机化三路快排随机数据约90ms约95ms约110msrand开销约100ms升序数据严重退化可能数秒约20ms约20ms约15ms全相同数据退化到O(n^2)约15ms约15ms约2ms数字会因机器和优化级别不同而变化但趋势很明确朴素版不是不能用而是面对真实数据太脆弱。变式不是炫技而是在不同数据分布下保住O(n log n)下限的必要手段。5.5 测试与计时方法写排序代码后第一件事不是立刻计时而是验证正确性。生成随机数组排完检查arr[i] arr[i1]。再加几个“陷阱”用例空数组、单元素、升序、逆序、全相同。如果某个版本挂了多数是基准位置和递归边界问题。计时建议用clock()或者gettimeofday排除printf输出重复多次取稳定最小值。排序结果一样性能对比才有意义。我通常还会把基准版本和其他变式放在同一个main里排同一份数据这样对比最公平。6. 我的组合策略与后续建议6.1 手写快排时会用哪个组合如果项目不允许引入高级语言标准库只能自己写排序我通常采用“三数取中 小数组切插入排序 双路分区”的组合。如果确认数据里有大量重复值就把双路替换成三路快排。阈值设15depth限制交给上线前的压测。这个组合在绝大多数数据分布下都稳而且代码不算复杂适合直接嵌入到C项目里。我自己实测下来三数取中加插入排序阈值比随机化快排少一点函数调用开销比裸快排稳得多。遇到全相同数据也不会翻车因为双路/三路已经把最坏情况摁住了。唯一要提醒的是不要迷信某个变式是银弹要根据数据特征做选择。6.2 这些变式能迁移到哪些地方快排的分区思想还能用到快速选择、找第K大元素、TopK问题、数组元素去重等场景。比如快速选择算法只要在partition后判断基准位置和目标位置的关系就能在平均O(n)时间内找到第K大元素不用完全排序。理解了双路和三路的分区细节这些代码可以顺手改出来。备考或者面试时快排最常问的不是默写而是最坏情况、稳定性、如何避免退化。你能把随机化、三路快排、内省排序这几个优化讲清楚比背十行代码有说服力得多。我自己也是从一个个坑里慢慢踩过来希望这篇内容能帮你绕过那些弯路。