🏷️ 知识点：归并排序

对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下：

A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序

归并排序 希尔排序

[tag_link]

正确答案：D

观察初始序列（25,84,21,47,15,27,68,35,20）和前三趟结果：第一趟后25位于序列中间，其左侧元素（20,15,21）均小于25，右侧元素（47,27,68,35,84）均大于25，这表明25在第一趟后已到达其最终排序位置，符合快速排序“选取基准并分区”的特点。 第二趟和第三趟继续对左右子序列进行类似分区操作，逐步使整个序列有序。 选择排序每趟应将最小元素置于前端，但第一趟结果中最小元素15不在首位，故排除； 希尔排序基于增量分组排序，结果通常不每趟使基准元素就位； 归并排序通过合并有序子序列实现，早期阶段元素不会快速定位到最终位置。 因此，所给过程与快速排序一致。

在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）

Ⅰ. 归并排序的程序代码更短Ⅱ. 归并排序的占用空间更少Ⅲ. 归并排序的运行效率更高

排序算法 归并排序 插入排序

A. 仅 Ⅱ B. 仅 Ⅲ C. 仅 Ⅰ、Ⅱ D. 仅 Ⅰ、Ⅲ

[tag_link]

正确答案：B

参考 排序算法复杂度 ，归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n), 后者是O(1)。但是前者时间复杂度是O(nlogn), 后者是O(n2)。所以 B 正确。

使用二路归并排序对含 n 个元素的数组 M 进行排序时，二路归并操作的功能是()。

A. 将两个有序表合并为一个新的有序表

B. 将M 划分为两部分，两部分的元素个数大致相等

C. 将 M 划分为n 个部分，每个部分中仅含有一个元素

D. 将M 划分为两部分，一部分元素的值均小千另一部分元素的值

[tag_link]

正确答案：A

概念题，归并针对的对象是序列，二路归并就是将两个有序序列合并成一个。

初始有三个升序序列 (3, 5)、(7, 9)、(6)，若按从左至右的次序选择有序序列进行二路归并排序，则关键字之间的总比较次数是（）。

归并排序

A. 3 B. 4 C. 5 D. 6

[tag_link]

正确答案：C

本题考察 多路归并 的原理，二路归并排序将相邻的有序子序列两两合并，得到合并后有序子序列。重复此过程，直到所有子序列合并为一个有序序列。第一轮归并：将升序序列两两分组，(3,5) 和 (7,9) 分为一组，(6) 分为一组。(3,5) 和 (7,9) 的归并过程如下：

下列排序方法中，时间性能与待排序记录的初始状态无关的是（ ）。

A. 插入排序和快速排序

B. 归并排序和快速排序

C. 选择排序和归并排序

D. 插入排序和归并排序

复杂度分析 归并排序

[tag_link]

正确答案：C

排序算法的时间性能是否与初始状态相关，取决于其时间复杂度在不同输入情况下的变化。 插入排序在最好情况下（已排序）时间复杂度为 O ( n ) ，最坏和平均为 O ( n 2 ) ，因此与初始状态有关； 快速排序的平均时间复杂度为 O ( n lo g n ) ，但最坏情况下（如已排序数组且枢轴选择不当时）会退化到 O ( n 2 ) ，也与初始状态有关。 归并排序采用分治策略，无论输入数据是否有序，其时间复杂度稳定为 O ( n lo g n ) ，与初始状态无关； 选择排序始终通过遍历未排序部分寻找最小（或最大）元素，其最好、最坏和平均时间复杂度均为 O ( n 2 ) ，因此也与初始状态无关。 选项 C 中的选择排序和归并排序均满足时间性能与初始状态无关的条件，而其他选项至少包含一种与初始状态相关的算法，故 C 为正确答案。

一组经过第一趟 2-路归并排序后的记录的关键字为 (25,50,15,35,80,85,20,40,36,70)，其中包含 5 个长度为 2 的有序序，用 2-路归并排序方法对该序列进行第二趟归并后的结果为（ ）。

A. 15,25,35,50,80,20,85,40,70,36

B. 15,25,35,50,20,40,80,85,36,70

C. 15,25,50,35,80,85,20,36,40,70

D. 15,25,35,50,80,20,36,40,70,85

归并排序

[tag_link]

正确答案：B

首先，第一趟归并后得到序列 ( 25 , 50 , 15 , 35 , 80 , 85 , 20 , 40 , 36 , 70 ) 其中包含 5 个长度为 2 的有序子序列，分别为： ( 25 , 50 ) , ( 15 , 35 ) , ( 80 , 85 ) , ( 20 , 40 ) , ( 36 , 70 ) 在第二趟 2-路归并中，需要将相邻的有序子序列两两合并。 具体来说： 合并第一个和第二个子序列：将 ( 25 , 50 ) 和 ( 15 , 35 ) 合并，得到有序序列 ( 15 , 25 , 35 , 50 ) 合并第三个和第四个子序列：将 ( 80 , 85 ) 和 ( 20 , 40 ) 合并，得到有序序列 ( 20 , 40 , 80 , 85 ) 第五个子序列 ( 36 , 70 ) 没有相邻配对，保持原样。 因此，第二趟归并后的序列由三个有序子序列依次组成： ( 15 , 25 , 35 , 50 ) , ( 20 , 40 , 80 , 85 ) , ( 36 , 70 ) , 整体为 15 , 25 , 35 , 50 , 20 , 40 , 80 , 85 , 36 , 70 对比选项，B 与此一致。

设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 5 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

(2) 根据你的合并过程，描述N(N≥2)个不等长升序表的合并策略，并说明理由。

哈夫曼树 归并排序

[tag_link]

1）对于长度分别为 m, n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m +n-1 次。故最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。根据上图中的 哈夫曼树，6 个序列的合并过程为：第 1 次合并：表 A 与表 B 合并，生成含有 45 个元素的表 AB ;第 2 次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC;第 3 次合并：表 D 与表 E 合并，生成含有 110 个元素表 DE;第 4 次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE;第 5 次合并：表 ABCDE 与表 F 合并，生成含有 395 个元素的最终表。由上述分析可知，最坏清况下的比较次数为：第 1 次合并，最多比较次数 = 10+35-1 = 44；第 2 次合并，最多比较次数 = 45+40-1 = 84；第 3 次合并，最多比较次数 = 50+60-1 = 109；第 4 次合并，最多比较次数 = 85+110-1 = 194；第 5 次合并，最多比较次数 = 195+200-1 = 394。故比较的总次数最多为：44+84+109+194+394 = 825。

2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。【评分说明】①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5 分。按其他策略进行合并，过程描述正确，给 3 分。②正确算出与合并过程一致的总比较次数，给 2 分。若计算过程正确，但结果错误，可给 1 分。③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给 3 分。如果采用其他策略，只要能够完成合并，给 2 分。

一个长度为 L（L ≥ 1） 的升序序列 S ，处在第⌈L/2⌉个位置的数称为 S 的中位数。例如，若序列 S1 = (11,13,15,17,19)，则 S1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 S2 = (2,4,6,8,20)，则 S1 和 S2 的中位数是 11 。现有两个等长的升序序列 A 和 B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

归并排序

[tag_link]

(1) 求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。根据题目分析，分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。① 若a=b，则a或b即为所求的中位数。原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列 b 前边的元素为先前两个序列中排在 a 和 b 前边的元素；排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b后边的元素。所以子序列 ab 一定位于最终序列的中间，又因为 a=b，显然 a 就是中位数。②否则（假设a<b)，中位数只能出现 (a,b) 范围内。原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如⋯a⋯b⋯的序列出现，中位数必出现在 (a,b) 之间。因此可以做如下处理：舍弃 a 所在序列 A 的较小一半，同时舍弃 b 所在序列 B 的较大一半。在保留两个升序序列中求出新的中位数 a 和 b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。算法的基本设计思想如下。分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下：① 若a=b，则 a 或 b 即为所求中位数，算法结束。② 若a<b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求舍弃的长度相等。③ 若a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等。在保留的两个升序序列中，重复过程①、②、③，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

2）算法实现

int M_Search(int A[], int B[], int n) {
    int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2;
    // 分别表示序列 A 和 B 的首位、末位和中位数
    while (s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])
            return A[m1];     // 满足条件 1
        if (A[m1] < B[m2]) {  // 满足条件 2
            if ((s1 + d1) % 2 == 0) {
                // 若元素个数为奇数
                s1 = m1;       // 舍弃 A 中间点以后的部分，且保留中间点
                d2 = m2;       // 舍弃 B 中间点以前的部分，且保留中间点
            } else {
                // 元素个数为偶数
                s1 = m1 + 1;   // 舍弃 A 中间点及中间点以后的部分
                d2 = m2;       // 舍弃 B 中间点以前部分，且保留中间点
            }
        } else {  // 满足条件 3
            if ((s1 + d1) % 2 == 0) {
                // 若元素个数为奇数
                d1 = m1;       // 舍弃 A 中间点以前的部分，且保留中间点
                s2 = m2;       // 舍弃 B 中间点以后的部分，且保留中间点
            } else {
                // 元素个数为偶数
                d1 = m1 + 1;   // 舍弃 A 中间点及中间点以前部分
                s2 = m2;       // 舍弃 B 中间点以后的部分，且保留中间点
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

3）时间复杂度 O(n)，空间复杂度 O(

1)。

以下排序算法中，()在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 简单选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序

[tag_link]

正确答案：C

以下排序算法中，()不需要进行关键字的比较。

A. 快速排序 B. 归并排序 C. 基数排序 D. 堆排序

[tag_link]

正确答案：C

在下列排序算法中，平均情况下空间复杂度为 O(n)的是(),最坏情况下空间复杂度 为 O(n)的 是 ( ) 。 I. 希 尔排序 IⅡ . 堆排序 Ⅲ. 冒泡排序 IV. 归并排序 V. 快速排序 VI. 基数排序

A. I 、IV 、VI B. Ⅱ、V C. IV、V D. IV

[tag_link]

正确答案：【解答】

下列排序算法中，排序过程中比较次数的数量级与序列初始状态无关的是()。

A. 归并排序 B. 插入排序 C . 快速排序 D. 冒泡排序

[tag_link]

正确答案：

2路归并排序中，归并趟数的数量级是()。

A. O(n) B.O(log₂n) C.O(nlog₂n) D.O(n²)

[tag_link]

正确答案：B

若对27个元素只进行三趟多路归并排序，则选取的归并路数最少为()。

A. 2 B.3 C.4 D.5

[tag_link]

正确答案：B

将两个各有N 个元素的有序表合并成一个有序表，最少的比较次数是(),最多的比 较 次 数 是 ( ) 。

A. N B.2N- 1 C.2N D.N- 1

[tag_link]

正确答案：

用归并排序算法对序列{1,2,6,4,5,3,8,7}进行排序，共需要进行()次比较。

A. 12 B.13 C.14 D.15

[tag_link]

正确答案：C

一组经过第一趟2路归并排序后的记录的关键字为{25,50,15,35,80,85,20,40,36,70}, 其中包含5个长度为2的有序表，用2路归并排序算法对该序列进行第二趟归并后的结 果为 ( ) 。

A. 15,25,35,50,80,20,85,40,70,36 B.15,25,35,50,20,40,80,85,36,70 C. 15,25,50,35,80,85,20,36,40,70 D.15,25,35,50,80,20,36,40,70,85

[tag_link]

正确答案：B

若将中国人按照生日(不考虑年份，只考虑月、日)来排序，则使用下列排序算法时， 最 快 的 是 ( ) 。

A. 归并排序 B. 希尔排序 C. 快速排序 D. 基数排序

[tag_link]

正确答案：D

设线性表中每个元素有两个数据项k₁ 和 k₂, 现对线性表按以下规则进行排序：先看数据 项 k₁,k₁ 值小的元素在前，大的元素在后；在k₁ 值相同的情况下，再看k₂,k₂ 值小的元 素在前，大的元素在后。满足这种要求的排序算法是()。

A. 先按 k₁进行直接插入排序，再按 k₂ 进行简单选择排序 B. 先按k₂ 进行直接插入排序，再按k₁ 进行简单选择排序 C. 先按k₁ 进行简单选择排序，再按k₂ 进行直接插入排序 D. 先按k₂ 进行简单选择排序，再按 k₁进行直接插入排序

[tag_link]

正确答案：D

对{05,46,13,55,94,17,42}进行基数排序， 一趟排序的结果是()。

A. 05,46,13,55,94,17,42 B.05,13,17,42,46,55,94 C. 42,13,94,05,55,46,17 D.05,13,46,55,17,42,94

[tag_link]

正确答案：C

有 n 个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立 的队列个数是()。

A. n B.2 C. 5 D.10

[tag_link]

正确答案：D

下列各种排序算法中，()需要的附加存储空间最大。 369第 8 章 排 序 369

A. 快速排序 B . 堆排序 C. 归并排序 D. 插入排序

[tag_link]

正确答案：C

【2021 统考真题】设数组 S[]={9 3,946,372,9,146,151,301,485,236,327,43, 892},采用最低位优先( LSD) 基数排序将S 排列成升序序列。第一趟分配、收集后，元 素372之前、之后紧邻的元素分别为()。

A. 43,892 B.236,301 C.301,892 D.485,301

[tag_link]

正确答案：

已知序列{503,87,512,61,908,170,897,275,653,462},采用非递归的2路归并排序算 法对该序列做升序排序时需要几趟排序?给出每一趟的结果。

[tag_link]

C

设待排序的关键字序列为{12,2,16,30,28,10,16,20,6,18},试写出使用最低位优先 (LSD) 基数排序算法每趟排序后的结果。

[tag_link]

C