注意
## 注意
对于不稳定的排序算法，只需举出一组关键字的实例，证明它的不稳定性即可。
在排序过程中，根据数据是否全部存放在内存中，可将排序算法分为两类：① 内部排序，指排序期间所有元素都存放在内存中；② 外部排序，指排序期间元素无法全部装入内存，需要在排序过程中频繁地在内、外存之间交换数据。
一般情况下，内部排序算法在执行过程中主要涉及两种基本操作：比较和移动。通过比较关键字的大小来确定元素的相对顺序，并通过移动元素使整个序列达到有序状态。当然，并非所有内部排序都基于比较操作——例如，基数排序就是一种典型的非比较排序。
各类排序算法各有优缺点，适用于不同场景。通常可将排序算法分为五大类：插入排序、交换排序、选择排序、归并排序和基数排序，后续几节将分别介绍。内部排序算法的性能主要由其时间复杂度和空间复杂度决定，而时间复杂度通常取决于比较和移动操作的次数。
## 注意
大多数内部排序算法更适用于顺序存储的线性表。
## 8.1.2 本节试题精选
### 单项选择题
01. 下述排序算法中，不属于内部排序算法的是（）。
A. 插入排序
B. 选择排序
C. 拓扑排序
D. 冒泡排序
02. 排序算法的稳定性是指（）。
A. 经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B. 经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C. 排序算法的性能与被排序元素个数关系不大
D. 排序算法的性能与被排序元素的个数关系密切
03. 下列关于排序的叙述中，正确的是（）。
A. 稳定的排序算法优于不稳定的排序算法
B. 对同一线性表使用不同的排序算法进行排序，得到的排序结果可能不同
C. 排序算法都是在顺序表上实现的，在链表上无法实现排序算法
D. 在顺序表上实现的排序算法在链表上也可以实现
## 8.1.3 答案与解析
### 单项选择题
01. C
拓扑排序是将有向图中所有结点排成一个线性序列，虽然也是在内存中进行的，但它不属于
<!-- page: 345 -->
第8章 排序
333
我们这里所提到的内部排序范畴，也不满足前面排序的定义。
## 02. A
注意，这里的绝对位置是指若在排序前元素 $R$ 在位置 $i$，则绝对位置就是 $i$，即排序后 $R$ 的位置不发生变化，显然选项 $\mathbf{B}$ 是不对的。选项 $\mathbf{C}$、$\mathbf{D}$ 与题目要求无关。
## 03. B
算法的稳定性与算法优劣无关，选项A排除。使用链表也可以进行排序，只是有些排序算法不再适用，因为这时定位元素只能顺序逐链查找，如折半插入排序。
## 8.2 插入排序
插入排序是一种简单直观的排序算法，其基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到所有记录都插入完毕。基于这一思想，可以引申出三种重要的排序算法：直接插入排序、折半插入排序和希尔排序。
## 8.2.1 直接插入排序①
根据上述插入排序的思想，不难得出一种最简单也最直观的直接插入排序算法。假设在排序过程中，待排序表 $\mathrm{L}[1\dots n]$ 在某一时刻的状态如下：
| 有序序列 L[1...i-1] | L(i) | 无序序列 L[i+1...n] |
| --- | --- | --- |
要将元素 $\mathrm{L}(\mathrm{i})$ 插入到已有序的子序列 $\mathrm{L}[1\dots \mathrm{i} - 1]$ 中，需执行以下操作（为避免混淆，下文中用 $\mathrm{L}[]$ 表示一个表，而用 $\mathrm{L}()$ 表示一个元素）：
1）查找 $\mathrm{L}(\mathrm{i})$ 在 $\mathrm{L}[1\dots \mathrm{i} - 1]$ 中的插入位置 $\mathrm{k}$。
2）将 $\mathrm{L}[\mathrm{k}\dots \mathrm{i} - 1]$ 中的所有元素依次后移一个位置。
3）将 $\mathrm{L}(\mathrm{i})$ 放入位置 $\mathrm{k}$。
为实现对整个表 $\mathrm{L}[1\dots n]$ 的排序，可从 $\mathrm{L}(2)$ 开始，依次将 $\mathrm{L}(2)$ 到 $\mathrm{L}(n)$ 插入其前面已排好序的子序列中。初始时，$\mathrm{L}[1]$ 可视为一个长度为 1 的有序子序列。上述过程共执行 $n - 1$ 次，最终得到一个有序表。直接插入排序通常采用原地排序（空间复杂度为 $O(1)$）。在从后往前的比较过程中，需要将已排序的元素逐个后移，为新元素腾出插入位置。
以下是直接插入排序的实现，其中再次使用了前面提到的“唱兵”（作用相同）。
void InsertSort(ElemType A[], int n) {
int i, j;
for (i = 2; i &lt;= n; i++) // 依次将 A[2] ~ A[n] 插入前面已排序序列
if (A[i] &lt; A[i-1]) { // 若 A[i] 关键码小于其前驱，将 A[i] 插入有序表
A[0] = A[i]; // 复制为唱兵，A[0] 不存放元素
for (j = i-1; A[0] &lt; A[j]; --j) // 从后往前查找待插入位置
A[j+1] = A[j]; // 向后挪位
A[j+1] = A[0]; // 复制到插入位置
}
}
假定初始序列为 49, 38, 65, 97, 76, 13, 27, 49，初始时 49 可视为一个已排好序的子序列。按
① 在本书中，凡是没有特殊注明的，通常默认排序结果为非递减有序序列。
<!-- page: 346 -->
2027年数据结构考研复习指导
照上述算法进行直接插入排序的过程如图8.1所示，括号内为当前已排好序的子序列。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.1 直接插入排序示例
直接插入排序的性能分析如下。
空间效率：仅使用常数个辅助单元，空间复杂度为 $O(1)$。
时间效率：整个排序过程共进行 $n - 1$ 趣插入操作，每趟包括关键字比较和元素移动，具体次数取决于初始序列的状态。最好情况下，表中元素已有序。每插入一个元素只需一次比较，无须移动，时间复杂度为 $O(n)$。最坏情况下，表中元素完全逆序。此时每趟插入需比较 $i - 1$ 次并移动 $i - 1$ 个元素，总时间复杂度为 $O(n^{2})$。平均情况下，假设元素随机排列，平均比较次数和移动次数均约为 $n^{2} / 4$，故时间复杂度仍为 $O(n^{2})$。因此直接插入排序算法的时间复杂度为 $O(n^{2})$。
稳定性：由于插入时总是从后往前比较，并在找到插入位置后才移动元素，因此相同关键字的元素相对顺序不会改变。直接插入排序是稳定的排序算法。
适用性：该算法适用于顺序存储和链式存储的线性表，采用链式存储时无须移动元素。
## 8.2.2 折半插入排序
从直接插入排序算法可以看出，每趟插入过程包含两项操作：① 在前面的有序子表中查找待插入元素的正确位置；② 为该位置腾出空间，并将待插入元素放入其中。在直接插入排序中，总是边比较边移动元素。而折半插入排序则将二者分离：先通过折半查找确定插入位置，再统一移动元素。当排序表采用顺序存储时，可以在查找有序子表时使用折半查找来提高效率。一旦确定了插入位置，便可将该位置及其后的所有元素统一后移一位，从而空出插入位置。
折半插入排序的排序过程示例见本书配套视频，其代码实现如下：
void BInsertSort(ElemType A[], int n) {
int i, j, low, high, mid;
for (i = 2; i &lt;= n; i++) {
A[0] = A[i]; //将 A[i] 暂存到 A[0]
low = 1; high = i - 1; //设置折半查找的范围
while (low &lt;= high) {
mid = (low + high) / 2; //取中间点
if (A[mid] &gt; A[0]) high = mid - 1; //查找左半子表
else low = mid + 1; //查找右半子表
}
for (j = i - 1; j &gt;= high + 1; --j)
A[j + 1] = A[j]; //统一后移元素，空出插入位置
A[high + 1] = A[0]; //插入操作
}
}
<!-- page: 347 -->
第8章 排序
335
**考虑选择** ▶ 直接插入排序和折半插入排序的比較（2012）
空间效率：与直接插入排序相同，仅使用常数个辅助单元，空间复杂度为 $O(1)$。
时间效率：折半插入排序的主要改进在于减少了关键字的比较次数。由于采用折半查找，比较次数约为 $O(n \log_2 n)$，仅取决于元素个数 $n$。然而，元素的移动次数并未减少，仍然依赖于初始序列的有序程度。因此，折半插入排序的时间复杂度仍为 $O(n^2)$。
稳定性：在插入过程中保持了相同关键字元素的相对顺序，因此是稳定的排序算法。
适用性：该算法仅适用于顺序存储的线性表。
## 8.2.3 希尔排序
由前文分析可知，直接插入排序的时间复杂度为 $O(n^{2})$，但在待排序列接近正序时，其时间效率可提升至 $O(n)$。因此，该算法更适用于基本有序或数据量较小的排序场景。希尔排序正是基于这一特性对直接插入排序进行改进，也称为缩小增量排序。
**考虑选择** ▶ 希尔排序的特性与分析（2014、2015、2018、2025）
希尔排序的基本思想是：通过逐步缩小增量的方式，对表中相隔一定距离的元素构成的子序列进行多次直接插入排序，使整个表逐渐趋于基本有序，最终通过一趟完整的直接插入排序完成全局排序。具体而言，算法首先选取一个小于 $n$ 的初始增量 $d_{1}$，将待排序表划分为 $d_{1}$ 个子序列（每个子序列包含下标间隔为 $d_{1}$ 的记录），并对各子序列分别进行直接插入排序；随后依次取更小的增量 $d_{2}, d_{3}, \dots$ （满足 $d_{1} &gt; d_{2} &gt; \dots &gt; d_{t} = 1$），重复分组与排序操作。当增量减至1时，所有记录属于同一子序列，且序列已高度有序，此时执行最后一趟直接插入排序，即可快速获得最终结果。
注意，目前尚未找到理论上最优的增量序列。仍以8.2.1节的关键字为例，假定第一趟取 $d_{1} = 5$，形成5个子序列（对应图中第2至第6行），排序后结果如第7行所示；第二趟取 $d_{2} = 3$，对3个子序列排序，结果见第11行；最后对整个序列进行一趟排序，完整过程如图8.2所示。
</pre>
<p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p>
<pre class="kb-transcript">
图8.2 希尔排序示例
希尔排序的算法实现如下：
```c
void ShellSort(ElemType A[], int n) {
// A[0]只是暂存单元，不是哨兵，当 j &lt;= 0 时，插入位置已到
int dk, i, j;
}
<!-- page: 348 -->
2027年数据结构考研复习指导
```c
for (dk=n/2; dk&gt;=1; dk=dk/2) //增量变化（无统一规定）
for (i=dk+1; i&lt;=n; ++i)
if (A[i]&lt;A[i-dk]) { //需将 A[i] 插入有序增量子表
A[0]=A[i]; //暂存在 A[0]
for (j=i-dk; j&gt;0&amp;&amp;A[0]&lt;A[j]; j-=dk)
A[j+dk]=A[j]; //记录后移，查找插入的位置
A[j+dk]=A[0]; //插入
}
希尔排序算法的性能分析如下：
空间效率：仅使用常数个辅助单元，空间复杂度为 $O(1)$。
时间效率：时间复杂度依赖于所选增量序列，而最优增量序列仍是数学上的未解难题，因此精确分析较为困难。当 $n$ 在常见范围内时，时间复杂度约为 $O(n^{1.3})$；最坏情况下退化为 $O(n^2)$。
稳定性：当相同关键字的记录被划分到不同子表时，可能会改变它们的相对次序，因此希尔排序是不稳定的排序算法。例如，图8.2中49与49在排序过程中相对顺序发生了变化。
适用性：希尔排序仅适用于顺序存储的线性表。
## 8.2.4 本节试题精选
### 一、单项选择题
01. 对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是（）。注意，哨兵的比较不计入次数。
A. 8
B. 10
C. 15
D. 25
02. 在待排序的元素序列基本有序的前提下，效率最高的排序算法是（）。
A. 直接插入排序
B. 简单选择排序
C. 快速排序
D. 归并排序
03. 对有 $n$ 个元素的顺序表采用直接插入排序算法进行排序，在最坏情况下所需的比较次数是（），在最好情况下所需的比较次数是（）。
A. $n - 1$
B. $n + 1$
C. $n / 2$
D. $n(n - 1) / 2$
04. 数据序列 $\{8, 10, 13, 4, 6, 7, 22, 2, 3\}$ 只能是（ ）两趟排序后的结果。
A. 简单选择排序
B. 冒泡排序
C. 直接插入排序
D. 坡排序
05. 用直接插入排序算法对下列4个表进行（从小到大）排序，比较次数最少的是（）。
A. $94, 32, 40, 90, 80, 46, 21, 69$
B. $21, 32, 46, 40, 80, 69, 90, 94$
C. $32, 40, 21, 46, 69, 94, 90, 80$
D. $90, 69, 80, 46, 21, 32, 94, 40$
06. 在下列算法中，（）算法可能出现下列情况；在最后一趟开始之前，所有元素都不在最终位置上。
A. 堆排序
B. 冒泡排序
C. 直接插入排序
D. 快速排序
07. 希尔排序属于（）。
A. 插入排序
B. 交换排序
C. 选择排序
D. 归并排序
08. 对序列 $\{15, 9, 7, 8, 20, -1, 4\}$ 采用希尔排序，经一趟后序列变为 $\{15, -1, 4, 8, 20, 9, 7\}$，则该次采用的增量是（）。
A. 1
B. 4
C. 3
D. 2
09. 若序列 $\{15, 9, 7, 8, 20, -1, 4\}$ 经一趟排序后变成 $\{9, 15, 7, 8, 20, -1, 4\}$，则采用的是（ ）方法。
A. 选择排序
B. 快速排序
C. 直接插入排序
D. 冒泡排序
<!-- page: 349 -->
第8章 排序
337
10. 对序列{98, 36, -9, 0, 47, 23, 1, 8, 10, 7}采用希尔排序，下列序列（ ）是增量为 4 的一趟排序结果。
A. {10, 7, -9, 0, 47, 23, 1, 8, 98, 36}
B. { -9, 0, 36, 98, 1, 8, 23, 47, 7, 10}
C. {36, 98, -9, 0, 23, 47, 1, 8, 7, 10}
D. 以上都不对
11. 对序列{E, A, S, Y, Q, U, E, S, T, I, O, N}按照字典顺序排序，采用增量 $d = 6, 3, 1$ 的希尔排序算法。则前两趟排序后，关键字的总比较次数为（ ）。
A. 15
B. 17
C. 16
D. 18
12. 已知输入序列{13, 24, 7, 1, 8, 9, 11, 56, 34, 51, 2, 77, 5}，增量序列 $d = 5, 3, 1$，采用希尔排序算法进行排序，则两趟排序后的结果为（ ）。
A. 1, 7, 8, 9, 13, 24, 11, 34, 51, 2, 5, 56, 77
B. 1, 7, 5, 2, 8, 9, 24, 11, 34, 51, 13, 77, 56
C. 2, 11, 5, 1, 8, 9, 24, 7, 34, 51, 13, 77, 56
D. 2, 5, 11, 1, 8, 9, 7, 24, 34, 13, 51, 77, 56
13. 折半插入排序算法的时间复杂度为（ ）。
A. $O(n)$
B. $O(n \log_2 n)$
C. $O(n^2)$
D. $O(n^3)$
14. 有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，（ ）算法不一定会出现此种情况。
A. 希尔排序
B. 堆排序
C. 冒泡排序
D. 快速排序
15. 以下排序算法中，不稳定的是（ ）。
A. 冒泡排序
B. 直接插入排序
C. 希尔排序
D. 归并排序
16. 以下排序算法中，稳定的是（ ）。
A. 快速排序
B. 堆排序
C. 直接插入排序
D. 简单选择排序
17.【2012 统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
18.【2014 统考真题】用希尔排序算法对一个数据序列进行排序时，若第一趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15，则该趟排序采用的增量（间隔）可能是（ ）。
A. 2
B. 3
C. 4
D. 5
19.【2015 统考真题】希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
20.【2018 统考真题】对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔）依次是（ ）。
A. 3, 1
B. 3, 2
C. 5, 2
D. 5, 3
二、综合应用题
01. 给出关键字序列{4,5,1,2,6,3}的直接插入排序过程。
02. 给出关键字序列{50, 26, 38, 80, 70, 90, 8, 30, 40, 20}的希尔排序过程（取增量序列为 $d = \{5, 3, 1\}$，排序结果为从小到大排列）。
<!-- page: 350 -->
2027年数据结构考研复习指导
## 8.2.5 答案与解析
### 一、单项选择题
#### 01. B
直接插入排序在最坏的情况下要做 $n(n - 1)/2$ 次关键字的比较，当 $n = 5$ 时，关键字的比较次数为10。注意不考虑与哨兵的比较。
#### 02. A
序列初始基本有序，因此使用直接插入排序算法的时间复杂度接近 $O(n)$，而使用其他算法的时间复杂度均大于 $O(n)$。
#### 03. D、A
待排序表为反序时，直接插入排序需要进行 $n(n - 1)/2$ 次比较（从前往后依次需要比较 $1, 2, \dots, n - 1$ 次）；待排序表为正序时，只需进行 $n - 1$ 次比较。注意本题不考虑与哨兵的比较。
#### 04. C
冒泡排序和选择排序经过两趟排序后，应该有两个最大（或最小）元素放在其最终位置；插入排序经过两趟排序后，前三个元素应该是局部有序的。只可能是插入排序。
### 注意
在排序过程中，每趟都能确定一个元素在其最终位置的有冒泡排序、简单选择排序、堆排序、快速排序，其中前三者能形成全局有序的子序列，后者能确定框轴元素的最终位置。
#### 05. B
越接近正序的序列，直接插入排序的比较次数就越少。选项B和C是比较接近正序的，然后分别判断两个序列的比较次数，以选项B为例：第一趟，插入32，比较1次；第二趟，插入46，比较1次；第三趟，插入40，因为40比46小但比32大，所以比较2次；第四趟，插入80，比较1次；第五趟，插入69，比较2次；以此类推，共比较9次。同理求出选项C的比较次数为11次。所以选择选项B。
#### 06. C
在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。
#### 07. A
希尔排序是对直接插入排序算法改进后提出来的，本质上仍属于插入排序的范畴。
#### 08. B
希尔排序将序列分成若干组，记录只在组内进行交换。由观察可知，经过一趟后9和-1交换，7和4交换，可知增量为4。
#### 09. C
前两个元素已经局部有序，很明显一趟直接插入排序算法有效。再排除其他算法即可。
#### 10. A
增量为4意味着所有相距为4的记录构成一组，然后在组内进行直接插入排序，经观察，只有选项A满足要求。
#### 11. B
第一趟：EE为一组，比较；AS为一组，比较；ST为一组，比较；YI为一组，比较后交换；QO为一组，比较后交换；UN为一组，比较后交换，结果为EASIONESTYQU。第二趟：EIEY为一组，用直接插入排序需要依次比较I和E、E和I、E和E、Y和I；AOSQ为一组，依次比较O和A、S
<!-- page: 351 -->
第8章 椿序
339
和 O、Q 和 S、Q 和 O；SNTU 为一组，依次比较 N 和 S、T 和 S、U 和 T。第一趟比较次数为 6，第二趟比较次数为 11，总比较次数为 17。
12. B
第一趟增量 $d = 5$，第一趟排序后，结果为 2, 11, 5, 1, 8, 9, 24, 7, 34, 51, 13, 77, 56。第二趟增量 $d = 3$，第二趟排序后，结果为 1, 7, 5, 2, 8, 9, 24, 11, 34, 51, 13, 77, 56。
13. C
虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数未发生变化，时间复杂度仍为 $O(n^{2})$。
14. A
因为希尔排序是基于插入排序算法提出的，所以它不一定在每趟排序过程后将某一元素放置到最终位置上。
15. C
希尔排序是一种复杂的插入排序算法，它是一种不稳定的排序算法。
16. C
基于插入、交换、选择的三类排序算法中，通常简单方法是稳定的（直接插入、折半插入、冒泡），但有一个例外就是简单选择，复杂方法都是不稳定的（希尔排序、快速排序、堆排序）。
17. D
折半插入排序与直接插入排序都将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序采用顺序查找法，而折半插入排序采用折半查找法。排序的总趟数取决于元素个数 $n$，两者都是 $n - 1$ 趟。元素的移动次数都取决于初始序列，两者相同。使用辅助空间的数量也都是 $O(1)$。折半插入排序的比较次数与序列初态无关，时间复杂度为 $O(n\log_2n)$；而直接插入排序的比较次数与序列初态有关，时间复杂度为 $O(n)\sim O(n^{2})$。
18. B
首先，第二个元素为 1，是整个序列中的最小元素，可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为 2，则第 $1 + 2$ 个元素 4 明显比第 1 个元素 9 要小，排除选项 A。若增量为 3，则第 $i, i + 3, i + 6$（$i = 1, 2, 3$）个元素都为有序序列，符合希尔排序的特点。若增量为 4，则第 1 个元素 9 比第 $1 + 4$ 个元素 7 要大，排除选项 C。若增量为 5，则第 1 个元素 9 比第 $1 + 5$ 个元素 8 要大，排除选项 D。
19. A
希尔排序的思想是：先将待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
20. D
如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第一趟分组：8, 1, 6；3, 4；9, 7；11, 5；2, 10；间隔为 5，排序后组内递增。
第二趟分组：1, 5, 4, 10；3, 2, 9, 8；7, 6, 11；间隔为 3，排序后组内递增。
因此，选择选项 D。
二、综合应用题
01. 【解答】
直接插入排序过程如下。
<!-- page: 352 -->
2027年数据结构考研复习指导
初始序列： 4,5,1,2,6,3
第一趟： 4,5,1,2,6,3 （将5插入{4}）
第二趟： 1,4,5,2,6,3 （将1插入{4,5}）
第三趟： 1,2,4,5,6,3 （将2插入{1,4,5}）
第四趟： 1,2,4,5,6,3 （将6插入{1,2,4,5}）
第五趟： 1,2,3,4,5,6 （将3插入{1,2,4,5,6}）
02. 【解答】
原始序列： 50,26,38,80,70,90,8,30,40,20
第一趟（增量5）： 50,8,30,40,20,90,26,38,80,70
第二趟（增量3）： 26,8,30,40,20,80,50,38,90,70
第三趟（增量1）： 8,20,26,30,38,40,50,70,80,90