如果你翻过408真题的排序部分，会发现快速排序几乎是选择题里的常驻嘉宾，2010年全国统考第10题就是典型代表。这类题看着简单，可我带过的学生里，能把“一趟划分”结果一次做对的不到一半。原因不是不懂原理，而是手推的时候被指针边界、等值元素、先动左还是先动右这些细节绊住了。今天就借这道真题，把快速排序从原理到手推、从代码到避坑完整过一遍，无论你是刚开始复习还是一轮强化结束，这篇都能帮你在排序选择题上少丢分。
1. 2010年真题考点定位：这道题到底在考什么
1.1 题型位置与考纲要求
2010年是全国计算机学科专业基础综合统考的第二个年头，数据结构部分的选择题第10题落在排序章节。题型是单项选择题，考法很直接：给一个初始关键字序列，让你判断“以第一个元素为基准，进行一趟快速排序后的结果”应该选哪一项。
搞清楚考纲要求很重要。408对排序这一章的要求不是“背结论”，而是“掌握基本思想、排序过程、时间复杂度和稳定性”。具体到快速排序，就是要做到三件事：第一，能手动模拟一趟划分过程；第二，能写出或者补全快排代码；第三，能说清楚最好、最坏、平均情况的时间复杂度以及为什么不稳定。很多同学复习排序爱背结论，选择题碰到模拟过程就现原形，这道10题就是用来筛掉“只看不练”的人的。
1.2 为什么快排是命题“钉子户”
排序算法那么多，为什么偏偏快排出镜率最高？道理很简单：冒泡、直接插入的过程太直观，推演起来不容易错；堆排序、归并排序的中间状态又太抽象，不适合出选择题。快速排序处在一个很微妙的位置——原理一听就懂，但手推一趟划分时到处都是坑，两个指针怎么移动、等值元素放哪边、基准最后落在哪个位置，稍微马虎就错。这种“看着会、推着错”的特性，决定了它是选择题的理想素材。
另外一个原因是，快排的思想可以被扩展出很多变式。比如利用一次划分求第k小元素、判断某个序列是快排第几趟的结果、补全partition函数缺失的代码等等。从2010年往后看，这些变式在408和各个院校的自命题里反复出现，所以吃透标准的一次划分过程，等于给这类题目都打了底。
2. 快速排序原理：先把“分治”掰开揉碎
2.1 一句话理解快排
快速排序做的事情可以压缩成一句话：选一个基准值，把比它小的放到左边，比它大的放到右边，然后对左右两个子区间重复同样的操作。
这个逻辑不陌生，跟整理书架很像。想象你面前有一排厚薄不一的书，你随手抽出一本当标准，让所有比它薄的书放到它左边，比它厚的放到它右边。做完这一步，那本“标准书”的位置就已经固定了——以后不管怎么整理，它都不会再挪地方。接下来只需要对左边那一堆和右边那一堆分别再抽一本标准书，重复同样的过程，直到每一堆都只剩一本书。
这里面藏着一个解所有“某趟快排结果”题的关键性质：一趟划分结束后，基准元素一定落在它最终该在的位置上。记住这句话，考场上能省下大量时间。
2.2 挖坑法和交换法到底什么区别
教材和网课里讲快排，会出现两套实现思路，一套叫挖坑法，一套叫交换法（也叫Hoare法）。408手推题目，我强烈建议你只用挖坑法，因为它每一步在干什么非常直观，不容易写乱。
挖坑法的过程是这样的：先把基准值pivot存到一个临时变量里，此时序列的第一个位置就是一个“坑”。然后从右往左找比pivot小的元素，找到就填到坑里，这个元素原来的位置变成新的坑；再从左往右找比pivot大的元素，找到就填到右边的坑里。两个指针交替往中间逼近，直到它们相遇，最后把pivot填进相遇的位置。
交换法则稍微不同：两个指针从两端出发，右指针找到比pivot小的、左指针找到比pivot大的，然后交换这两个元素，重复直到相遇，最后再把pivot换到相遇点。从最终效果看，两种方法得到的结果是一样的，但交换法的代码和手推容易把下标搞乱，所以在考场上我建议你固定用挖坑法。
提示：如果基准选的是第一个元素，那一定是右指针先动。因为第一个位置已经被挖成坑了，必须先从右边找一个元素来填，你要是先动左指针，那就是找一个比基准大的元素去填一个空的左边的坑，逻辑上完全不对。
2.3 等值元素与边界条件的底层逻辑
很多人搞不懂代码里为什么写>=和<=，而不是>和<。这背后其实是个很实际的问题：当序列里存在和基准相等的元素时，如果只写>，右指针遇到等于基准的元素会继续往前走吗？会停住吗？如果两边都停住，就进入了死循环。
标准教材代码里，右指针用a[high] >= pivot作为继续左移的条件，意思是“只要当前元素不小于基准，就继续往左找”，遇到等于基准的元素直接跨过去；左指针用a[low] <= pivot作为继续右移的条件，遇到等于基准的元素也直接跨过去。这样一来，等于基准的元素会被左右指针均匀地分到两侧，两个指针都会稳定地向中间移动，不会卡死。
这个细节在408代码填空题里经常出现。给你一段挖坑法代码，中间挖掉一两个条件，让你从选项里选，很多同学就凭感觉乱填，填完自己都不知道为什么。你现在理解了“为什么要写成大于等于而不是大于”，以后再遇到这种题，一眼就能看穿出题人想考什么。
3. 真题核心过程还原：一趟快速排序手把手推
3.1 题干典型形态与初始序列
2010年这道第10题，不同回忆版本里具体的关键字序列可能有细微出入，但考察逻辑完全一致。下面用王道和严蔚敏教材里最经典的序列来完整还原手推过程，你把这套方法掌握了，不管真题里换成什么数字都能照做。
给定初始序列：
[ 49, 38, 65, 97, 76, 13, 27, 49 ]
要求：以第一个元素49为基准，写出进行一趟快速排序之后的序列。
先明确下标：序列长度为8，low指向下标0，high指向下标7，pivot取a[0] = 49。
3.2 挖坑法六步完整推演
第一步：右指针往左找小于49的元素。
从high=7开始，a[7] = 49，它等于pivot，不满足“小于49”的条件，继续左移。a[6] = 27，27小于49，停。把27填入low指向的坑，也就是下标0的位置。此时序列变成：
[ 27, 38, 65, 97, 76, 13, 27, 49 ]
下标6的位置变成了新坑，high停留在6。
第二步：左指针往右找大于49的元素。
从low=0开始，a[1] = 38，不大于49，继续右移。a[2] = 65，65大于49，停。把65填入high指向的坑，也就是下标6的位置。此时序列变成：
[ 27, 38, 65, 97, 76, 13, 65, 49 ]
下标2的位置变成了新坑，low停留在2。
第三步：右指针往左找小于49的元素。
从high=6开始，a[5] = 13，13小于49，停。把13填入下标2的坑。此时序列变成：
[ 27, 38, 13, 97, 76, 13, 65, 49 ]
下标5变成新坑，high停留在5。
第四步：左指针往右找大于49的元素。
从low=2开始，a[3] = 97，97大于49，停。把97填入下标5的坑。此时序列变成：
[ 27, 38, 13, 97, 76, 97, 65, 49 ]
下标3变成新坑，low停留在3。
第五步：右指针继续往左找小于49的元素。
high从5开始左移，a[4] = 76，76大于49，继续；a[3] = 97，97也大于49，继续。此时high移动到3，low也是3，两个指针相遇，循环结束。
第六步：回填pivot。
把基准49填入low和high相遇的位置，也就是下标3。最终一趟快排后的序列为：
[ 27, 38, 13, 49, 76, 97, 65, 49 ]
我把每一步的状态整理成一张表，方便你对照检查：
| 步骤 | 操作 | 当前序列 | low | high |
|---|---|---|---|---|
| 初始 | 取pivot=49 | 49, 38, 65, 97, 76, 13, 27, 49 | 0 | 7 |
| 1 | high左移，27填入下标0 | 27, 38, 65, 97, 76, 13, 27, 49 | 0 | 6 |
| 2 | low右移，65填入下标6 | 27, 38, 65, 97, 76, 13, 65, 49 | 2 | 6 |
| 3 | high左移，13填入下标2 | 27, 38, 13, 97, 76, 13, 65, 49 | 2 | 5 |
| 4 | low右移，97填入下标5 | 27, 38, 13, 97, 76, 97, 65, 49 | 3 | 5 |
| 5 | 指针相遇于下标3 | 27, 38, 13, 97, 76, 97, 65, 49 | 3 | 3 |
| 6 | 回填pivot到下标3 | 27, 38, 13, 49, 76, 97, 65, 49 | 3 | 3 |
3.3 30秒验证法：如何快速检查答案
考场上你不会一步一步推六遍，也不需要在每个选项上都做完整手推。更快的方法是利用“基准最终位置”。
先把原始序列排好序看一遍：
[ 13, 27, 38, 49, 49, 65, 76, 97 ]
两个49中，无论哪个作为基准，一趟快排后基准49都应该停在最终位置——如果按稳定排序看，左49应该在排序后数组的第4个位置。所以一趟快排后的序列，第4位（下标3）必须是49。然后检查这个49左边的元素是不是都小于等于49，右边的元素是不是都大于等于49。
假设题目给你四个选项：
- A. 13, 27, 38, 49, 49, 65, 76, 97 —— 这已经整体有序，是完整排序结果，不是一趟快排；
- B. 27, 38, 13, 49, 76, 97, 65, 49 —— 下标3是49，左侧全小于49，右侧全大于等于49，是正确答案；
- C. 38, 49, 65, 97, 76, 13, 27, 49 —— 基准49在第2位，但排序后49不可能停在第2位，排除；
- D. 27, 38, 13, 76, 49, 97, 65, 49 —— 下标3不是49，排除。
这个验证法其实就是在用性质做题：一趟划分结束后，pivot一定落在最终位置，左侧全不大于它，右侧全不小于它。三个条件同时满足，基本就是正确答案。
4. 快速排序代码实现与“边界”记忆方法
4.1 C语言挖坑法标准实现
手推会了，代码也得能写。下面是408考试最常用的挖坑法C语言实现：
void QuickSort(int a[], int low, int high) { if (low < high) { int pivotpos = Partition(a, low, high); QuickSort(a, low, pivotpos - 1); QuickSort(a, pivotpos + 1, high); } } int Partition(int a[], int low, int high) { int pivot = a[low]; // 取第一个元素为基准 while (low < high) { while (low < high && a[high] >= pivot) { high--; // 右指针左移，跳过不小于基准的元素 } a[low] = a[high]; // 把小于基准的元素填到左边的坑 while (low < high && a[low] <= pivot) { low++; // 左指针右移，跳过不大于基准的元素 } a[high] = a[low]; // 把大于基准的元素填到右边的坑 } a[low] = pivot; // 基准回填到相遇位置 return low; // 返回基准最终位置 }注意循环条件里那个low < high是必须的。如果没有它，右指针在内层循环里可能一路减到比low还小，或者左指针一路加到越界。所有快排代码的边界错误，几乎都是因为漏写内层循环里的low < high。
再注意等号的方向：右指针用>=，左指针用<=。写成>和<在全是相同元素的序列里会死循环，这个我在2.3小节已经解释过，属于408期末或统考填空的高频陷阱。
4.2 为什么工程里的快排都不“标准”
你翻Java的Arrays.sort、C++的std::sort，表面看都叫快排，但实现方式和教材代码差别很大。原因是标准快排有两个致命弱点：第一，待排序序列接近有序时，时间复杂度会退化到O(n²)；第二，递归深度可能达到n，栈溢出风险高。
工程上的解法通常是三招：一是随机选基准，或者从首、中、尾三个位置取中间值当基准，避免每次选到最大或最小元素；二是当子区间长度小于某个阈值（比如16）时，改用插入排序，因为小规模数据插入排序的常数更小；三是用非递归的栈模拟代替递归，或者像C++的std::sort那样混合使用快排、堆排序和插入排序，最坏情况也能保持O(n log n)。
408考试不会要求你写这些变体，但理解它们的存在，能帮你更好地理解“为什么标准快排在有序序列上反而慢”这个经典考点。
4.3 快排思想的两个高频变式
变式一：求第k小元素。
利用partition的性质，每次划分后基准的位置就是它在有序序列中的最终位置。如果基准位置正好是k-1，那基准就是第k小元素；如果基准位置大于k-1，只需要在左半区间继续找；否则在右半区间找。平均时间复杂度是O(n)，这也是408综合题喜欢考的“快排思想扩展”。
int FindKth(int a[], int low, int high, int k) { if (low <= high) { int pos = Partition(a, low, high); if (pos == k - 1) { return a[pos]; } else if (pos > k - 1) { return FindKth(a, low, pos - 1, k); } else { return FindKth(a, pos + 1, high, k); } } return -1; }注意不要在递归里反复对全区间partition，那样复杂度会退化到O(n log n)甚至更高。这也是很多同学代码题拿不到满分的原因。
变式二：双轴快排。
Java的Arrays.sort对基本类型数组用的是双轴快排，选取两个基准，把序列分成三部分。这个了解一下就行，408不会要求手写。
5. 考场易错清单与复杂度速查
5.1 7个高频易错点
| 易错点 | 错误示范 | 正确理解 |
|---|---|---|
| 指针移动顺序 | 基准在左，却先动左指针 | 基准在第一个位置时，必须先动右指针 |
| 等号缺失 | 右指针用>而不是>= | 遇到相等元素会卡住，极端情况死循环 |
| 混淆“趟”的概念 | 以为一趟等于一层递归 | 408语境里一趟通常指一次完整partition |
| 忽视觉度稳定性 | 认为快排属于稳定排序 | 快排不稳定，等值元素可能互换位置 |
| 有序序列复杂度 | 以为有序时最快 | 每次基准都在极端位置，退化O(n²) |
| 递归深度判断 | 认为递归深度恒为log n | 最坏情况下递归深度等于n |
| 忽略返回位置 | 只写出排列结果，不写基准下标 | 综合题里经常需要返回基准最终位置 |
这里重点说一下“一趟”这个词。408题目里说“一趟快速排序”，几乎都是指“一次划分过程”，也就是partition执行完，基准落到最终位置。不是指递归树上同一层的所有划分。有的同学把“一趟”理解成“两个子区间分别又做了一次划分”，那结果就对不上了。考试时如果题干没有额外说明，默认一趟就是一次partition。
5.2 排序算法复杂度对照表
这张表建议你考前自己默写一遍，不要只看不写：
| 排序算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n)~O(n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
快速排序的空间复杂度记得分情况：平均情况下递归深度是log n，空间是O(log n)；最坏情况下递归深度是n，空间是O(n)。选择题如果只说“快排空间复杂度是O(1)”，那是错的，它把递归栈的空间忘了。
6. 从2010到冲刺阶段：快排还能怎么考
6.1 408高频变式总结
第一类是概念判断。比如给你一个序列的前三趟排序结果，让你判断它是什么排序方法；或者给你几个排序过程描述，问哪个不可能是快排的中间状态。这种题考的是“每一趟partition后至少有一个元素到最终位置”的性质。
第二类是代码补全。挖掉partition函数中的几个关键语句，让你从选项中选择。高频挖空点就是内层while的边界条件、等号方向、指针移动语句。我前面为什么反复强调等号和low<high，因为这就是出题人的固定考点。
第三类是综合应用。比如在长度为n的数组里查找第k大元素，要求平均时间复杂度O(n)；或者用快排思想把数组分成“小于基准、等于基准、大于基准”三部分。这些都建立在你能熟练写出partition的基础上。
6.2 最后一个月怎么复习快排
我的建议是三遍法。第一遍，不看任何资料，手推两个序列的全部排序过程，推完对照教材检查每一趟序列是否正确；第二遍，闭卷写完整快排代码，写完用几组边界数据测，比如空数组、单元素数组、全部相等的数组；第三遍，把复杂度和稳定性背下来，同时把快排和堆排序、归并排序的代码对比着记，防止混淆。
如果你用的是严蔚敏教材，重点看7.4节快排的代码；如果你用王道，重点刷课后选择题中“排序过程模拟”部分。湖科大教书的课程我看过，讲得细，适合第一轮打基础，但到了强化阶段，一定要自己动手推，不能只看课。
再多说一句，408真题里排序题不是考算法多花哨，而是考你在有限时间里手稳不稳。你要是能像条件反射一样写出那个partition循环，这类题就再也不会成为你的失分点。
我个人当年复习时，做2010年这类“一趟快排结果”题也栽过跟头——第一次手推时我把等于基准的第二个49放到了基准左边，结果和所有选项都对不上。后来我把所有“某趟结果判断”类题目统一用“基准最终位置检查法”来验证，再也没有错过。最后送大家一个小习惯：每次推完一趟划分，先别急着对答案，自己问一句“基准现在在不在它最终该在的位置”，这一个问题能帮你排查掉九成的手误。
