测试 1035. 插入与归并(25)-pat乙级真题

guixianren · June 12, 2020 · 3 hits

前言

这应该会是一个会持续很长时间的主题,要上研究生了,总感觉自己的基本功很差,而如果真的要有所成就,这基本功就是必要的东西了,而且这也不是一天两天能完成的事情,急不得,whatever,要步履不停啊。

这题是 PAT 乙级的关于插入与归并算法的一题,需要真正的搞清楚各个排序算法的特点,并搞清楚各个算法的不同之处,看来不仅仅是要会写代码,还要会精通。

题目描述

根据维基百科的定义:

插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确
的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作:首先将原始序列看成 N 个只包含 1 个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩
下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法?

输入描述:

输入在第一行给出正整数 N (<=100);随后一行给出原始序列的 N 个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以
空格分隔。

输出描述:

首先在第 1 行中输出 “Insertion Sort” 表示插入排序、或 “Merge Sort” 表示归并排序;然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试
的结果是唯一的。数字间以空格分隔,且行末不得有多余空格。

输入例子:

10

3 1 2 8 7 5 9 4 6 0

1 2 3 7 8 5 9 4 6 0

输出例子:

Insertion Sort

1 2 3 5 7 8 9 4 6 0

解析

首先最重要的就是搞清楚插入排序和归并排序的特点及区别:

从序列的第一个一直到最后一个循环,然后在已有的序列里面找到该数字的位置插进去。从这里就可以发现,插入排序的特点就是前面一段有序,而后面一段与原序列相同。从这个地方就可以将之区分开来。

所以先找到从左到右满足从小到大顺序的最后一个数字的坐标,然后从这个坐标后面开始找,若后面的序列都相同,就说明是排序,不然就是归并。

其次就是要在搞清楚排序种类后,输出下一次的排序结果:

插入排序好计算,但是难的是归并排序,因为其实归并算法的代码是递归的,先排完左边,再排完右边的,但是本题要求要左边右边一起排列。而根据归并排序的特点,所以最后只能从最开始归并,直到找到给出的序列,就能得到下一次的序列。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <algorithm> // 要用到Sort函数,就要用到Algorithm 记住
using namespace std;

int (){
int n, a[100], b[100], i, j;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (i = 0; b[i] <= b[i + 1] && i < n - 1; i++);
for (j = i + 1; a[j] == b[j] && j < n; j++);
if (j == n){
cout << "Insertion Sort" << endl;
sort(a, a + i + 2);
} else {
cout << "Merge Sort" << endl;
int k = 1, flag = 1;
while (flag){
flag = 0;
for(i = 0; i < n; i++)
if (a[i] != b[i]) flag = 1;
k = k * 2;
for (i = 0; i < n / k; i++)
sort(a + i * k, a + (i + 1) * k);
sort(a + n / k * k, a + n);
}
}
for (i = 0; i < n - 1; i++)
cout << a[i] << " ";
cout << a[n - 1];
return 0;
}
No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.