跳转至

408 高频考点精讲:排序算法(Internal Sorting Algorithms Comprehensive Analysis)

模块归属:数据结构 · 排序
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:13 次(2016~2025 年:2017#10、2017#11、2018#10、2019#7、2019#10、2020#11、2021#10、2021#42、2022#11、2023#10、2023#11、2025#10、2025#11)
  • 历年总考查频次:24 次
  • 出题形式:单项选择题高频密集考查(考查算法性质对比、中间状态识别、趟数判定、元素移动和比较极限分析等);综合应用大题深度考查(2021 年第 42 题以计数排序为载体,考查算法模拟、比较次数数学推导及稳定性改进)。
  • 命题特点:
  • 考频极高,考题覆盖几乎所有考年,属于数据结构微观考点中考查密度最大的一级重点。
  • 理论综合性极强:八大内部排序的时间复杂度(最好、最坏、平均)、空间复杂度、稳定性、存储结构敏感度(顺序存储对比链式存储)构成选择题的核心母题。
  • 过程动态推导:快速排序的枢轴定位及划分树、希尔排序的增量序列反推、基数排序的分配收集中间状态呈现递增考查趋势。
  • 极限分析及底层机理:比较次数、移动次数的极值差异(如简单选择排序在最坏情况下移动次数仅为 \(O(n)\)$ \text{,直接插入排序在基本有序时比较次数仅为} $\(O(n)\))是区分度极高的核心考向。
近十年考查年份分布:
2016   2017         2018    2019          2020    2021          2022    2023          2024   2025
 -     √ (#10,#11)  √ (#10) √ (#7,#10)    √ (#11) √ (#10,#42)   √ (#11) √ (#10,#11)   -      √ (#10,#11)

二、 具体考察内容

1. 内部排序理论体系及分类

1.1 排序稳定性严格数学定义

设待排序记录序列为 \(\{R_1, R_2, \dots, R_n\}\)$ \text{,其对应的关键字序列为} $\(\{K_1, K_2, \dots, K_n\}\)。
若在排序前的序列中,记录 \(R_i\)$ \text{领先于} $\(R_j\)$ \text{(即} $\(i < j\)$ \text{),且存在关键字相等的情况} $\(K_i = K_j\): * 稳定排序算法:若经过排序后,在输出序列中 \(R_i\)$ \text{仍必然领先于} $\(R_j\); * 不稳定排序算法:若经过排序后,在输出序列中可能出现 \(R_j\)$ \text{领先于} $\(R_i\) 的次序颠倒。

稳定性并非指算法执行时间的波动程度,而是指等键值记录在排序前后相对物理次序的保序性。

1.2 内部排序算法分类体系

内部排序指待排序记录全部存放在计算机内存中进行的排序过程。按照排序过程中依据的基本操作原理,内部排序算法划分为五大类别: 1. 插入类排序:直接插入排序、折半插入排序、希尔排序; 2. 交换类排序:冒泡排序、快速排序; 3. 选择类排序:简单选择排序、堆排序; 4. 归并类排序:二路归并排序、多路归并排序; 5. 分配类排序:基数排序、计数排序、桶排序。

1.3 八大内部排序算法全维度指标对比大表

算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性 每趟是否至少确定一个元素最终位置 比较次数是否与初始状态有关 移动次数是否与初始状态有关
直接插入排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定 否 有关 有关
折半插入排序 \(O(n \log_2 n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\)$ \text{ 稳定 否 无关(恒为} $\(O(n \log_2 n)\)) 有关
希尔排序 \(O(n^{1.3})\) \(O(n^2)\) \(O(n^{1.25} \sim n^{1.5})\) \(O(1)\) 不稳定 否 有关 有关
冒泡排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定 是(每趟确定极大/极小值) 有关 有关
快速排序 \(O(n \log_2 n)\) \(O(n^2)\) \(O(n \log_2 n)\) \(O(\log_2 n) \sim O(n)\) 不稳定 是(每趟确定枢轴位置) 有关 有关
简单选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\)$ \text{ 不稳定 是(每趟确定极值位置) 无关(恒为} $\(\frac{n(n-1)}{2}\)$ \text{) 有关(最坏仅} $\(3(n-1)\))
堆排序 \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(1)\) 不稳定 是(每趟堆顶元素归位) 有关 有关
二路归并排序 \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n \log_2 n)\) \(O(n)\) 稳定 否 有关(或实现无关) 无关(固定复制)
基数排序 \(O(d(n+r))\) \(O(d(n+r))\) \(O(d(n+r))\) \(O(r)\) 稳定 否 无关(无关键字间比较) 无关(按位分配收集)

2. 插入类排序算法深层机理

2.1 直接插入排序(Straight Insertion Sort)

  • 算法机理:将序列划分为“已排序”和“未排序”两个部分。初始时已排序部分仅包含第 1 个元素。此后依次取出未排序部分的第 \(i\)$ \text{个元素,在已排序子序列} $\(A[1 \dots i-1]\) 中从后向前寻找合适插入位置,移动大于该元素的记录,最后将该元素插入。
  • 哨兵机制:将下标 0 的位置设为暂存单元 A[0]。A[0] = A[i] 既充当暂存器,又起到“哨兵”作用。在内层循环中只需判定 A[j] > A[0],免去了每次判断下标是否越界(j >= 1)的操作。
  • 最好情况分析:待排序列呈正序排列。每趟只需与前驱元素比较 1 次,无需移动任何元素。 $$ \text{总比较次数 } C_{\min} = \sum_{i=2}^n 1 = n - 1 = O(n) $$ $$ \text{总移动次数 } M_{\min} = 0 $$
  • 最坏情况分析:待排序列呈逆序排列。第 \(i\)$ \text{趟需与前面所有} $\(i-1\) 个元素比较,且已排序元素均需向后移动 1 位。 $$ \text{总比较次数 } C_{\max} = \sum_{i=2}^n i = \frac{(n+2)(n-1)}{2} = O(n^2) $$ $$ \text{总移动次数 } M_{\max} = \sum_{i=2}^n (i+1) = \frac{(n+4)(n-1)}{2} = O(n^2) $$
  • 稳定性保证:当扫描遇到相等元素时,插入操作停止在该相等元素之后,相等元素的相对次序保持不变,因而算法是稳定的。

2.2 折半插入排序(Binary Insertion Sort)

  • 算法机理:由于子序列 \(A[1 \dots i-1]\)$ \text{严格有序,在确定} $\(A[i]\) 的插入位置时,采用折半查找(二分查找)替代线性扫描。找到插入位置 high + 1 后,再统一将 [high + 1 ... i - 1] 范围内的元素向后平移 1 位,插入目标元素。
  • 比较次数推导:折半查找在长度为 \(i-1\)$ \text{的有序表中寻找插入点,比较次数仅取决于二叉判定树的高度,固定为} $\(\lfloor \log_2(i-1) \rfloor + 1\)。 总比较次数 \(C\) 为: $\(C = \sum_{i=2}^n \lceil \log_2 i \rceil = \Theta(n \log_2 n)\)$ 核心结论:折半插入排序的关键字比较次数与待排序列的初始排列状态完全无关,恒为 \(O(n \log_2 n)\)。
  • 移动次数及总时间复杂度:折半查找仅优化了元素位置的查找效率,未能减少元素的物理移动次数。在最坏情况下,移动次数依旧为 \(O(n^2)\)$ \text{。因此总时间复杂度仍为} $\(O(n^2)\)。
  • 稳定性:二分查找设定条件 low = mid + 1(当 A[mid] <= A[0] 时),可保证将待插元素放置在相等元素构成的区间最右端之后,从而保证算法稳定性。

2.3 希尔排序(Shell's Sort)

  • 突破平方阶的数学思想:直接插入排序在两种情况下极其高效:(1) 待排序列规模 \(n\) 很小;(2) 待排序列基本有序(移动距离极短)。希尔排序通过设置递减增量序列,使初始阶段序列规模小、跨度大,逐步实现宏观有序;最终增量收敛为 1 时,序列已高度趋近于全局有序,极大地规避了元素大范围移动的开销。
  • 子序列切分规则:选定增量序列 \(d_1 > d_2 > \dots > d_k = 1\)$ \text{。对于当前增量} $\(d\)$ \text{,将序列划分为} $\(d\)$ \text{个互不相交的子序列,所有下标同余(模} $\(d\) 同余)的元素划入同一子序列,即: $$ \text{子序列 } k: {A[k], A[k+d], A[k+2d], \dots}, \quad (1 \le k \le d) $$ 对每个子序列分别执行直接插入排序。
  • 不稳定性的几何本质:增量跳跃比较及跨步长交换导致相同关键字的记录在各自所属的不同子序列中发生不同步的移位,从而打乱原有的先后顺序。例如序列 [3, 2, 2*],若第一趟增量 \(d=2\),子序列 0 为 (3, 2*),排序后为 (2*, 3),序列变为 [2*, 2, 3],导致 2* 跑到了 2 之前。
  • 顺序存储依赖性:希尔排序计算相隔增量 \(d\)$ \text{的元素地址完全依赖数组的随机寻址公式} $\(\text{Loc}(A[i+d]) = \text{Loc}(A[i]) + d \times \text{size}\)$ \text{。若改为链式存储,定位相距} $\(d\)$ \text{的后继节点需要顺序遍历指针} $\(d\) 次,算法时间效率大幅恶化。

3. 交换类排序算法深层机理

3.1 冒泡排序(Bubble Sort)

  • 算法机理:从前往后两两比较相邻记录的关键字,若为逆序(\(A[j-1] > A[j]\)),则交换位置,直到整趟处理结束。每趟排序均使当前待排区间的最大元素沉淀到区间尾部。
  • 标志位终止优化:设立布尔变量 exchange_flag。若整趟扫描遍历中未发生任何一次数据交换,表明待排区间已完全有序,算法提前终止。
  • 最好和最坏复杂度:
  • 最好情况(初始正序):第一趟扫描比较 \(n-1\)$ \text{次,0 次交换,算法退出,时间复杂度} $\(O(n)\);
  • 最坏情况(初始逆序):需进行 \(n-1\)$ \text{趟处理,比较次数与交换次数均为} $\(\frac{n(n-1)}{2}\)$ \text{,时间复杂度} $\(O(n^2)\)。
  • 稳定性:因仅在相邻元素出现严格逆序时才执行交换,相等元素绝不交换,具有绝对稳定性。

3.2 快速排序(Quick Sort)

  • 分治策略及划分操作(Partition):快速排序是基于分治策略的高效排序算法。单次划分选取一个基准元素(枢轴 Pivot),通过双指针相向扫描(填坑法),将待排区间划分为两部分: $\(\forall x \in \text{LeftSubArray}, \quad x \le \text{Pivot}\)$ $\(\forall y \in \text{RightSubArray}, \quad y \ge \text{Pivot}\)$ 枢轴元素在此过程结束后,其位置即为其在全局最终有序序列中的确定位置。
快速排序单次划分(填坑法)状态演变过程:
初始状态(选取 A[low] 作为 pivot 暂存):
low -> [ 49 ]  38   65   97   76   13   27  [ 49*] <- high
pivot = 49

步骤 1:high 从右向左扫描,寻找首个小于 pivot 的元素:
发现 27 < 49,将 27 填入 low 处,low 右移:
      [ 27 ]  38   65   97   76   13  (坑)  [ 49*]
              ^low                        ^high

步骤 2:low 从左向右扫描,寻找首个大于 pivot 的元素:
发现 65 > 49,将 65 填入 high 处,high 左移:
      [ 27 ]  38  (坑)  97   76   13  [ 65 ] [ 49*]
                   ^low              ^high

步骤 3:high 从右向左扫描,发现 13 < 49,填入 low 处,low 右移:
      [ 27 ]  38  [ 13 ] 97   76  (坑) [ 65 ] [ 49*]
                          ^low     ^high

步骤 4:low 从左向右扫描,发现 97 > 49,填入 high 处,high 左移:
      [ 27 ]  38  [ 13 ] (坑) 76  [ 97 ] [ 65 ] [ 49*]
                          ^low
                          ^high  (low == high,循环结束)

步骤 5:将 pivot 回填至 low==high 处:
最终结果:[ 27   38   13 ]  < 49 >  [ 76   97   65   49*]
(枢轴 49 已处于全局最终有序位置,左侧全部 <= 49,右侧全部 >= 49)
  • 递归树及复杂度推导:
  • 最好时间复杂度:每次划分均能将区间均匀对半平分。 递推方程:\(T(n) = 2T(n/2) + O(n)\)$ \text{,根据主定理,解得} $\(T(n) = \Theta(n \log_2 n)\)$ \text{。递归树高度为} $\(\lfloor \log_2 n \rfloor + 1\)。
  • 最坏时间复杂度:每次划分选取的枢轴均为当前区间的极值元素(如序列初始完全正序或完全逆序,且每次选取首元素为枢轴)。划分产生极其不平衡的子区间(大小分别为 \(0\)$ \text{和} $\(n-1\))。 递推方程:\(T(n) = T(n-1) + O(n)\),展开求和得: $\(T(n) = \sum_{k=1}^n O(k) = O(n^2)\)$ 此时递归树退化为单支树,树高达到 \(n\)。
  • 空间复杂度推导(递归调用栈深度):
  • 最好与平均情况:递归树高为 \(O(\log_2 n)\)$ \text{,辅助栈深度为} $\(O(\log_2 n)\);
  • 最坏情况:递归树高为 \(n\)$ \text{,辅助栈深度达到} $\(O(n)\)。
  • 每趟排序归位定理:若定义一“趟”为对当前所有尚未确定最终位置的子区间各进行一次划分处理,则:
  • 经过第 1 趟处理后,有且仅有 1 个元素就位(根节点枢轴);
  • 经过第 2 趟处理后,序列中处于最终就位状态的元素总数至少增加 1 个(退化为单支时)或至多增加 2 个(左右子树均非空时),即总就位元素数量在 2 到 3 个之间。

4. 选择类排序算法深层机理

4.1 简单选择排序(Simple Selection Sort)

  • 算法机理:第 \(i\)$ \text{趟(} $\(1 \le i \le n-1\)$ \text{)在后续未排序区间} $\(A[i \dots n]\)$ \text{中线性遍历寻找关键字最小的记录,若最小记录不在位置} $\(i\)$ \text{,则将其与} $\(A[i]\) 进行数据交换。
  • 比较次数推导定理: 在简单选择排序中,每趟寻找最小值的遍历不论待排序列初始状态如何,都必须完整比较到底。第 \(i\)$ \text{趟固定进行} $\(n-i\) 次比较。 总比较次数 \(C\) 严格为: $\(C = \sum_{i=1}^{n-1} (n - i) = (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}\)$ 数学定理:简单选择排序的关键字比较次数与序列初始排列状态严格无关。
  • 移动次数极小性定理(核心高频考点):
  • 最好情况:待排序列初始已完全有序,每趟最小值即为当前区间的首元素,无需交换,移动次数为 0;
  • 最坏情况:每趟选出的最小值均非当前区间首元素,必须执行 1 次记录交换。借助临时变量交换两个元素需要执行 3 次移动赋值。总共执行 \(n-1\) 趟交换,因此最大移动次数为: $\(M_{\max} = 3(n-1)\)$ 学术结论:简单选择排序在最坏情况下的元素移动次数仅为 \(O(n)\)$ \text{级别。在所有基本排序算法(冒泡、直接插入、快速等最坏移动次数均为} $\(O(n^2)\))中,简单选择排序是最坏情况下元素移动次数最少的排序算法。
  • 不稳定性质证明:长距离跨区间数据交换造成稳定性破坏。反例:待排序列 \((5, 5^*, 2)\)$ \text{。第 1 趟在待排序列中找到最小值 2,将其与首位的 5 交换,得到序列} $\((2, 5^*, 5)\)。原本在前的 5 变成了在后,相等元素的初始顺序发生倒置。

4.2 堆排序(Heap Sort)

  • 完全二叉树的数组映射定义:堆是在逻辑上满足完全二叉树结构、在物理上采用一维数组紧凑存储的优先队列。 设完全二叉树包含 \(n\)$ \text{个节点,节点按层次遍历从 1 到} $\(n\) 编号:
  • 大顶堆(Max Heap):每个节点的值均大于等于其左右孩子节点的值。 $$ \text{A[i] \ge A[2i] \quad \text{且} \quad A[i] \ge A[2i+1], \quad (1 \le i \le \lfloor n/2 \rfloor)} $$
  • 小顶堆(Min Heap):每个节点的值均小于等于其左右孩子节点的值。 $$ \text{A[i] \le A[2i] \quad \text{且} \quad A[i] \le A[2i+1], \quad (1 \le i \le \lfloor n/2 \rfloor)} $$
  • 建堆过程及线性时间复杂度推导: 建堆采用自底向上的下滤调整(Sift-Down)策略,从最后一个非叶子节点 \(\lfloor n/2 \rfloor\) 开始,逆序向前逐个节点执行下滤,直至根节点 1。 严格数学推导: 设含有 \(n\)$ \text{个节点的完全二叉树高度为} $\(h = \lfloor \log_2 n \rfloor\)。 位于深度 \(k\)$ \text{(根节点深度设为 0)的节点数量至多为} $\(2^k\)$ \text{个,其最多需要下滤的层数为} $\(h - k\)。 整个建堆过程中节点下滤比较与移动的总步数上界为: $\(S = \sum_{k=0}^{h-1} 2^k (h - k)\)$ 令变量置换 \(j = h - k\)$ \text{,则当} $\(k=0\)$ \text{时} $\(j=h\)$ \text{;当} $\(k=h-1\)$ \text{时} $\(j=1\)。 $\(S = \sum_{j=1}^h j \cdot 2^{h-j} = 2^h \sum_{j=1}^h \frac{j}{2^j}\)$ 考察数列前 \(h\)$ \text{项和:} $\(\sum_{j=1}^\infty \frac{j}{2^j} = 2\)。 因此: $\(S \le 2^h \times 2 = 2^{h+1} \approx 2n = O(n)\)$ 结论:自底向上筛选建堆算法的时间复杂度为严格的 \(O(n)\)$ \text{,而非} $\(O(n \log_2 n)\)。
  • 堆排序执行流程及总复杂度:
  • 首先将无序数组构建为大顶堆,耗时 \(O(n)\);
  • 循环执行 \(n-1\)$ \text{次:将堆顶元素} $\(A[1]\)$ \text{(当前最大值)与堆底未就绪末位元素} $\(A[i]\)$ \text{交换,堆有效规模递减 1;随后对新的堆顶元素} $\(A[1]\)$ \text{执行下滤调整恢复大顶堆特性(单次耗时} $\(O(\log_2 i)\))。 循环阶段总耗时为 \(\sum_{i=2}^n O(\log_2 i) = O(n \log_2 n)\)。 综合复杂度:\(O(n) + O(n \log_2 n) = O(n \log_2 n)\)$ \text{。堆排序在最好、最坏、平均情况下的时间复杂度恒为} $\(O(n \log_2 n)\)。
  • 空间复杂度及稳定性特征: 空间复杂度为 \(O(1)\)(原地排序)。由于在建堆和下滤调整过程中,父子节点跨层跳跃交换,堆排序是不稳定排序。

5. 归并类排序算法深层机理

5.1 二路归并排序(2-way Merge Sort)

  • 分治思想:将包含 \(n\)$ \text{个元素的序列递归划分为两个长度约为} $\(n/2\)$ \text{的子序列,分别递归进行归并排序;最后通过双指针技术将两个有序子表合并(Merge)为一个长度为} $\(n\) 的有序表。
  • 算法性能数学推导:
  • 递推方程:\(T(n) = 2T(n/2) + cn\)$ \text{(其中} $\(cn\) 为合并双子表所需线性扫描时间)。
  • 展开递推:归并树高度为 \(\lceil \log_2 n \rceil + 1\)$ \text{。每一层所有子表合并所需总比较与移动次数均不超过} $\(c \cdot n\)。 $\(T(n) = n T(1) + c n \log_2 n = \Theta(n \log_2 n)\)$
  • 无论是最好、最坏还是平均情况,二路归并排序的执行时间恒为 \(O(n \log_2 n)\)。
  • 空间开销分析: 在执行 Merge 操作时,需要将两个待合并子表暂存至辅助数组中,因此必须分配一个长度为 \(n\)$ \text{的连续内存空间。尽管递归树的调用栈空间为} $\(O(\log_2 n)\)$ \text{,但辅助数组占用的} $\(O(n)\)$ \text{是空间复杂度的主导项。因此二路归并排序的空间复杂度为} $\(O(n)\)。
  • 稳定性: 在两个子表合并过程中,当左子表与右子表遇到关键字相等的元素时,算法优先将左子表中的元素移入目标数组,保证相对次序不颠倒。因此二路归并排序是稳定的。

6. 分配类排序算法深层机理

6.1 基数排序(Radix Sort)

  • 非比较排序本质:基数排序不通过任何记录关键字之间的直接两两比较来确定相对次序,而是利用关键字各数位(或字符位)的值,将记录分配到 \(r\) 个队列中,再按队列先后顺序串接收集。
  • 多关键字排序策略: 设记录的关键字由 \(d\)$ \text{元组} $\((k^1, k^2, \dots, k^d)\)$ \text{组成,每一位的取值基数为} $\(r\)$ \text{(例如十进制整数的基数} $\(r=10\))。
  • 最低位优先(LSD, Least Significant Digit First):从最低有效位开始向最高位递进,进行 \(d\) 趟“分配”与“收集”。要求每一趟的分配与收集过程必须具备严格的稳定性(先进先出)。
  • 最高位优先(MSD, Most Significant Digit First):从最高位开始将序列切分成若干子区间,再在各子区间内部递归执行 MSD。
  • 时空复杂度推导:
  • 时间复杂度:每一趟分配需要遍历 \(n\)$ \text{个元素入队(耗时} $\(O(n)\)$ \text{),收集需要依次链接} $\(r\)$ \text{个队列的首尾(耗时} $\(O(r)\)$ \text{)。共有} $\(d\) 趟处理,故总时间复杂度为: $\(T(n) = O(d(n + r))\)$ 当 \(d\)$ \text{为常数且} $\(r \ll n\)$ \text{时,基数排序呈现线性时间} $\(O(n)\)。
  • 空间复杂度:需要维护 \(r\)$ \text{个队列的队头与队尾指针,故空间复杂度为} $\(O(r)\)。

7. 内部排序理论极限:基于比较的排序算法时间复杂度下界证明

7.1 决策树模型(Decision Tree Model)

在基于元素两两比较的排序算法中,算法的每一次执行路径均可用一棵二叉判定树完全刻画: 1. 内部节点:表示算法中进行的一次两两比较操作,如 \(A[i] : A[j]\); 2. 分支边:表示比较的结果(如 \(\le\)$ \text{分支和} $\(>\) 分支); 3. 叶子节点:对应于经过一系列比较后得到的一个唯一排定次序。

3 个互异元素 {a, b, c} 的比较决策树示意图:
                   [ a : b ]
                  /         \
              <= /           \ >
           [ b : c ]       [ a : c ]
            /     \         /     \
        <= /       \ >  <= /       \ >
       (a,b,c)  [a:c]   (b,a,c)  [b:c]
                /   \            /   \
               /     \          /     \
            (a,c,b) (c,a,b)  (b,c,a) (c,b,a)

(叶子节点数共 3! = 6 个,决策树高度为 3,最坏情况下至少需比较 3 次)

7.2 最坏情况比较次数下界 \(\Omega(n \log_2 n)\) 严格数学推导

  • 对于任意包含 \(n\)$ \text{个互异元素的序列,其所有可能的排列组合状态数为} $\(n!\) 种。
  • 任何一个正确的排序算法必须能够区分并输出全部这 \(n!\)$ \text{种排列。因此决策树的叶子节点总数} $\(L\) 必须满足: $\(L \ge n!\)$
  • 设该二叉决策树的高度为 \(h\)$ \text{。由二叉树的性质可知,高度为} $\(h\)$ \text{的二叉树其叶子节点数最多为} $\(2^h\),即: $\(2^h \ge L \ge n!\)$
  • 对不等式两端取以 2 为底的对数: $\(h \ge \log_2(n!)\)$
  • 利用斯特林近似公式(Stirling's Formula)\(n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\),或者通过定积分对对数求和进行放缩: $\(\log_2(n!) = \sum_{k=1}^n \log_2 k \ge \int_1^n \log_2 x \, dx = \left[ x \log_2 x - x \log_2 e \right]_1^n = n \log_2 n - n \log_2 e + \log_2 e\)$ $\(\implies h \ge n \log_2\left(\frac{n}{e}\right) = \Omega(n \log_2 n)\)$
  • 定理结论:任何基于关键字比较的内部排序算法,在最坏情况下的比较次数至少为 \(\lceil \log_2(n!) \rceil = \Omega(n \log_2 n)\)$ \text{。因此二路归并排序、堆排序的最坏时间复杂度} $\(O(n \log_2 n)\) 已经达到了基于比较的内部排序算法的理论下界渐近最优解。若要突破此极限,只能依赖非比较策略(如基数排序、计数排序)。

三、 近十年真题精讲(2016~2025)


【真题 1】2025 年 408 第 10 题 · 最坏情况下移动次数极限分析

题目
下列排序算法中,最坏情况下元素移动最少的是( )。
A. 冒泡排序          B. 直接插入排序          C. 快速排序          D. 简单选择排序

【解析】

对各备选项在最坏情况下的元素移动操作量级进行逐项辨析: 1. 冒泡排序:在最坏情况(初始序列逆序)下,每次相邻元素比较均产生逆序并发生交换。总交换次数为 \(\frac{n(n-1)}{2}\)$ \text{次。每次数据交换需要借助临时变量执行 3 次移动赋值,因此元素总移动次数为} $\(\frac{3n(n-1)}{2} = O(n^2)\)。 2. 直接插入排序:在最坏情况(初始序列逆序)下,第 \(i\)$ \text{趟插入需要将前} $\(i-1\) 个元素全部后移 1 位。加上将待插入元素移入暂存单元及移回数组的开销,总移动次数为: $\(\sum_{i=2}^n (i+1) = \frac{(n+4)(n-1)}{2} = O(n^2)\)$ 3. 快速排序:在最坏情况(枢轴划分极度不平衡,退化为单支树)下,算法退化为平方阶,元素交换与移动操作的累积次数为 \(O(n^2)\)。 4. 简单选择排序:无论待排序列初始状态如何,第 \(i\)$ \text{趟排序仅通过比较找到当前区间的最小元素,最终与区间首位置元素执行至多 1 次交换。在最坏情况下,每趟均需交换 1 次(消耗 3 次移动赋值)。总共执行} $\(n-1\) 趟,因此最坏情况下的最大移动次数为: $\(M_{\max} = 3(n-1) = O(n)\)$ 其移动次数的数量级为严格的线性阶 \(O(n)\)$ \text{,远少于平方阶} $\(O(n^2)\)。

正确答案:D


【真题 2】2025 年 408 第 11 题 · 希尔排序增量子序列逆向判定

题目
对含 9 个关键字的初始序列进行排序,若序列的变化情况如下表所示,则下列排序算法中,采用的是( )。
初始序列:5, 25, 40, 30, 10, 20, 45, 15, 35
第 1 趟排序后的序列:5, 10, 20, 30, 15, 35, 45, 25, 40
第 2 趟排序后的序列:5, 10, 15, 25, 20, 30, 40, 35, 45
A. 希尔排序          B. 基数排序          C. 归并排序          D. 折半插入排序

【解析】

  1. 检验希尔排序子序列同余特征:
  2. 第 1 趟分析:对比初始序列与第 1 趟序列,观察元素跳跃规律。 假设增量为 \(d_1 = 3\):
    • 子序列 0(下标 0, 3, 6):初始为 \(5, 30, 45\) \(\to\)$ \text{排序后为} $\(5, 30, 45\)(单调递增);
    • 子序列 1(下标 1, 4, 7):初始为 \(25, 10, 15\) \(\to\)$ \text{排序后为} $\(10, 15, 25\)(单调递增);
    • 子序列 2(下标 2, 5, 8):初始为 \(40, 20, 35\) \(\to\)$ \text{排序后为} $\(20, 35, 40\)(单调递增)。 对应第 1 趟序列为 [5, 10, 20, 30, 15, 35, 45, 25, 40],完全吻合。
  3. 第 2 趟分析:基于第 1 趟序列,假设增量缩小为 \(d_2 = 2\):
    • 子序列 0(下标 0, 2, 4, 6, 8):元素为 \(5, 20, 15, 45, 40\) \(\to\)$ \text{排序后为} $\(5, 15, 20, 40, 45\);
    • 子序列 1(下标 1, 3, 5, 7):元素为 \(10, 30, 35, 25\) \(\to\)$ \text{排序后为} $\(10, 25, 30, 35\)。 合并交错后得到序列 [5, 10, 15, 25, 20, 30, 40, 35, 45],与题干中第 2 趟序列完全契合。因此采用的是希尔排序。
  4. 排除其他选项:
  5. 折半插入排序:前 \(k\)$ \text{趟后前缀子序列必定局部完全有序。本题第 1 趟前缀 5, 10, 20, 30, 15... 中} $\(30 > 15\),前缀并不单调,排除 D。
  6. 归并排序:第 1 趟两两合并后,每相邻 2 个元素构成的子表必须有序(如 [5, 25], [30, 40], [10, 20], [15, 45], [35]),与序列不符,排除 C。
  7. 基数排序(LSD):第 1 趟按个位数分配收集,个位为 0 的元素(40, 30, 10, 20)必须排在最前端,与序列不符,排除 B。

正确答案:A


【真题 3】2023 年 408 第 10 题 · 排序算法稳定性辨析

题目
下列排序算法中,不稳定的是( )。
I. 希尔排序
II. 归并排序
III. 快速排序
IV. 堆排序
V. 基数排序
A. 仅 I 和 II          B. 仅 II 和 V          C. 仅 I,III,IV          D. 仅 III,IV,V

【解析】

逐项分析各个排序算法的稳定性机理: * I. 希尔排序:基于增量跳跃分组。相同关键字的记录若落入不同的同余子序列中各自插入排序,跨步长移动会导致相对次序发生颠倒,为不稳定排序。 * II. 归并排序:合并操作时,当左右子序列关键字相等时,严格将左侧记录先放入目标数组,可确保原有相对次序不改变,属于稳定排序。 * III. 快速排序:双指针相向扫描并与枢轴交换时,相等元素跨越枢轴发生长距离移位,破坏相对顺序,为不稳定排序。 * IV. 堆排序:在将堆顶元素与堆底末尾交换、以及父子节点筛选下滤调整时,完全二叉树的父子关系调整会使同键值记录的相对位置改变,为不稳定排序。 * V. 基数排序:每一趟按位分配入队、收集出队均严格遵循先进先出(FIFO)原则,从而保证了多关键字处理时的绝对稳定性,属于稳定排序。

综上所述,不稳定的排序算法是 I、III、IV。

正确答案:C


【真题 4】2023 年 408 第 11 题 · 快速排序单次划分枢轴元素判定

题目
使用快速排序算法对数据进行升序排序,若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的枢轴( )。
A. 11          B. 70          C. 80          D. 81

【解析】

快速排序单次划分的核心性质为:枢轴元素 \(P\) 在划分结束后必然处于其全局最终有序位置,且满足两个充要边界条件: 1. \(P\)$ \text{左侧的所有元素值均小于等于} $\(P\); 2. \(P\)$ \text{右侧的所有元素值均大于等于} $\(P\)。

逐项检验备选项: * A 项(元素 11):其左侧包含元素 68。\(68 > 11\),违背了左侧元素均小于枢轴的条件,排除 A。 * B 项(元素 70):其右侧包含元素 23 与 48。\(23 < 70, 48 < 70\),违背了右侧元素均大于枢轴的条件,排除 B。 * C 项(元素 80):其右侧包含元素 77 与 48。\(77 < 80, 48 < 80\),违背了右侧元素均大于枢轴的条件,排除 C。 * D 项(元素 81): * 左侧子序列为 \(\{68, 11, 70, 23, 80, 77, 48\}\)$ \text{,其中最大值为} $\(80 \le 81\); * 右侧子序列为 \(\{93, 88\}\)$ \text{,其中最小值为} $\(88 \ge 81\)。 完全满足枢轴划分的数学定义。

正确答案:D


【真题 5】2022 年 408 第 11 题 · 直接插入排序对比快速排序选型论证

题目
对数据进行排序时,若采用直接插入排序而不采用快速排序,则可能的原因是( )。
I. 大部分元素已有序
II. 待排序元素数量很少
III. 要求空间复杂度为 O(1)
IV. 要求排序算法是稳定的
A. 仅 I、II          B. 仅 III、IV          C. 仅 I、II、IV          D. I、II、III、IV

【解析】

对题干列出的四个工程考量维度进行深入分析: * I. 大部分元素已有序:直接插入排序对“基本有序”序列具有自适应性,比较与移动次数退化为线性阶 \(O(n)\)$ \text{。而快速排序在基本有序且未做随机化基准优化时,极易发生极端划分,时间复杂度退化为} $\(O(n^2)\)。故 I 正确。 * II. 待排序元素数量很少:快速排序递归调用与区间划分带来额外的函数调用栈开销和常数因子,当 \(n\) 极小时,简单的直接插入排序运行速度更快。故 II 正确。 * III. 要求空间复杂度为 O(1):直接插入排序仅需常数项辅助变量,辅助空间严格为 \(O(1)\)$ \text{;快速排序依赖递归调用栈,在最好/平均情况下为} $\(O(\log_2 n)\)$ \text{,最坏情况下为} $\(O(n)\)$ \text{,无法满足} $\(O(1)\) 严格空间限制。故 III 正确。 * IV. 要求排序算法是稳定的:直接插入排序属于保序的稳定排序;快速排序在左右跨界交换时会打乱相等元素的原始相对次序,属于不稳定排序。在必须维持等值记录先后次序的场景下必须选用直接插入排序。故 IV 正确。

综上所述,I、II、III、IV 均成立。

正确答案:D


【真题 6】2021 年 408 第 10 题 · LSD 基数排序分配收集中间状态推导

题目
设数组 \(S[] = \{93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892\}\)$ \text{,采用最低位优先(LSD)基数排序将} $\(S\) 排列成升序序列。第 1 趟分配、收集后,元素 372 之前、之后紧邻的元素分别是( )。
A. 43, 892          B. 236, 301          C. 301, 892          D. 485, 301

【解析】

基数排序采用 LSD 策略,第 1 趟分配按照每个关键字的最低有效位(个位数)进行分配: 1. 提取各位个位数值: * \(93 \to 3\);\(946 \to 6\);\(372 \to 2\);\(9 \to 9\);\(146 \to 6\);\(151 \to 1\); * \(301 \to 1\);\(485 \to 5\);\(236 \to 6\);\(327 \to 7\);\(43 \to 3\);\(892 \to 2\)。 2. 分配入 10 个队列(桶 0 ~ 9,依输入顺序入队): * 桶 1:151 -> 301 * 桶 2:372 -> 892 * 桶 3:93 -> 43 * 桶 5:485 * 桶 6:946 -> 146 -> 236 * 桶 7:327 * 桶 9:9 (其余桶为空) 3. 按桶号 0 到 9 依次出队收集: 收集后的序列为:
151, 301, 372, 892, 93, 43, 485, 946, 146, 236, 327, 9 4. 定位目标元素: 观察元素 372,其前驱紧邻元素为 301,其后继紧邻元素为 892。

正确答案:C


【真题 7】2021 年 408 第 42 题 · 计数排序综合设计、比较次数推导与稳定性修正(算法大题,分值 10 分)

题目
已知某排序算法如下:

void cmpCountSort(int a[], int b[], int n) {
    int i, j, *count;
    count = (int*)malloc(sizeof(int) * n); // C++ 语言:count = new int[n];
    for (i = 0; i < n; i++)
        count[i] = 0;
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[i] < a[j])
                count[j]++;
            else
                count[i]++;
    for (i = 0; i < n; i++)
        b[count[i]] = a[i];
    free(count); // C++ 语言:delete[] count;
}
请回答下列问题。
(1) 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6];,则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么?
(2) 若 a 中含有 n 个元素,则算法执行过程中,元素之间的比较次数是多少?
(3) 该算法是稳定的吗?若是,则阐述理由;否则,修改为稳定排序算法。

【解析】

(1) 算法执行追踪及输出结果推导

cmpCountSort 算法采用“比较计数”思想:通过将序列中所有元素两两比较,统计序列中有多少个元素严格小于(或根据判定条件小于等于)当前元素。若有 \(k\)$ \text{个元素比当前元素小,则当前元素在输出有序序列中的最终物理下标即为} $\(k\)。

对于待排输入数组 \(a = \{25, -10, 25, 10, 11, 19\}\)$ \text{,长度} $\(n = 6\)。初始 count 数组各分量清零:count = {0, 0, 0, 0, 0, 0}。
双重循环逐对执行比较: * \(i = 0\)$ \text{时(} $\(a[0] = 25\)): * \(j = 1\):\(a[0] < a[1]\)$ \text{即} $\(25 < -10\)$ \text{为假} $\(\implies count[0]++ \implies count[0] = 1\); * \(j = 2\):\(a[0] < a[2]\)$ \text{即} $\(25 < 25\)$ \text{为假} $\(\implies count[0]++ \implies count[0] = 2\); * \(j = 3\):\(a[0] < a[3]\)$ \text{即} $\(25 < 10\)$ \text{为假} $\(\implies count[0]++ \implies count[0] = 3\); * \(j = 4\):\(a[0] < a[4]\)$ \text{即} $\(25 < 11\)$ \text{为假} $\(\implies count[0]++ \implies count[0] = 4\); * \(j = 5\):\(a[0] < a[5]\)$ \text{即} $\(25 < 19\)$ \text{为假} $\(\implies count[0]++ \implies count[0] = 5\); * \(i = 1\)$ \text{时(} $\(a[1] = -10\)): * \(j = 2\):\(-10 < 25 \implies count[2]++ \implies count[2] = 1\); * \(j = 3\):\(-10 < 10 \implies count[3]++ \implies count[3] = 1\); * \(j = 4\):\(-10 < 11 \implies count[4]++ \implies count[4] = 1\); * \(j = 5\):\(-10 < 19 \implies count[5]++ \implies count[5] = 1\); * \(i = 2\)$ \text{时(} $\(a[2] = 25\)): * \(j = 3\):\(25 < 10\)$ \text{为假} $\(\implies count[2]++ \implies count[2] = 2\); * \(j = 4\):\(25 < 11\)$ \text{为假} $\(\implies count[2]++ \implies count[2] = 3\); * \(j = 5\):\(25 < 19\)$ \text{为假} $\(\implies count[2]++ \implies count[2] = 4\); * \(i = 3\)$ \text{时(} $\(a[3] = 10\)): * \(j = 4\):\(10 < 11 \implies count[4]++ \implies count[4] = 2\); * \(j = 5\):\(10 < 19 \implies count[5]++ \implies count[5] = 2\); * \(i = 4\)$ \text{时(} $\(a[4] = 11\)): * \(j = 5\):\(11 < 19 \implies count[5]++ \implies count[5] = 3\)。

最终 count 统计数组状态为:
count[0] = 5, count[1] = 0, count[2] = 4, count[3] = 1, count[4] = 2, count[5] = 3。
执行映射赋值 b[count[i]] = a[i]: * \(b[count[0]] = b[5] = a[0] = 25\) * \(b[count[1]] = b[0] = a[1] = -10\) * \(b[count[2]] = b[4] = a[2] = 25\) * \(b[count[3]] = b[1] = a[3] = 10\) * \(b[count[4]] = b[2] = a[4] = 11\) * \(b[count[5]] = b[3] = a[5] = 19\)

因此,数组 \(b\) 中的最终内容为:{-10, 10, 11, 19, 25, 25}。

(2) 元素之间比较次数数学推导

由代码结构可知,外层循环控制变量 \(i\)$ \text{从} $\(0\)$ \text{遍历至} $\(n-2\)$ \text{,内层循环控制变量} $\(j\)$ \text{从} $\(i+1\)$ \text{遍历至} $\(n-1\)。每次内层循环体执行严格一次两两比较操作 if (a[i] < a[j])。
这是一个完全组合比较过程,每个元素均与其后继的所有元素进行一次且仅一次比较。
总比较次数 \(C\) 为: $\(C = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{n-2} (n - 1 - i) = (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}\)$ 该比较次数完全由嵌套循环边界控制,与数组 \(a\)$ \text{中元素的具体初始排列状态无关,恒为} $\(\frac{n(n-1)}{2}\) 次。

(3) 稳定性机理分析及代码修正

结论:该算法不是稳定的。
原因阐述:
考察代码核心比较分支:

if (a[i] < a[j])
    count[j]++;
else
    count[i]++;
当出现相同关键字元素(如 \(i < j\)$ \text{且} $\(a[i] == a[j]\))时,由于条件 a[i] < a[j] 判定为假,算法进入 else 分支,执行了 count[i]++。
这使得原本在原序列中物理位置靠前的元素 \(a[i]\)$ \text{的计数值增加了 1,而位置靠后的元素} $\(a[j]\)$ \text{的计数值未变。其直接后果是} $\(count[i] > count[j]\)$ \text{。在最后映射到数组} $\(b\)$ \text{时,} $\(a[i]\)$ \text{被放置在} $\(a[j]\) 的后方,导致等值记录的原始相对先后顺序发生颠倒,违背了稳定性的定义。

算法修改方案:
将比较条件中的严格小于号 < 修改为小于等于号 <=:

if (a[i] <= a[j])
    count[j]++;
else
    count[i]++;
修改后机理:
当 \(i < j\)$ \text{且} $\(a[i] == a[j]\)$ \text{时,条件 a[i] <= a[j] 判定为真,触发 count[j]++。这使得排在后方的元素} $\(a[j]\)$ \text{计数值加 1,而排在前面的元素} $\(a[i]\)$ \text{计数值保持不变。从而确保了} $\(count[i] < count[j]\)$ \text{,在输出数组} $\(b\)$ \text{中} $\(a[i]\)$ \text{依然严格排在} $\(a[j]\) 之前,算法恢复稳定性。


【真题 8】2020 年 408 第 11 题 · 基本有序序列下插入与选择效率机理辨析

题目
对大部分元素已有序的数组进行排序时,直接插入排序比简单选择排序效率更高,其原因是( )。
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需要的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I          B. 仅 III          C. 仅 I,II          D. 仅 I,II 和 III

【解析】

  • 审视 I(比较次数):在数组大部分已有序的场景下,直接插入排序待插入记录通常只需与前驱比较 1~2 次即可找到插入点,最好情况下比较次数为 \(n-1\)$ \text{次,平均为} $\(O(n)\)$ \text{。而简单选择排序每趟必须无条件遍历剩余区间以寻找全局最小值,其比较次数恒为} $\(\frac{n(n-1)}{2}\)$ \text{(即} $\(O(n^2)\)),与序列初始状态完全无关。因此直接插入排序的比较次数远少于简单选择排序,I 正确。
  • 审视 II(辅助空间):直接插入排序与简单选择排序均仅需要常数级的辅助临时变量(用于暂存数据或记录下标),两者的辅助空间复杂度严格相等,均为 \(O(1)\),无空间差异,II 错误。
  • 审视 III(移动次数):简单选择排序每趟选出极值后仅执行至多 1 次交换(3 次移动),总移动次数至多为 \(3(n-1) = O(n)\)。虽然在完全正序时直接插入排序移动次数为 0,但只要序列中存在少量无序元素,直接插入排序为了腾出位置就需要将其后所有元素依次后移,其移动次数通常高于简单选择排序。因此“移动次数更少”不能作为直接插入排序总体效率高于简单选择排序的普遍理由,III 错误。

综上所述,正确的依据仅有 I。

正确答案:A


【真题 9】2019 年 408 第 7 题 · 排序算法工程选型考量体系

题目
选择一个排序算法时,除算法的时空效率外,下列因素中,还需要考虑的是( )。
Ⅰ. 数据的规模      Ⅱ. 数据的存储方式      Ⅲ. 算法的稳定性      Ⅳ. 数据的初始状态
A. 仅 Ⅲ          B. 仅 Ⅰ、Ⅱ          C. 仅 Ⅱ、Ⅲ、Ⅳ          D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

【解析】

对实际工程及理论选型中的四大核心约束条件进行逐项论证: * Ⅰ. 数据的规模:若规模 \(n\)$ \text{很小,简单排序(如直接插入排序)常数因子小、无递归调用栈开销,往往比} $\(O(n \log_2 n)\) 算法更优;若规模巨大无法全部载入内存,则必须选用外部归并排序。规模大小直接决定算法技术路线,故 Ⅰ 需考虑。 * Ⅱ. 数据的存储方式:数据采用顺序存储(支持下标随机寻址)还是单链表存储(仅支持顺序访问)影响显著。例如堆排序、希尔排序高度依赖随机寻址,若换用链表存储会导致效率断崖式下降;反之,直接插入排序与归并排序在链表上具有天然优势,故 Ⅱ 需考虑。 * Ⅲ. 算法的稳定性:若数据记录包含多个字段且需执行多级次序排列(例如先按分数排序,分数相同时维持原始录入次序),必须强制选用稳定排序算法,故 Ⅲ 需考虑。 * Ⅳ. 数据的初始状态:若数据初始已基本有序,直接插入排序与冒泡排序时间复杂度降至 \(O(n)\)$ \text{,而快速排序若选基准不当则可能退化为} $\(O(n^2)\)。数据的分布分布直接影响自适应排序算法的实际表现,故 Ⅳ 需考虑。

综上,Ⅰ、Ⅱ、Ⅲ、Ⅳ 均属于排序算法选型必须权衡的核心要素。

正确答案:D


【真题 10】2019 年 408 第 10 题 · 快速排序趟数及递归划分归位判别

题目
排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是( )。
A. 5,2,16,12,28,60,32,72
B. 2,16,5,28,12,60,32,72
C. 2,12,16,5,28,32,72,60
D. 5,2,12,28,16,32,72,60

【解析】

  1. 题意规范界定: “对尚未确定最终位置的所有元素进行一遍处理称为一趟”,意味着快速排序的“一趟”对应于递归树上某一深度层级对所有待处理子区间的完全划分:
  2. 第 1 趟:对全局区间进行划分,必然产生 1 个枢轴归位于最终位置,将序列划分为左、右子序列;
  3. 第 2 趟:对第 1 趟划分产生的所有非空子序列各自选取 1 个基准进行划分。
    • 若第 1 趟枢轴处于中间位置,则产生 2 个非空子序列,第 2 趟处理后序列中就位的枢轴元素总数应为 \(1 + 2 = 3\) 个;
    • 若第 1 趟枢轴恰好位于区间端点(退化情形),只产生 1 个非空子序列,第 2 趟仅能对这 1 个子序列进行划分,处理后就位的枢轴元素总数应为 \(1 + 1 = 2\) 个。
  4. 基准元素最终全局有序位置判定准则: 将全部 8 个元素升序排列确定其全局标准位置:
    [0]:2, [1]:5, [2]:12, [3]:16, [4]:28, [5]:32, [6]:60, [7]:72。
    处于最终位置的元素必须满足其自身下标等于排序后下标,且其左侧所有元素均不大于它、右侧所有元素均不小于它。
  5. 逐项推导验证:
  6. A 项(5, 2, 16, 12, 28, 60, 32, 72):
    • 元素 72(下标 7):处于末端,左侧全部小于 72,符合第 1 趟枢轴;
    • 元素 28(下标 4):左侧 \(\{5, 2, 16, 12\} \le 28\)$ \text{,右侧} $\(\{60, 32\} \ge 28\),符合第 2 趟枢轴;
    • 共 2 个枢轴归位,符合第 1 趟枢轴在最右端退化的情形。可能为第二趟结果。
  7. B 项(2, 16, 5, 28, 12, 60, 32, 72):
    • 元素 2(下标 0)处于首端,右侧全部大于 2,可作为一趟枢轴;
    • 元素 72(下标 7)处于末端,左侧全部小于 72,可作为一趟枢轴;
    • 2 与 72 分别在两端归位,可能为第二趟结果。
  8. C 项(2, 12, 16, 5, 28, 32, 72, 60):
    • 元素 28(下标 4):左侧均 \(\le 28\)$ \text{,右侧均} $\(\ge 28\),为第 1 趟枢轴;
    • 第 1 趟将序列划分为左子序列 \(\{2, 12, 16, 5\}\)$ \text{与右子序列} $\(\{32, 72, 60\}\);
    • 第 2 趟对左子序列划分:元素 2(下标 0)归位;
    • 第 2 趟对右子序列划分:元素 32(下标 5)归位;
    • 就位元素共 3 个(2, 28, 32),完全符合分治划分特性。可能为第二趟结果。
  9. D 项(5, 2, 12, 28, 16, 32, 72, 60):
    • 检验各元素就位状态:
    • 12(下标 2):左侧为 \(\{5, 2\} \le 12\)$ \text{,右侧为} $\(\{28, 16, 32, 72, 60\} \ge 12\),满足就位条件;
    • 32(下标 5):左侧 \(\{5, 2, 12, 28, 16\} \le 32\)$ \text{,右侧} $\(\{72, 60\} \ge 32\),满足就位条件;
    • 序列中仅有 12 和 32 满足枢轴归位条件。
    • 推导矛盾:
    • 若第 1 趟选 32 为枢轴,则划分出左子序列 \(\{5, 2, 12, 28, 16\}\)$ \text{和右子序列} $\(\{72, 60\}\)$ \text{。第 2 趟必须同时对左右两个子序列进行处理。右子序列} $\(\{72, 60\}\) 经过第 2 趟划分后,必有一个元素就位(变为有序的 60, 72)。然而 D 选项中右侧依旧是逆序的 72, 60,表明右子序列根本未进行第二趟处理!
    • 若第 1 趟选 12 为枢轴,则左子序列为 \(\{5, 2\}\)$ \text{,右子序列为} $\(\{28, 16, 32, 72, 60\}\)$ \text{。第二趟对右子序列划分出 32 后,其右侧的} $\(\{72, 60\}\) 同样未经处理。
    • 因此,D 选项违背了“对尚未确定最终位置的所有元素进行一遍处理”的定义,绝不可能是第二趟结果。

正确答案:D


【真题 11】2018 年 408 第 10 题 · 希尔排序步长识别及同余验算

题目
对初始数据序列 \((8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)\)$ \text{进行希尔排序。若第一趟排序结果为} $\((1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)\)$ \text{,第二趟排序结果为} $\((1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)\),则两趟排序采用的增量(间隔)依次是( )。
A. 3, 1          B. 3, 2          C. 5, 2          D. 5, 3

【解析】

  1. 反推第 1 趟增量 \(d_1\): 序列共 11 个元素,下标 \(0 \sim 10\)。
    第 1 趟序列 \(A_1 = (1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)\)。
  2. 检验增量 5:
    • \(k = 0\)$ \text{(下标 0, 5, 10):元素为} $\(A_1[0]=1, A_1[5]=6, A_1[10]=8\)$ \text{。原序列对应元素为} $\(8, 1, 6\)$ \text{,排序后为} $\(1, 6, 8\),完全单调递增;
    • \(k = 1\)$ \text{(下标 1, 6):元素为} $\(A_1[1]=3, A_1[6]=4\)(单调递增);
    • \(k = 2\)$ \text{(下标 2, 7):元素为} $\(A_1[2]=7, A_1[7]=9\)(单调递增);
    • \(k = 3\)$ \text{(下标 3, 8):元素为} $\(A_1[3]=5, A_1[8]=11\)(单调递增);
    • \(k = 4\)$ \text{(下标 4, 9):元素为} $\(A_1[4]=2, A_1[9]=10\)(单调递增)。 全部 5 个同余子序列均严格单调递增,故第 1 趟增量确定为 5。排除 A、B。
  3. 反推第 2 趟增量 \(d_2\): 第二趟序列 \(A_2 = (1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)\)。
  4. 检验增量 3:
    • \(k = 0\)$ \text{(下标 0, 3, 6, 9):元素为} $\(A_2[0]=1, A_2[3]=4, A_2[6]=5, A_2[9]=10\)(单调递增);
    • \(k = 1\)$ \text{(下标 1, 4, 7, 10):元素为} $\(A_2[1]=2, A_2[4]=3, A_2[7]=8, A_2[10]=9\)(单调递增);
    • \(k = 2\)$ \text{(下标 2, 5, 8):元素为} $\(A_2[2]=6, A_2[5]=7, A_2[8]=11\)(单调递增)。 所有相距为 3 的子序列均保持有序,符合希尔排序增量为 3 的处理结果。
  5. 若检验增量 2:
    • 考察偶数下标(0, 2, 4, 6...):\(A_2[0]=1, A_2[2]=6, A_2[4]=3\)$ \text{。出现} $\(6 > 3\),存在逆序,不可能为增量 2。排除 C。

正确答案:D


【真题 12】2017 年 408 第 10 题 · 归并排序对比插入排序特性判别

题目
在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是( )。
1. 归并排序的程序代码更短
2. 归并排序的占用空间更少
3. 归并排序的运行效率更高
A. 仅 2          B. 仅 3          C. 仅 1、2          D. 仅 1、3

【解析】

  • 断言 1(代码长度):直接插入排序只需两重简短循环即可实现,核心代码仅十余行;而二路归并排序需要递归划分区间以及双指针合并两个子数组,辅助代码较多,程序更为复杂。因此断言 1 错误。
  • 断言 2(空间占用):直接插入排序是就地排序,空间复杂度为 \(O(1)\)$ \text{;归并排序在合并子序列时必须开辟与待排数组同等规模的辅助数组,空间复杂度为} $\(O(n)\)。归并排序占用的空间明显更多,因此断言 2 错误。
  • 断言 3(运行效率):在平均与最坏情况下,直接插入排序的时间复杂度为 \(O(n^2)\)$ \text{;归并排序的时间复杂度始终稳定在} $\(O(n \log_2 n)\)$ \text{。当数据规模较大时,} $\(O(n \log_2 n)\)$ \text{的执行速度远超} $\(O(n^2)\),效率优势极其显著。因此断言 3 正确。

正确答案:B


【真题 13】2017 年 408 第 11 题 · 链式存储结构对排序算法时间效率影响分析

题目
下列排序方法中,若将顺序存储更换为链式存储,则算法的时间效率会降低的是( )。
1. 插入排序     

  1. 选择排序     

  2. 起泡排序     

  3. 希尔排序     

  4. 堆排序
    A. 仅 1、2          B. 仅 2、3          C. 仅 3、4          D. 仅 4、5

【解析】

分析顺序存储与单链表存储在物理访问机制上的差异对各类排序算法复杂度的实质影响: * 1. 插入排序(直接插入排序):在链表结构中,寻找插入位置需从头遍历链表(耗时 \(O(n)\)$ \text{),而插入节点仅需修改指针(耗时} $\(O(1)\)$ \text{,无需移动任何元素)。排序} $\(n\)$ \text{个节点的总时间仍为} $\(\sum_{i=1}^n O(i) = O(n^2)\),时间效率未降低。 * 2. 选择排序(简单选择排序):在单链表中寻找最小值节点需顺序遍历链表未排序部分(比较次数仍为 \(\frac{n(n-1)}{2}\)$ \text{次),找到后通过交换数据域或调整指针将其挂载到已排序链表末尾(耗时} $\(O(1)\)$ \text{)。总时间复杂度仍为} $\(O(n^2)\),时间效率未降低。 * 3. 起泡排序(冒泡排序):在链表中可通过工作指针沿链表从前往后依次扫描相邻节点并比较大小,逆序则交换其数据域(或调整指针)。每趟处理的比较和交换次数均未改变,总时间仍为 \(O(n^2)\),时间效率未降低。 * 4. 希尔排序:希尔排序的核心基础在于能够以 \(O(1)\)$ \text{时间随机定位下标为} $\(i, i+d, i+2d \dots\)$ \text{的子序列元素。若改为单链表存储,定位相距步长} $\(d\)$ \text{的元素必须从当前节点出发沿 next 指针顺序移动} $\(d\)$ \text{次,访问开销从} $\(O(1)\)$ \text{骤增至} $\(O(d)\)。这彻底破坏了希尔排序快速交换的优势,导致其时间效率严重降低。 * 5. 堆排序:堆数据结构在逻辑上是完全二叉树,其父子节点下标具有紧凑的倍数关系(节点 \(i\)$ \text{的左孩子为} $\(2i\)$ \text{、右孩子为} $\(2i+1\)$ \text{、双亲为} $\(\lfloor i/2 \rfloor\)$ \text{)。堆排序的高度依赖基于数组下标的} $\(O(1)\)$ \text{随机访问。若改为链式存储,无法快速定位孩子节点与末尾节点,建堆与下滤调整过程将极为低效,无法在} $\(O(n \log_2 n)\) 时间内完成,时间效率显著降低。

因此,更换为链式存储后时间效率显著降低的是 4(希尔排序)和 5(堆排序)。

正确答案:D


四、 核心解题套路与易错陷阱

1. 核心解题套路

1.1 排序趟数及中间状态识别

  • 快速排序判定法则:
  • 检查枢轴条件:在当前序列中寻找满足“左侧元素全 \(\le P\)$ \text{且右侧元素全} $\(\ge P\)$ \text{”的元素} $\(P\);
  • 检查全局归位:验证 \(P\) 在升序排定后的下标是否与当前下标完全一致;
  • 检查递归子区间完整性:对于一“趟”处理,必须确保当前所有未就位的子区间各自至少选出了 1 个枢轴归位。若某侧非空子区间完全原封未动,则不满足一趟划分的完整性。
  • 希尔排序增量识别法则:
  • 假设增量为 \(d\)$ \text{,则将所有下标满足} $\(i \equiv j \pmod d\) 的元素提取为一个子序列;
  • 验证各个子序列内部是否已经完全单调递增;
  • 若所有子序列均单调有序,则该增量 \(d\) 成立;反之若存在任一逆序对,该增量立即排除。
  • 堆排序中间状态识别法则: 若经过 \(k\)$ \text{趟大顶堆排序,序列末尾必有} $\(k\)$ \text{个最大的元素已经由小到大排定,且前} $\(n-k\) 个元素在逻辑上必须满足大顶堆的不等式关系(即根节点大于左右孩子)。

1.2 极值分析及选型决策

  • 移动次数极值考查: 最坏情况下元素移动最少 \(\to\)$ \text{简单选择排序(移动次数严格为} $\(3(n-1) = O(n)\))。
  • 比较次数自适应极值考查: 待排序列基本有序时效率最高 \(\to\)$ \text{直接插入排序(比较次数为} $\(n-1\)$ \text{,移动 0 次,时间线性阶} $\(O(n)\))。
  • 空间严苛受限考查: 要求严格 \(O(1)\)$ \text{辅助空间且时间为} $\(O(n \log_2 n)\) \(\to\)$ \text{堆排序(归并需} $\(O(n)\)$ \text{,快排需} $\(O(\log_2 n)\))。
  • 数据结构适配考查: 单链表存储排序 \(\to\) 适宜选用 直接插入排序、二路归并排序;严禁选用 希尔排序、堆排序。

2. 易错陷阱大盘点

  • 陷阱 1:混淆“比较次数与初始状态无关”与“时间复杂度与初始状态无关”
  • 典型陷阱:误认为折半插入排序的时间复杂度与初始状态无关。
  • 深度辨析:折半插入排序利用二分查找,其比较次数确实严格固定为 \(O(n \log_2 n)\)$ \text{,与初始状态无关;但是其元素移动次数依然高度依赖初始序列的排列次序(最好为 0,最坏为} $\(O(n^2)\)$ \text{)。因此折半插入排序的总时间复杂度依然与初始状态相关(最好} $\(O(n \log_2 n)\)$ \text{,最坏} $\(O(n^2)\))。
  • 陷阱 2:快速排序“趟数”的定义边界
  • 典型陷阱:将单次划分(Partition)简单等同于一趟。
  • 深度辨析:在 408 统考真题体系中,“一趟”严格定义为“对尚未确定最终位置的所有元素进行一遍处理”。第一趟后生成左、右两个子序列;第二趟必须同时对左、右两个子序列各做一次划分(除非某侧为空)。因此第二趟结束后,就位元素总数通常为 3 个(根枢轴 + 左子枢轴 + 右子枢轴),退化时至少也有 2 个。
  • 陷阱 3:简单选择排序与堆排序的稳定性误区
  • 典型陷阱:误以为选择类排序存在稳定算法。
  • 深度辨析:简单选择排序与堆排序均属于不稳定排序。简单选择排序因跨越未排区间的长距离交换破坏保序性;堆排序在建堆与下滤时调整完全二叉树父子节点相对位置,同样破坏保序性。
  • 陷阱 4:基数排序无关键字比较的本质认知
  • 典型陷阱:在计算基数排序复杂度时套用比较决策树下界。
  • 深度辨析:\(\Omega(n \log_2 n)\)$ \text{的时间下界仅适用于“基于关键字两两比较”的内部排序。基数排序、计数排序基于映射与桶分配,完全不发生关键字之间的相对大小比较,因此能够突破该理论下界,达到线性时间} $\(O(d(n+r))\)。

五、 考点速记清单

  1. 稳定性记忆口诀:
    “考(快)研(选)希(希)望(堆)不稳定”。
    解释:快速排序、简单选择排序、希尔排序、堆排序是不稳定的;其余直接插入、折半插入、冒泡、归并、基数排序均稳定。
  2. 每趟至少确定一个最终位置口诀:
    “快(快速)选(简单选择)堆(堆排序)冒(冒泡)”。
    解释:这四种排序算法每执行一趟,必定至少将一个元素放置在其全局最终有序位置上。
  3. 比较次数与初始状态完全无关算法:
    “折半插入、简单选择、二路归并、基数排序”。
    解释:折半插入固定为 \(O(n \log_2 n)\)$ \text{次比较;简单选择固定为} $\(\frac{n(n-1)}{2}\) 次比较;基数排序无关键字两两比较。
  4. 移动次数最少算法:
    简单选择排序。最坏情况下元素移动次数为 \(3(n-1) = O(n)\)$ \text{,远低于其他平方阶排序的} $\(O(n^2)\)。
  5. 最好、最坏与平均时间复杂度均相同的算法:
    “堆排、归并、选择、基数”。
    解释:堆排序(恒为 \(O(n \log_2 n)\)$ \text{)、二路归并(恒为} $\(O(n \log_2 n)\)$ \text{)、简单选择(恒为} $\(O(n^2)\)$ \text{)、基数排序(恒为} $\(O(d(n+r))\))。
  6. 建堆时间复杂度:
    自底向上调整筛选建堆的时间复杂度为 \(O(n)\)$ \text{(利用级数放缩} $\(\sum \frac{j}{2^j} = 2\)$ \text{证明),而非} $\(O(n \log_2 n)\)。
  7. 基于比较的排序算法理论下界:
    基于决策树叶子节点数 \(L \ge n!\)$ \text{,最坏比较次数下界为} $\(\lceil \log_2(n!) \rceil = \mathbf{\Omega(n \log_2 n)}\)。