2010年408统考数据结构第10题一道看似不起眼的选择题当年实打实坑了不少考生。题目给了一组数据2121688510再给出前三趟排序结果让你判断采用的是哪种排序方法。四个选项里有冒泡、希尔、归并和快速排序标准答案是冒泡排序但很多同学第一反应是为什么不是快速排序每趟明明都确定了一个元素的最终位置这不是很像快排吗后来我把这道题翻来覆去研究了很久才发现它真正考的不是“你会不会排序”而是你对每种排序算法“每一趟”产生的过程特征有没有透理解尤其是快速排序——它以谁为基准408默认实现怎么写一趟划分之后序列到底会发生什么变化。这篇文章就把这道题从题干到选项完整拆开顺带把408里快速排序的原理、边界、代码模板和常见坑全部串一遍。考研党、准备期末考或者单纯想把排序算法搞明白的人都可以对着这篇过一遍。1. 2010年第10题到底长什么样1.1 原题与答案原题内容如下对一组数据2121688510进行排序若前三趟排序结果如下第一趟排序结果2121651088第二趟排序结果2125101688第三趟排序结果2510121688则采用的排序方法可能是 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序这道题的正确答案是A起泡排序也就是我们常说的冒泡排序。题目里“可能”两个字很关键意思是只要某个选项能合理解释这三趟结果它就可以是答案而在四个选项中唯一能做到逐趟严格吻合的只有冒泡排序。1.2 题目在考什么排序过程的特征判别这道题在408大纲里的位置很明确属于“数据结构——排序”章节考查的是排序算法过程辨析。408对排序的要求不仅仅是会写代码、会背复杂度更要求你能根据排序过程中的中间结果反推算法或者判断某趟结果属于哪一种排序。很多同学复习排序时只背结论比如“快排平均O(n log n)、不稳定”“堆排序最坏也是O(n log n)”之类的这些当然要背但遇到这种把过程摆在你面前的题光背结论是不够的。你需要知道每种排序每一趟操作之后会留下什么样的“痕迹”谁到了最终位置、哪些区域开始有序、元素是相邻交换还是跳跃移动、有序段长度是怎么增长的。这道题就是把“痕迹识别”考到了极致。1.3 为什么答案偏偏是冒泡而不是快速排序这是整道题最核心的迷惑点。D选项快速排序之所以是最大的干扰项是因为从结果表面看每一趟确实似乎有一个元素“固定”到最终位置第一趟88到了末尾第二趟16到了倒数第二个位置第三趟12到位。这和“快排每趟确定一个枢轴元素的最终位置”的表面特征很像。但注意408默认的快速排序实现是严蔚敏教材里的“挖坑法”基准取当前区间的第一个元素。题给序列2121688510第一趟如果以2为枢轴2已经是全局最小一趟划分后序列根本不会变不可能得到2121651088。这个“默认基准取首元素”的前提正是排掉D选项的关键也是很多考生做错这道题的根源。后面我会详细展开。2. 冒泡排序三趟逐元素模拟这题最直接的解法2.1 第一趟88如何被一步步“冒”到最后冒泡排序的核心是相邻元素两两比较前面大于后面就交换一趟下来当前待排区间里最大的元素会像气泡一样浮到区间末尾。我们按这个规则完整走一遍第一趟。初始序列是2121688510比较2和122小于12不交换比较12和1612小于16不交换比较16和8816小于88不交换比较88和588大于5交换序列变为2121658810比较88和1088大于10交换序列变为2121651088。第一趟结束最大的88被“冒”到了序列末尾待排区间变成前5个元素。这个结果和题目给的第一趟完全一致。这里有个细节值得注意88原本在第4个位置按冒泡排序的规则它只和相邻元素逐个交换一步一步往后走并不会发生跳跃式移动。观察题给的第一趟结果88从第4位移到第6位5和10分别向前挪了一位这正是相邻交换的典型痕迹。2.2 第二趟16在倒数第二个位置落定第二趟的操作范围是前5个元素2121651088已经排好不再参与比较比较2和122小于12不交换比较12和1612小于16不交换比较16和516大于5交换序列变为21251610比较16和1016大于10交换序列变为21251016。整个序列最终是2125101688。这一趟确定的是当前区间最大值16的位置它落在整个序列的倒数第二位和题目给的第二趟结果完全一致。从这里可以看出冒泡排序的一个过程特征每一趟结束待排区间的“尾部”就会多一个已经就位的最大元素。第一趟定88第二趟定16第三趟就轮到12有点像从后往前一点点把序列“焊死”。2.3 第三趟12就位剩下来的全有序第三趟的操作范围继续缩到前4个元素212510比较2和122小于12不交换比较12和512大于5交换序列变为251210比较12和1012大于10交换序列变为251012。整个序列变成2510121688完全有序。这一趟确定的是12的位置此时6个元素里已经有88、16、12三个元素被冒泡确定了最终位置。题目给的第三趟结果和这个完全吻合。三趟冒泡下来每一趟都能完美解释题干给出的结果没有一步多余也没有一步冲突。这就是为什么A选项是这道题的不二之选。做这类题当你发现某个选项能对过程结果逐趟解释时基本就可以锁定答案了再去反复揣摩其他选项反而浪费时间。3. 三个干扰项的排除每一处都有说头3.1 二路归并的第一趟痕迹两两归并而不是跨组交换二路归并排序每一趟做的事情是把若干个已经有序的短序列两两合并成更长的有序序列第一趟通常是把相邻的每两个元素分别归并成一个有序对。拿原始序列2121688510来看相邻的两个元素组成的三个小组分别是212、1688、510。巧的是这三个小组本身就已经满足升序所以第一趟二路归并之后序列应该原封不动还是2121688510。但题目给的第一趟结果是212165108888跑到了最后5和10跑到了中间这说明发生了跨组元素交换。二路归并的一个硬性特征是第一趟归并时第3、4个元素组成的组和第5、6个元素组成的组是互相独立的它们之间不会有元素交换。题目结果里88和5、10明显发生了跨组移动所以C选项在第一趟就被排除了。这里不需要看第二趟、第三趟一步就够。3.2 希尔排序没有给增量怎么从结果看出不对劲希尔排序的特征是按照某个增量dk把序列分成若干子序列分别对每个子序列做直接插入排序然后缩小增量继续。做这道题时题目并没有明确给出增量序列所以理论上我们无法用“第一趟结果一定等于某个确定值”来直接归谬B选项。但我们可以试几个最常见的增量看看第一趟大概会变成什么样。比如dk2时位置1、3、5是一组2165位置2、4、6是一组128810组内直接插入排序后整体变为2105121688和题给的第一趟结果不一致dk3时位置1、4一组288位置2、5一组125位置3、6一组1610排序后得到2510881216也不一致。这里要说明一个做题策略选择题的“排除”不一定要求你在逻辑上证明一个选项“绝对不可能”而是要在四个选项里选一个解释力最强、最符合题目条件的最优项。希尔排序的增量没有给定它的结果本身就是一个无法唯一确定的东西而冒泡排序可以逐趟完美匹配这种情况下选A是没有争议的。3.3 快速排序被排除的真正前提枢轴取首元素D选项为什么不能选这是这道题的灵魂。很多人会觉得快速排序每一趟都让一个基准元素到达最终位置题目给的三趟结果似乎也能凑出来比如第一趟让88当基准第二趟让16当基准第三趟让12当基准好像真的可以。但这个思路忽略了一个大前提408统考默认采用严蔚敏数据结构教材中的快速排序实现也就是“挖坑法”并且默认取当前待排区间的第一个元素作为枢轴。在这个前提下第一趟对2121688510进行划分枢轴是2从右往左寻找比2小的元素结果12、16、88、5、10全部大于2一个都找不到于是枢轴2落在原位整个序列原样不变。换句话说按408默认快排实现题给序列的第一趟结果必须是2121688510而题干写的是2121651088这两者直接矛盾。所以D选项在第一趟就被排除了。这也是为什么这道题的标题挂着“快速排序”——它考察的恰恰是你对快排默认实现的理解是否准确而不只是知道“快排很快”。4. 快速排序一趟划分的完整原理与争议点4.1 从严蔚敏经典案例看懂挖坑法要理解前面说的“挖坑法”最好的例子就是严蔚敏教材上的经典序列49386597761327。我们以第一个元素49为枢轴完整走一遍一趟划分。先把49暂存到一个变量pivot里此时序列第一个位置相当于一个“坑”。然后high指针从右往左找比49小的元素找到27把它填到左边的坑里接着low指针从左往右找比49大的元素找到65把它挪到右边刚才空出来的位置继续high指针往左找比49小的找到13填到左边low指针再往右找比49大的找到97挪到右边。最后low和high相遇把暂存的49放回这个位置。一趟划分结束序列变成27381349769765。可以看到49到达了它在有序序列中的最终位置它左边的27、38、13都小于49右边的76、97、65都大于49。这就是一趟快速排序的完整效果从宏观上看序列被枢轴劈成左右两半枢轴本身就地不动了。4.2 首元素作枢轴时题给序列为什么过不了第一趟现在把同样的逻辑套到题给序列2121688510上。假设采用408默认的“首元素作为枢轴”第一趟划分的完整过程是这样的pivot暂存2low指向第1个位置high指向第6个位置high从右往左寻找比2小的元素10、5、88、16、12全部大于2high一路走到和low重合都无法找到循环结束把pivot即2放回第1个位置。整个过程没有发生任何元素移动序列依然是2121688510。这里的关键是2本身就是整个序列的最小值往右所有的元素都比它大所以一趟划分结束后2注定留在原地其余元素顺序也原封不动。题干第一趟给的结果却是88跑到了末尾这在默认枢轴取首元素的快排实现里是不可能发生的。D选项就是在这一步被淘汰的。4.3 如果枢轴能随便选D选项还成立吗这一节回答很多同学心里的一个疑问我要是让第一趟以88为枢轴是不是就能得到题给结果了可以做一个小实验第一趟选88作枢轴所有元素都在88左边一趟后88到末尾得到2121651088 第二趟对左区间21216510选16作枢轴得到2125101688 第三趟对212510选12作枢轴得到2510121688。这样看快速排序确实也能解释题干给的三趟结果。这正是网上这道题偶尔会引发争论的原因。但问题是408考试默认的快排就是严蔚敏版枢轴取首元素不给你“随便选枢轴”的自由。你一旦理解了这道题默认实现的前提就能明白为什么官方答案始终是A而不是D。这给我们备考提了个醒408的很多算法题都有隐含的教材语境。复习时最好以王道和教材一致的处理方式为准不要自己脑补“如果换个基准会怎样”。换个基准的讨论适合你理解算法本质但不适合用来做官方真题。4.4 复杂度、稳定性与408常考结论快速排序在408里的高频考点除了过程辨析还有复杂度、稳定性和适用场景。时间复杂度方面平均情况是O(n log n)。理想情况下每次划分都能把序列均匀分成两半递归树高度为log n每层划分的总比较次数是O(n)所以总共是O(n log n)。最坏情况是O(n^2)典型场景就是序列已经基本有序、甚至完全有序同时默认选取第一个元素作枢轴这时候每次划分都极不平衡递归树退化成一条链比较次数接近n(n-1)...1。空间复杂度方面快排不是O(1)的原地排序它依赖于递归调用栈的深度。平均情况下栈深度是O(log n)最坏情况下退化成O(n)。这一点经常有人记错把快排的空间复杂度记成O(1)实际上只有堆排序、简单选择排序、冒泡排序这些才是O(1)。稳定性方面快速排序是不稳定的。一个很经典的例子是序列332以第一个3为枢轴一趟划分后两个3的相对位置会发生变化。原因很简单快排的划分是跳跃式的覆盖移动不是相邻交换相等元素的相对顺序无法保证。408常考的“不稳定排序”一共四个希尔排序、简单选择排序、快速排序、堆排序简称“快些选堆”可以连在一起记。5. 从一道题到一类题排序过程辨析的通用方法5.1 八大排序“每趟痕迹”对比表做完这道真题值得做一次横向总结。我把408常考的排序算法按“一趟之后你会看到什么”整理成一张表做题时直接对照它来认算法。排序算法每一趟后的典型痕迹是否稳定平均时间最坏时间额外空间直接插入排序序列前部逐渐有序新元素一个个插入稳定O(n^2)O(n^2)O(1)希尔排序按增量分组后组内元素有序组间交错不稳定约O(n^1.3)O(n^2)O(1)冒泡排序每趟把当前区间最大元素“冒”到尾部稳定O(n^2)O(n^2)O(1)快速排序枢轴一趟就位左小右大不稳定O(n log n)O(n^2)O(log n)简单选择排序每趟选出最小值放到前部不稳定O(n^2)O(n^2)O(1)堆排序每趟把当前堆顶换到末尾剩余重新调整不稳定O(n log n)O(n log n)O(1)二路归并排序每趟有序段长度翻倍两两归并稳定O(n log n)O(n log n)O(n)基数排序按关键字位逐位有序稳定O(d(nr))O(d(nr))O(r)这张表的核心不是背而是看“痕迹”。比如题目给了三趟结果你第一眼应该观察是不是尾部在逐步变成全局较大的元素如果是冒泡和堆排序都有可能再看移动方式是相邻交换还是堆顶交换来区分。是不是前面一部分变得有序、后面还没动那更像是插入排序。5.2 拿到一趟结果后的判断顺序做排序过程辨析题我建议按下面的顺序来判断能省很多时间先看第一趟结果里有没有“两两归并、有序段长度翻倍”的迹象有就优先考虑二路归并再看是不是从前往后前面逐渐有序像是不断插入新元素那是直接插入排序接着看每趟是不是都在向尾部“沉”一个当前最大元素是的话大概率是冒泡排序然后找一个“已经位于最终位置且左边都小、右边都大”的元素如果存在可能是快速排序一趟划分的结果最后考虑是不是每趟选最小放到前面的选择排序或者堆顶换到末尾的堆排序。这个判断顺序不一定每道题都完备但覆盖了408最常考的几个主要算法。实际操作中你只需要把每种排序第一趟的逻辑在草稿纸上快速核对一下如果选项里有一个能和题目给的每一趟严格对上基本就可以选它。5.3 常见变形考法枢轴判断、一趟结果归属围绕排序过程408还有两种很常见的变形考法。第一种是给你一趟快速排序后的结果反推枢轴是谁。比如某序列经过一趟快排后变成325798问你枢轴可能是哪个。答案是5因为5在最终有序位置并且它左边的3和2都小于5右边的7、9、8都大于5。这种题考察的本质上就是“一趟划分后枢轴就位、左小右大”这个性质值得熟练掌握。第二种是给出某个序列经过两趟排序之后的样子问它“不可能是”哪种排序方法。这种题比“可能是”更难因为你要去验证每个选项是否严格符合“两趟之后”的痕迹。我的经验是先找每趟强调的“硬性标志”比如归并排序两趟之后有序段的长度必须变成4的规模堆排序两趟之后尾部必须出现两个全局最大的元素等等硬性标志对不上就立刻排除。6. 408快速排序代码模板与边界处理6.1 递归实现的完整C代码408真题里偶尔会要求手写快速排序的核心代码或者是把快速排序作为工具用在某道算法大题里。这里给出一份最标准的递归实现和严蔚敏教材的风格一致建议直接背诵。int Partition(int A[], int low, int high) { int pivot A[low]; // 以当前区间第一个元素为枢轴408默认 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; // 返回枢轴最终位置 } 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); // 排序右半部分 } }调用方式一般是QuickSort(A, 0, n - 1)注意数组下标从0开始。如果你习惯严蔚敏教材里下标从1开始的写法把low初始化为1、high初始化为n即可整体逻辑不变。6.2 四个边界条件的记忆技巧快排代码看着短但边界条件特别容易出错。我总结成四句话每次默写代码时心里过一遍基本不会翻车。第一内层两个while循环里都必须带上low high这个判断防止指针越界。比如找右边比pivot小的元素时如果没有这个判断high可能会一路减到负去找左边比pivot大的元素时low可能一路加到超出区间。这个条件在每一层循环里都是“保护锁”。第二比较符号要用和不能只用和。这里的关键是“等于枢轴的元素怎么办”。如果用严格大于、小于当序列中存在大量等于pivot的元素时划分会非常不平衡极端情况下还可能死循环。用和把等于pivot的元素归到某一侧既能避免死循环也让划分更均衡。第三递归入口的判断条件是if (low high)不是if (low high)。因为当low等于high时区间里只剩下一个元素它天然就是有序的不需要再递归调用。写成会导致不必要的调用甚至造成无限递归。第四枢轴位置返回后左右区间的边界是pivotpos - 1和pivotpos 1枢轴本身已经就位不要再把它纳入后续排序。这个边界如果写错比如写成QuickSort(A, low, pivotpos)枢轴会被反复排进递归导致结果错误或者栈溢出。这四句话可以连成一个记忆链条指针要防越界、比较要带等号、递归只排一个元素以上、枢轴本身不再入队。默写代码时按这个顺序检查一遍快排代码基本就稳了。6.3 快速排序在真题中的其他高频考点除了代码题快排在408选择题里还有几个高频出题角度。最坏情况对应的初始序列特征是一个几乎必考的点。默认取第一个元素为枢轴时如果初始序列已经正序或逆序每趟划分都只能确定一个元素的位置递归退化成n层时间复杂度会达到O(n^2)。这一点要能和“堆排序最坏也是O(n log n)”区分开因为堆排序不怕顺序序列这一点常被拿来对比出题。另一个点是“一趟划分后序列中哪些元素一定就位”。一趟快排结束后只有枢轴元素一定在最终位置其他元素只是被分到了左右两个区间各自区间内部仍然是无序的。这一点可以出一种陷阱题问你某趟快排后有几个元素可能已经就位很多考生会把划分后“看起来位置对了”的元素也算进去结果踩坑。还有一种是性能对比题把快排、堆排序、归并排序放在一起考。比如问“平均情况下速度最快的内部排序算法是什么”答案就是快速排序问“最坏情况下表现仍然很好且稳定的排序算法”那就是归并排序问“哪些排序算法最坏情况下也能保持O(n log n)”那是堆排序和归并排序。这些结论和本章的过程辨析结合起来复习效果最好。我自己备考的时候做这类排序题有个习惯不管题目怎么问都在草稿纸上把每一趟过程亲手写一遍而不是只盯着选项猜。这个习惯看着笨但确实帮我解决了不少选择题也让我在快速排序的大题上几乎没有丢过分。这道2010年第10题就是最好的例子——你把冒泡那三趟在纸上走完把快排的默认前提想清楚答案几乎是自己从纸面上跳出来的。