一文搞懂快速排序递归、基准值与三种划分方法快速排序是数据结构与算法中非常经典的一种排序算法也是面试和笔试的高频考点。它的平均时间复杂度为 O(n log n)实际运行效率较高。很多同学第一次学快速排序时容易卡在两个地方一是不理解递归过程二是不清楚基准值到底是怎么归位的。本文就从快速排序的基本思想出发依次介绍递归框架、Hoare 划分、Lomuto 划分以及三路划分最后补充复杂度分析与常见优化。1. 快速排序的基本思想快速排序的核心是递归和划分。假设数组为6,4,7,12,2,1以最左边的 6 为基准值比 6 小的放左边比 6 大的放右边一趟划分后得到2,4,1,6,12,7。然后对 6 左右两边的子数组分别递归执行同样的操作最终整个数组有序。注意一趟划分只是保证基准值左边都比它小、右边都比它大左右两边内部仍然无序需要继续递归划分。2. 快速排序的递归框架在深入划分细节之前先把递归的骨架搭好voidswap(int*x,int*y){inttmp*x;*x*y;*ytmp;}voidquick_sort(int*arr,intleft,intright){if(leftright){return;}intkeyihoare_part(arr,left,right);// 一趟划分quick_sort(arr,left,keyi-1);// 递归左区间quick_sort(arr,keyi1,right);// 递归右区间}有了递归框架之后接下来的关键就是如何围绕基准值完成一趟划分让基准值回到它最终应该在的位置。下面介绍三种常用的划分方法。3. 三种常见的划分方法3.1 Hoare 划分法Hoare 划分是快速排序最经典的实现方式也是 C 语言标准库qsort的原始版本所采用的思路。inthoare_part(int*arr,intleft,intright){intkeyileft;intkeyarr[keyi];left;while(leftright){// 从右往左走跳过大于等于 key 的元素寻找小于 key 的元素while(leftrightarr[right]key){right--;}// 从左往右走跳过小于等于 key 的元素寻找大于 key 的元素while(leftrightarr[left]key){left;}if(leftright){swap(arr[left],arr[right]);left;right--;}}// 循环结束时right 指向最后一个小于 key 的位置// 将基准值与 arr[right] 交换基准值归位swap(arr[keyi],arr[right]);returnright;}这段代码中有两个非常容易出错的细节内层 while 中需要反复检查left right否则指针可能越界比较条件使用和而非严格大于/小于且交换后left; right--;。如果使用严格大于/小于遇到与基准值相等的元素时两个指针都无法移动交换后也会原地踏步导致死循环。为什么最后交换的是 right 而不是 left循环结束时left已经越过了right此时right指向的是最后一个小于基准值的位置。将基准值与arr[right]交换后基准值来到正确位置左边都不大于它右边都不小于它。3.2 Lomuto 双指针划分法Lomuto 双指针法使用 cur 和 prev 两个指针cur 负责遍历数组prev 始终保持在最后一个小于基准值的元素位置。当 cur 遇到比基准值小的数时prev 前移然后交换 prev 和 cur 处的值当 cur 遇到比基准值大的数时仅 cur 前移prev 不动。在遍历过程中数组可以看成三个区域[left1, prev]小于 key 的区域 [prev1, cur-1]大于等于 key 的区域 [cur, right]还未扫描的区域最终 prev 及其左侧所有元素都小于基准值最后将基准值与 prev 交换即可。代码中prev ! cur的含义是先扩大小于区间再判断是否需要交换——如果 prev 和 cur 指向同一位置则无需交换避免无意义的自交换。intlomuto_part(int*arr,intleft,intright){intkeyileft;intprevleft,curprev1;while(curright){if(arr[cur]arr[keyi]prev!cur){swap(arr[prev],arr[cur]);}cur;}swap(arr[prev],arr[keyi]);returnprev;}需要注意的是普通 Lomuto 划分在遇到大量重复元素时划分效果可能不够均衡效率会下降。因此如果序列中重复元素较多三路划分通常是更好的选择。3.3 三路划分三路划分适合处理含有大量重复元素的序列。它将数组划分为三个区域小于基准值、等于基准值、大于基准值。这样可以避免重复元素反复参与递归提高排序效率。voidthree_way_qsort(int*arr,intleft,intright){if(leftright){return;}intkeyarr[left];intltleft;// arr[left...lt-1] 小于 keyintgtright;// arr[gt1...right] 大于 keyintcurleft1;// arr[lt...cur-1] 等于 keywhile(curgt){if(arr[cur]key){swap(arr[lt],arr[cur]);lt;cur;}elseif(arr[cur]key){swap(arr[cur],arr[gt]);gt--;}else{cur;}}three_way_qsort(arr,left,lt-1);three_way_qsort(arr,gt1,right);}核心思想三个指针将数组分为四个区间——[left, lt-1]小于 key[lt, cur-1]等于 key[cur, gt]待处理[gt1, right]大于 key。遇到小于 key 的往左扔lt 和 cur 同步右移遇到大于 key 的往右扔gt 左移等于 key 的直接跳过。一趟扫描后等于区自然落在中间只需对小于区和大于区递归即可。这里最容易写错的地方当arr[cur] key时交换之后 cur不能右移。因为从 gt 位置换过来的元素还没有被判断它可能小于 key、等于 key也可能大于 key所以必须继续检查当前 cur 位置。4. 快速排序的复杂度分析快速排序的平均时间复杂度为 O(n log n)。如果每一趟划分都比较均匀递归深度大约是 log n而每一层划分需要 O(n) 的时间因此整体时间复杂度为 O(n log n)。但在最坏情况下例如数组已经有序且每次都选择最左边元素作为基准值那么每次划分只能确定一个元素的位置递归深度退化为 n此时时间复杂度为O(n²)。空间复杂度主要来自递归调用栈。平均情况下为 O(log n)最坏情况下为 O(n)。5. 常见的优化方式随机选取基准值避免在有序或接近有序的数组中总是选到极端值。三数取中从 left、mid、right 三个位置中选取大小居中的元素作为基准值比随机选取更稳定。三路划分当数组中有大量重复元素时将等于基准值的元素集中到中间减少递归次数。小区间插入排序当子区间长度较小时比如小于 16改用插入排序减少递归开销。6. 常见错误忘记递归终止条件如果没有left right的判断递归会无限进行。Hoare 划分中指针越界内层 while 一定要判断left right否则可能访问越界。交换后没有移动指针交换完成后如果 left 和 right 不继续移动遇到重复元素时可能会死循环。三路划分中 cur 错误右移当arr[cur] key时cur 不能马上右移因为交换过来的新元素还没有被检查。基准值没有保存为局部变量应先用int key arr[keyi]保存基准值避免后续比较时 keyi 位置被修改导致错误。7. 完整测试代码#includestdio.hvoidswap(int*x,int*y){inttmp*x;*x*y;*ytmp;}voidprint_arr(int*arr,intn){for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);}inthoare_part(int*arr,intleft,intright){intkeyileft;intkeyarr[keyi];left;while(leftright){while(leftrightarr[right]key)right--;while(leftrightarr[left]key)left;if(leftright){swap(arr[left],arr[right]);left;right--;}}swap(arr[keyi],arr[right]);returnright;}voidquick_sort(int*arr,intleft,intright){if(leftright)return;intkeyihoare_part(arr,left,right);quick_sort(arr,left,keyi-1);quick_sort(arr,keyi1,right);}intmain(){intarr[]{6,4,7,12,2,1};intnsizeof(arr)/sizeof(arr[0]);printf(排序前: );print_arr(arr,n);quick_sort(arr,0,n-1);printf(排序后: );print_arr(arr,n);return0;}8. 总结快速排序的核心是选基准值 一趟划分 递归处理左右区间。Hoare 划分法效率较高但指针移动和边界条件需要特别注意Lomuto 划分法逻辑更直观适合理解快速排序的基本思想三路划分适合处理重复元素较多的数组。真正理解快速排序不只是记住代码更重要的是理解每一趟划分后基准值为什么能回到正确位置以及左右区间为什么还需要继续递归。