【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】

目录😋

任务描述

本关任务：实现二路归并算法

相关知识

为了完成本关任务，你需要掌握：

二路归并算法的基本概念
二路归并算法步骤
代码示例（以 C++ 为例）
时间复杂度和空间复杂度

1. 二路归并算法的基本概念

二路归并算法旨在将两个已经有序的序列合并成为一个新的有序序列。打个比方，就如同有两列分别按照从小到大顺序排好队的人，现在要把这两列人合并成一列，并且依旧保持从小到大的顺序，这就是二路归并算法要完成的任务。它也是归并排序算法中的关键基础操作，归并排序整体思路就是不断地把待排序数组划分成多个子数组，先对子数组排序（常常通过递归调用归并排序来实现），之后再将这些排好序的子数组合并起来。

2. 算法步骤

输入：提供两个已经排好序的数组（或者序列），这里假设为A和B。
输出：生成一个将A和B合并后的新的有序数组。
具体合并操作流程如下：

        首先，定义三个指针，分别指向两个输入数组A和B的起始位置，以及用于存储合并结果的新数组C的起始位置。通常可以用整型变量来表示这些指针，比如i指向A数组，j指向B数组，k指向C数组（初始时，k为 0）。

        接着，开始循环比较A和B指针所指向元素的大小：

当A[i]小于等于B[j]时，把A[i]放入C[k]这个位置，然后i指针向后移动一位（即i++），同时k指针也向后移动一位（即k++），代表已经向结果数组C中成功放入了一个元素，并且准备放入下一个元素的位置。
反之，要是A[i]大于B[j]，则把B[j]放入C[k]中，之后j指针和k指针分别后移一位（执行j++和k++操作）。

        持续进行上述的比较和放入操作，一直到A或者B其中一个数组的所有元素都已经被放入到C数组中为止。

        最后，把还没处理完的那个数组（也就是A或者B中剩余的元素），按照顺序依次放入C数组当中。

3. 代码示例（以 C++ 为例）
#include <iostream>
#include <vector>
using namespace std;// 二路归并函数，将两个有序数组A和B合并为一个有序数组C
vector<int> merge(vector<int>& A, vector<int>& B) {vector<int> C;int i = 0, j = 0;// 循环比较A和B数组的元素，将较小的元素放入C数组while (i < A.size() && j < B.size()) {if (A[i] <= B[j]) {C.push_back(A[i]);i++;} else {C.push_back(B[j]);j++;}}// 将A数组剩余的元素放入C数组（如果有剩余）while (i < A.size()) {C.push_back(A[i]);i++;}// 将B数组剩余的元素放入C数组（如果有剩余）while (j < B.size()) {C.push_back(B[j]);j++;}return C;
}
在上述代码中：

定义了一个名为merge的函数，它接受两个vector类型（可以类比于数组）的参数A和B，分别代表两个已经有序的输入序列。
在函数内部，首先创建了一个名为C的vector，用于存放合并后的结果。然后通过两个嵌套的while循环来实现归并操作，第一个while循环用于比较A和B当前位置的元素，并把较小的元素放入C中；后面两个while循环分别用于处理A或者B有剩余元素的情况，将剩余元素依次添加到C数组中。最后返回合并好的有序数组C。

4. 时间复杂度和空间复杂度

时间复杂度：假设两个输入数组A和B的长度分别是m和n，在最坏的情况下，需要对两个数组中的每一个元素都进行一次比较操作，总共需要比较m + n - 1次左右，所以时间复杂度为 $O(m+n)$ 。
空间复杂度：由于代码中创建了一个新的数组（vector）C来存储合并后的结果，其长度是m + n，所以空间复杂度同样为 $O(m+n)$ 。不过，在一些特殊的实现场景中，如果允许直接在原有的存储空间上进行合并操作（例如原地归并），那么空间复杂度可以经过优化降低到 $O(1)$ ，但这种实现方式的代码逻辑会相对复杂很多。

测试说明

平台会对你编写的代码进行测试：

测试输入示例：(第一行是元素个数，第二行是待排序的原始关键字数据。）
11
18 2 20 34 12 32 6 16 5 8 1 

输出示例：

排序前:18 2 20 34 12 32 6 16 5 8 1 
第1趟归并:2 18 20 34 12 32 6 16 5 8 1 
第2趟归并:2 18 20 34 6 12 16 32 1 5 8 
第3趟归并:2 6 12 16 18 20 32 34 1 5 8 
第4趟归并:1 2 5 6 8 12 16 18 20 32 34 
排序后:1 2 5 6 8 12 16 18 20 32 34

开始你的任务吧，祝你成功！

通关代码

#include <malloc.h>
#include <stdio.h>#define MAXL 100     //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;typedef struct {KeyType key;   //关键字项InfoType data; //其他数据项，类型为InfoType
} RecType;       //查找元素的类型int count = 1; //全局变量，记录第几趟归并void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{for (int i = 0; i < n; i++)printf("%d ", R[i].key);printf("\n");
}//一次归并：将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {/********** Begin *********/RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));int i = low, j = mid + 1, k = 0;while (i <= mid && j <= high) {if (R[i].key <= R[j].key)R1[k++] = R[i++];elseR1[k++] = R[j++];}while (i <= mid)R1[k++] = R[i++];while (j <= high)R1[k++] = R[j++];for (k = 0, i = low; i <= high; i++, k++)R[i] = R1[k];free(R1);/********** End **********/
}void MergePass(RecType R[], int length, int n) //实现一趟归并
{/********** Begin *********/int i;for (i = 0; i + 2 * length - 1 < n; i += 2 * length)Merge(R, i, i + length - 1, i + 2 * length - 1);if (i + length - 1 < n)Merge(R, i, i + length - 1, n - 1);/********** End **********/
}void MergeSort(RecType R[], int n) //二路归并排序算法
{/********** Begin *********/int length = 1;printf("排序前:");DispList(R, n);while (length < n) {MergePass(R, length, n);printf("第%d趟归并:", count++);DispList(R, n);length *= 2;}printf("排序后:");DispList(R, n);/********** End **********/
}int main() {/********** Begin *********/int n;scanf("%d", &n);KeyType keys[MAXL];RecType R[MAXL];for (int i = 0; i < n; i++)scanf("%d", &keys[i]);CreateList(R, keys, n);MergeSort(R, n);/********** End **********/return 0;
}