快速排序核心解析：三种partition方法及基准值优化

1. 快速排序的整体思路与基准值选型

1.1 partition的本质：一次划分到底干了什么

快速排序说难也难，说简单也简单。它核心就做一件事：选一个基准值，把数组划分成两块——左边都比它小，右边都比它大。这一步在算法里叫 partition（划分），做完之后，基准值自己就落在了最终排序的位置上，因为它左边的都比它小、右边的都比它大，无论之后怎么递归，它都不用再动了。

很多人写快排出问题，十有八九是卡在这里：不是指针对撞弄错了，就是边界条件没想清楚，要么就是写出来的代码在数组里死循环，跑都跑不完。我自己的经验是，把 partition 这一环节彻底吃透，快排就成功了一大半。三种调整基准值位置的方法——hoare、挖坑、前后指针——本质上都是在回答同一个问题：怎么把基准值放到它该待的位置，同时保证划分正确。

先建立一个直观印象。假设你有一排身高不同的人，你随便拉一个人出来当基准，让所有比他矮的站到他左边，所有比他高的站到他右边。partition 干的就是这件事。至于这个“站队”的具体操作方式，hoare、挖坑、前后指针提供了三种不同的执行流程——它们在细节上各有取舍，但只要实现正确，最终结果都能保证划分正确，时间复杂度也都能达到 O(n log n) 的平均水平。

1.2 基准值选择：为什么这个环节直接决定效率

在深入三种方法之前，必须先把基准值的选法说清楚。快排的时间复杂度不是稳定 O(n log n)，它的平均情况确实是 O(n log n)，但最坏情况会退化到 O(n²)——这个退化通常就是因为基准值选得不巧。

举个例子，数组本身是[1, 2, 3, 4, 5, 6, 7]这种已经有序的情况。如果你的基准值只会取第一个元素，那每次划分都只能分出“空 + 剩下所有”，一共要递归 n 层，每层都要扫描一遍剩余数组，总复杂度自然是 O(n²)。这在有序数据量大的时候是灾难级的性能倒退。

所以常见的补救手段有三个：一是随机选基准值，让最坏情况变成一个概率极低的随机事件；二是三数取中法，把首、中、尾三个元素排个序，取中间那个数当基准，这种办法对基本有序的数据特别友好；三是在工程实现里，当递归区间小到一定程度（比如小于16个元素）直接改用插入排序，这属于优化层面的技巧。

下面讲到三种 partition 方法时，我会统一用“取区间第一个元素作为基准值”来演示，因为这样最直观、最好理解。但代码注释里我会写清楚怎么替换成随机基准值或三数取中，等你看懂了基本逻辑再升级也不迟。

2. 三种调整基准值的方法逐个拆解

2.1 hoare 版本：左右双指针交换，最经典的祖师爷写法

hoare 版本是快排发明者最初提出的方法，思路非常朴素：两个指针，一个从头往右走，一个从尾往左走，找到一个左边比基准大的，再找一个右边比基准小的，然后把它们俩交换，直到两个指针撞上为止。

你可能要问了：交换完之后，基准值怎么归位？

答案是：最后把基准值和相遇位置的值交换。所以 hoare 全程基准值一直待在原地没动，等划分结束，它才挪到正确的位置上。

用一个具体例子走一遍。假设数组是 [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]，基准值选第一个元素 6，left从 1 开始往右找比 6 大的，right从 9 开始往左找比 6 小的。

• left找到 7（下标3），right找到 5（下标7），交换 → 序列变成 [6, 1, 2, 5, 9, 3, 4, 7, 10, 8]。
• 继续移动，left找到 9（下标4），right找到 4（下标6），交换 → [6, 1, 2, 5, 4, 3, 9, 7, 10, 8]。
• 继续移动，left停在 9（下标6），right继续左移，走到下标5的 3，再走到下标4的 4，此时left和right交叉或者相遇，循环结束。

最终基准值 6 和right指向的位置交换，得到 [3, 1, 2, 5, 4, 6, 9, 7, 10, 8]。左边全是比 6 小的，右边全是比 6 大的，划分成功。

这里有个极其重要的细节：必须让 right 先走。为什么？因为最后要保证相遇位置的值比基准值小（或相等），才能和基准值交换。如果 right 先走，它停下来的位置一定是“小于等于基准值”的位置；如果 left 先走，就可能停在比基准值大的位置，交换之后基准值左边就会出现一个比它大的元素，划分就错了。

提示：很多讲解快排的教程里会把这一步忽略掉，但你实际写代码时一旦顺序反了，跑出来的结果就会在某些用例上莫名出错。这不是玄学，是循环不变量的逻辑必然。

hoare 版本的代码模板我写在这里，注释里标注了每一步的用意：

int Partition_Hoare(int arr[], int left, int right) { int keyIndex = left; // 基准值所在下标，全程先不动 int key = arr[left]; while (left < right) { // 注意顺序：先让right走，找小的 while (left < right && arr[right] >= key) right--; // 再让left走，找大的 while (left < right && arr[left] <= key) left++; // 两者都停下来了，交换 Swap(&arr[left], &arr[right]); } // 相遇位置和基准值交换 Swap(&arr[keyIndex], &arr[left]); return left; // 返回基准值现在的位置 }

注意内层循环的判断条件里都必须带上left < right，否则指针可能跑出数组边界，或者越过对方继续走，直接越界崩溃。边界处理是这一段的重点，我后面会在常见问题部分专门展开。

2.2 挖坑版本：把基准值先拿出来，空位逐步填平

挖坑法的思路比 hoare 更直观一点。核心思想是：先把基准值保存到一个临时变量里，它原来的位置就当成了一个“坑”。然后另一个指针从右侧往左找比基准值小的数，找到后直接填到坑里；空出新位置后，左侧指针再从左边往右找比基准值大的数，填到右侧那个新坑；如此反复，两个坑逐渐往中间逼近，最终两个指针相遇时，把基准值放上去。

还是用 [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 走一遍。先把arr[0] = 6取出来存进变量 key，于是数组下标0的位置就空出来了，这就是第一个坑。

• right从右往左找比 6 小的数，找到 5（下标7），把 5 填到下标0的坑里。此时下标7反而空了。
• left从左往右找比 6 大的数，找到 7（下标3），把它填到下标7的坑里，下标3空了。
• right继续从下标6往左找，找到 3（下标5），填到下标3的坑，下标5空了。
• left从下标4往右走，走到下标5时left == right，循环停止。
• 把 key = 6 放到下标5，划分结束。

挖坑法有个很舒服的点：它不需要最后一步的交换操作，因为基准值是被单独保存的，填来填去不会覆盖到基准值本身。但代价是逻辑上要多一个“坑”的概念，代码里的赋值操作要比 hoare 多一些，不过理解和调试都更容易。

int Partition_Hole(int arr[], int left, int right) { int key = arr[left]; // 先取出基准值，形成坑 int hole = left; // hole 指向当前坑的位置 while (left < right) { // 右侧找小，填到坑里 while (left < right && arr[right] >= key) right--; arr[hole] = arr[right]; hole = right; // 左侧找大，填到新坑里 while (left < right && arr[left] <= key) left++; arr[hole] = arr[left]; hole = left; } // 两个指针相遇，把基准值放回坑中 arr[hole] = key; return hole; }

这里有个不易察觉的细节：值相等的元素不需要交换位置，所以循环条件里用的是>=和<=。假如把>=写成>，当数组里有很多重复值的时候，指针会在相等的元素之间来回折腾，严重时还会死循环或者产生极不平衡的划分。

同值的处理同样适用于 hoare 版本，这也是我见过的很多实现出错的高频原因之一。

2.3 前后指针版本：一对前后跟随的指针，最优雅的现代写法

前后指针法的思路是完全不同的。它不再用“左右夹逼”的方式，而是用两个指针一前一后同时在数组里向右走：一个指向最近一个已经放好的“小于等于基准值”的区域边界，另一个负责扫描。

具体说就是定义prev和cur两个指针，初始时prev = left（基准值所在位置），cur = prev + 1。cur往右走，每碰到一个比基准值小的元素，就让它和prev + 1位置的元素交换，然后prev前进一步；如果碰到不小于基准值的元素，cur继续走，prev不动。扫描结束后，prev停的位置就是“最后一个小于等于基准值”的位置，把基准值和prev位置交换即可。

用 [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 再走一遍。prev = 0，cur = 1：

• arr[cur] = 1，小于6。交换arr[prev+1]和arr[cur]，即交换 arr[1] 和 arr[1]，prev = 1，cur = 2。
• arr[cur] = 2，小于6，交换 arr[2] 和 arr[2]，prev = 2，cur = 3。
• arr[cur] = 7，不小于6，prev不动，cur = 4。
• arr[cur] = 9，不小于6，继续走，cur = 5。
• arr[cur] = 3，小于6，交换 arr[3] 和 arr[5] → [6, 1, 2, 3, 9, 7, 4, 5, 10, 8]，prev = 3，cur = 6。
• 继续扫描，4（下标6）与 arr[4] 交换 → [6, 1, 2, 3, 4, 7, 9, 5, 10, 8]，prev = 4。
• 5（下标7）与 arr[5] 交换 → [6, 1, 2, 3, 4, 5, 9, 7, 10, 8]，prev = 5。
• 最终把基准值 6 和 arr[5] 交换 → [5, 1, 2, 3, 4, 6, 9, 7, 10, 8]。

这里最巧妙的地方是：虽然交换次数不一定比前面两种方法少，但逻辑结构极其干净，尤其适合用来处理链表排序之类的场景，因为它的交换只涉及相邻位置之间的搬运，不需要像 hoare 那样记住一堆下标。

int Partition_Pointer(int arr[], int left, int right) { int key = arr[left]; int prev = left; int cur = left + 1; while (cur <= right) { // 遇到比基准小的，就放到prev的后面 if (arr[cur] < key && ++prev != cur) Swap(&arr[prev], &arr[cur]); cur++; } // 把所有比基准小的值都放到了左边，最后把基准换过去 Swap(&arr[left], &arr[prev]); return prev; }

注意这里判断条件里用了++prev != cur这个技巧：当prev加一后恰好等于cur，说明元素本来就在正确的位置上，没必要自己跟自己交换，直接跳过。如果不加这个判断，也能跑，只是会多做很多无意义交换，而且代码看起来不够干脆。

我自己的经验是，前后指针版本是最容易写对、也最好解释的版本，面试时如果时间紧张，直接用这个最快。

3. 完整实现代码与随机化优化

3.1 全套可运行代码：hoare + 递归主逻辑

三种 partition 方法讲完，肯定有人想直接跑起来看效果。下面给一份配合 hoare 划分的完整快速排序代码，把递归调用和交换函数都补齐。你只要把这段代码原样复制到你的编译环境里，就能看到排序结果。

#include <stdio.h> void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int Partition_Hoare(int arr[], int left, int right) { int keyIndex = left; int key = arr[left]; while (left < right) { while (left < right && arr[right] >= key) right--; while (left < right && arr[left] <= key) left++; Swap(&arr[left], &arr[right]); } Swap(&arr[keyIndex], &arr[left]); return left; } void QuickSort(int arr[], int left, int right) { if (left >= right) // 区间为空或只有一个元素，无需排序 return; int keyIndex = Partition_Hoare(arr, left, right); // 基准值已经定位，分别对左右两侧继续递归 QuickSort(arr, left, keyIndex - 1); QuickSort(arr, keyIndex + 1, right); } int main() { int arr[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, n - 1); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

这里有一个至关重要的点：递归处理子区间时，范围是[left, keyIndex-1]和[keyIndex+1, right]，而不是包含keyIndex。因为基准值在 partition 结束时已经放在了最终位置，不需要、也不能再参与后续排序。新手最常见的错误就是把边界写成了[left, keyIndex]，结果基准值反复参与划分，递归永远不会收敛，轻则排序错误，重则栈溢出。

注意：上面递归里的返回条件left >= right覆盖了两种情况：区间只有一个元素（left == right）和区间为空（left > right）。如果只写left == right，空区间会漏处理，后面递归调用就可能传入 left > right 的参数，然后继续往里走，直接越界。

3.2 随机化基准值和三数取中：彻底消灭最坏情况的隐患

前面说过，固定选第一个元素当基准值在有序数组上会退化到 O(n²)。解决办法很简单，但很多人没意识到它在工程上的重要程度——只改一行代码，就能把最坏情况从“必现”变成“几乎不可能发生”。

随机化的思路是：在 partition 之前，随机选一个区间内的下标，把该位置的元素和第一个元素交换，然后继续使用原来的划分逻辑。这样基准值就变成了随机值，即使输入是最坏情况，也不会每次都倒霉地选中同一个位置的元素。

void QuickSort_WithRandom(int arr[], int left, int right) { if (left >= right) return; // 随机选基准值：将随机位置的元素交换到最左边 int randomIndex = left + rand() % (right - left + 1); Swap(&arr[left], &arr[randomIndex]); int keyIndex = Partition_Hoare(arr, left, right); QuickSort_WithRandom(arr, left, keyIndex - 1); QuickSort_WithRandom(arr, keyIndex + 1, right); }

用的时候记得在 main 里先调srand((unsigned)time(NULL))。

三数取中的思路更可控：取left、mid、right三个位置上的元素，找到它们中间大小的那个，放到left位置作为基准值。它对基本有序的数据特别有效，因为排序后的数组首、中、尾三个数中，中间值基本上接近整个区间的中位数，能保证划分不会极度失衡。

int GetMidIndex(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]); // 此时 arr[left] <= arr[mid] <= arr[right]，取 mid 作为基准值 return mid; } void QuickSort_Mid(int arr[], int left, int right) { if (left >= right) return; int mid = GetMidIndex(arr, left, right); Swap(&arr[left], &arr[mid]); int keyIndex = Partition_Pointer(arr, left, right); QuickSort_Mid(arr, left, keyIndex - 1); QuickSort_Mid(arr, keyIndex + 1, right); }

4. 三种方法的核心差异与场景选择

4.1 三种 partition 方法的对照表

三种方法讲了那么多，是时候汇总成一个表，方便对比记忆了。我把它们的关键特征整理一下：

从执行效率上看，hoare 的平均交换次数最少，因为它的交换是“跨越式”的，一次交换能把一个大的挪到后面、一个小的挪到前面；挖坑法是单边填坑，其实每次填坑也算一次搬运，整体不比 hoare 少；前后指针是逐步“挤”小数，每一步可能只有一次交换，但元素位移的总量级仍然是 O(n)。

不过说实话，这种常数级别的差异在普通数据量下根本感觉不出来。你有那个精力去抠这几个交换次数的细节，不如把精力放在防止递归栈溢出、处理重复元素这种真正影响正确性和健壮性的问题上。

4.2 面试和实际工程里到底该怎么选

这个问题从来没有标准答案，取决于你的场景。

• 面试场景：优先写前后指针版本。理由很现实：它的逻辑最短、最不容易出错，面试官一看就懂。挖坑版也常被用来做解释，因为“坑”的概念特别直观。hoare 版如果你能一口气写对，说明你对边界条件的理解确实到位，但这个版本在紧张状态下很容易写乱，不太建议作为首选。
• 教科书学习：建议三个版本都亲手实现一遍，并且用多种用例测试。我当年就是这么练的——光看不写很快就忘，写一遍、调试一遍、再对比一遍，三种方法的差异就刻在脑子里了。
• 工程实践：多数语言标准库里的排序并不是纯快排，而是混合排序（比如数据量小的时候转插入排序，数据量大的时候用快排配合堆排序兜底）。如果你自己实现排序，推荐用前后指针 + 三数取中 + 小区间插入排序的组合，这是公认最容易维持效率和稳定性平衡的方案。
• 链表场景：前后指针版本天然适合，因为它只用交换值，不需要回溯指针，单链表也能操作。

5. 常见问题、边界条件与调试建议

5.1 死循环和越界：快排写挂的三大元凶

第一个元凶是指针越界。内层循环的while (left < right && arr[right] >= key)里，那个left < right条件漏写的话，如果整个数组里所有元素都比基准值大，右指针会一直往左走到数组开头，甚至越过left，直接访问负数下标，当场崩溃。左指针同理，可能一路跑到数组末尾之外。

第二个元凶是死循环。当数组里出现大量等于基准值的元素，比如 [5, 5, 5, 5, 5]，如果内层循环用的是>而不是>=，右指针和左指针都不会移动，然后外层循环里的交换变成了自己跟自己换，left和right永远撞不上，程序就在那里空转。用>=和<=保证指针在遇到相等元素时能继续前进，是避免这种情况的关键。

第三个元凶是递归边界没兜住。partition 返回的位置如果处理不当，比如递归传了[left, keyIndex]，基准值永远在子区间里，递归深度会越来越离谱。尤其是当数组已经有序且基准值固定取第一个时，递归深度会直接到 n——这不只是性能差的问题，是栈溢出崩溃的问题。

我自己调试快排时有个习惯：先用小数组、多用例测，特别是测这三种用例——完全有序数组、完全逆序数组、全部相等的数组。这三种极端情况能把绝大多数边界问题暴露出来。只要这三关过了，再测随机数组基本就没问题了。

5.2 递归深度、栈空间与算法稳定性

快排是递归算法，每层递归都会在系统栈上占用空间。平均情况下递归深度是 O(log n)，4 亿个元素也就 30 层不到；但最坏情况下递归深度是 O(n)，如果你在一个 10 万级别的逆序数组上用固定取首元素的 hoare，栈直接就可能爆掉。

这就是为什么几乎所有的教科书都会强调随机化基准值的重要性——它不只是“优化性能”，更是“保证不崩溃”。工程实现里普遍还会配合一个兜底方案：如果递归深度超过某一个阈值（比如 2 倍 log n），就改用堆排序把剩余区间排掉。这个方案就是著名的“内省排序”，很多标准库排序的实现思路都基于此。

另外注意，快速排序是不稳定排序。所谓不稳定，指的是两个键值相等的元素，排序前后它们的相对位置可能发生变化。比如一个按照“先按成绩、再按姓名”排好的数据，如果你只按成绩重新排序，成绩相同的人，姓氏先后顺序可能被打乱。如果需要稳定性，就应该选归并排序或者给每个元素额外带上一个序号索引，而不是强行用快排。

5.3 不用递归：用显式栈实现快速排序

有时候你不想冒着递归栈溢出的风险，或者你正在写的是嵌入式环境，系统栈特别小，那就得用显式栈来模拟递归。

思路不复杂：把递归函数里的每一次“待处理区间”压入一个栈，然后循环弹出处理。用第一次递归调用作为例子：原本是把[left, right]划分成[left, keyIndex-1]和[keyIndex+1, right]两个子任务——现在不调用函数，而是把这两个区间先后压入栈，然后循环弹出栈顶区间做同样的处理，直到栈为空。

void QuickSort_Stack(int arr[], int left, int right) { if (left >= right) return; int stack[100][2]; // 简单示例：假定数据量不超过栈容量 int top = 0; // 初始区间入栈 stack[top][0] = left; stack[top][1] = right; top++; while (top > 0) { // 弹出一个区间 top--; int l = stack[top][0]; int r = stack[top][1]; if (l >= r) continue; int keyIndex = Partition_Pointer(arr, l, r); // 先压右区间，再压左区间（顺序任意，栈会倒序处理） stack[top][0] = l; stack[top][1] = keyIndex - 1; top++; stack[top][0] = keyIndex + 1; stack[top][1] = r; top++; } }

写这段代码时有个小技巧：每次压栈之前先判断区间长度是否大于 1，否则会压入大量空区间，白白增加循环次数。上面代码用if (l >= r) continue;在弹出时兜了一次底，这样也能省去多余的压栈操作。

5.4 复杂度分析和重复元素的特殊处理

快速排序的平均时间复杂度是 O(n log n)，最坏是 O(n²)；空间复杂度平均 O(log n)，最坏 O(n)。这个最坏情况的空间复杂度其实也就是递归深度那一层层的栈帧。

如果是重复元素特别多的数组，比如大量 0 和 1 混合的情况，普通快排仍然会被“等值元素”困扰：虽然用>=和<=能保证指针移动，但划分依然可能非常不平衡。这时候更适合用三分法——把数组划分为“小于基准值”“等于基准值”“大于基准值”三个区域。这样所有等于基准值的元素一次到位，两边递归只处理小于/大于区域，在重复元素多的场景下效率提升非常明显。

三分法的实现比三分 partition 稍微复杂一点，但思路仍然是“基准值先选出来，然后两个指针往中间夹，遇到相等元素就累积在中间区”，有兴趣的可以自己尝试写一版，这里不展开。

回到最开头说的那句话：快排的难点不在“快”，而在“边界”——尤其是三种 partition 方法各自的边界条件。hoare 的右指针先走、挖坑法的坑位更新、前后指针的 prev/cur 交换条件，每一个拿出来都值得单独调试几遍。我个人最推荐的做法是：先把前后指针版本练到闭着眼能写对，再回头对比 hoare 和挖坑的差异，这样循序渐进，比一上来就三种一起啃要舒服得多。排序这东西，看十遍不如写一遍，写完再跑一跑极端用例，你才算真正掌握。