从2010年408真题看快速排序：手推一趟划分的避坑指南

如果你翻过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为基准写出进行一趟快速排序之后的序列。先明确下标序列长度为8low指向下标0high指向下标7pivot取a[0] 49。3.2 挖坑法六步完整推演第一步右指针往左找小于49的元素。从high7开始a[7] 49它等于pivot不满足“小于49”的条件继续左移。a[6] 2727小于49停。把27填入low指向的坑也就是下标0的位置。此时序列变成[ 27, 38, 65, 97, 76, 13, 27, 49 ]下标6的位置变成了新坑high停留在6。第二步左指针往右找大于49的元素。从low0开始a[1] 38不大于49继续右移。a[2] 6565大于49停。把65填入high指向的坑也就是下标6的位置。此时序列变成[ 27, 38, 65, 97, 76, 13, 65, 49 ]下标2的位置变成了新坑low停留在2。第三步右指针往左找小于49的元素。从high6开始a[5] 1313小于49停。把13填入下标2的坑。此时序列变成[ 27, 38, 13, 97, 76, 13, 65, 49 ]下标5变成新坑high停留在5。第四步左指针往右找大于49的元素。从low2开始a[3] 9797大于49停。把97填入下标5的坑。此时序列变成[ 27, 38, 13, 97, 76, 97, 65, 49 ]下标3变成新坑low停留在3。第五步右指针继续往左找小于49的元素。high从5开始左移a[4] 7676大于49继续a[3] 9797也大于49继续。此时high移动到3low也是3两个指针相遇循环结束。第六步回填pivot。把基准49填入low和high相遇的位置也就是下标3。最终一趟快排后的序列为[ 27, 38, 13, 49, 76, 97, 65, 49 ]我把每一步的状态整理成一张表方便你对照检查步骤操作当前序列lowhigh初始取pivot4949, 38, 65, 97, 76, 13, 27, 49071high左移27填入下标027, 38, 65, 97, 76, 13, 27, 49062low右移65填入下标627, 38, 65, 97, 76, 13, 65, 49263high左移13填入下标227, 38, 13, 97, 76, 13, 65, 49254low右移97填入下标527, 38, 13, 97, 76, 97, 65, 49355指针相遇于下标327, 38, 13, 97, 76, 97, 65, 49336回填pivot到下标327, 38, 13, 49, 76, 97, 65, 49333.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的边界条件、等号方向、指针移动语句。我前面为什么反复强调等号和lowhigh因为这就是出题人的固定考点。第三类是综合应用。比如在长度为n的数组里查找第k大元素要求平均时间复杂度O(n)或者用快排思想把数组分成“小于基准、等于基准、大于基准”三部分。这些都建立在你能熟练写出partition的基础上。6.2 最后一个月怎么复习快排我的建议是三遍法。第一遍不看任何资料手推两个序列的全部排序过程推完对照教材检查每一趟序列是否正确第二遍闭卷写完整快排代码写完用几组边界数据测比如空数组、单元素数组、全部相等的数组第三遍把复杂度和稳定性背下来同时把快排和堆排序、归并排序的代码对比着记防止混淆。如果你用的是严蔚敏教材重点看7.4节快排的代码如果你用王道重点刷课后选择题中“排序过程模拟”部分。湖科大教书的课程我看过讲得细适合第一轮打基础但到了强化阶段一定要自己动手推不能只看课。再多说一句408真题里排序题不是考算法多花哨而是考你在有限时间里手稳不稳。你要是能像条件反射一样写出那个partition循环这类题就再也不会成为你的失分点。我个人当年复习时做2010年这类“一趟快排结果”题也栽过跟头——第一次手推时我把等于基准的第二个49放到了基准左边结果和所有选项都对不上。后来我把所有“某趟结果判断”类题目统一用“基准最终位置检查法”来验证再也没有错过。最后送大家一个小习惯每次推完一趟划分先别急着对答案自己问一句“基准现在在不在它最终该在的位置”这一个问题能帮你排查掉九成的手误。