PAT题解 B 1035

题解:PAT-B 1035 插入与归并

这是一篇测试用文章,欢迎围观.

题目全文:

题目地址在这里

根据维基百科的定义:

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

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

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

输入格式:

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

输出格式:

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

输入样例1:

1
2
3
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例1:

1
2
Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例2:

1
2
3
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例2:

1
2
Merge Sort
1 2 3 8 4 5 7 9 0 6

题目解读

这是我刷乙级题时比较头疼的一道题,前后查阅了很多别人的代码,后又观看了陈越姥姥的视频总算弄明白了这道题需要注意哪些.

  1. 如何区分简单插入排序和非递归的归并排序;
  2. 如何根据测试用例的类型再迭代一次运算;
  3. 如何处理边界测试.

这里要强调一下本题使用递归的归并排序是无法AC的,本渣使用递归的归并排序最多只能得到17分. 关于递归的归并与迭代归并区别请围观这里 (中文版省去了很多分析过程,强烈建议读英文原版),另外,关于插入排序算法的Wiki在这里.

解题过程

如何区分简单插入排序和非递归的归并排序

只要抓住两个关键点即可:

  1. 使用插入排序序列的开头一部分一定是有序的;
  2. 无序部分与原文一致

比如下面这个例子:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

我们可以这样来判断:

  1. 首先扫描 1 2 3 7 8 为有序序列,当读取到5时发现 8 > 5暂停,执行步骤2;
  2. 5开始对后面的序列与原序列进行比较,若发现全部是匹配的,则该序列的排序算法为插入排序,并记录下开始无序的位置;否则为归并排序.

显然后面的部分与原文一致,因此这个序列排序使用的是插入排序. 注意这里必须满足以上两个条件才能推出插入排序算法.

这里不得不提到有同学使用从后向前寻找不匹配点的方法来判断排序算法,这个方法是不对的,比如下面这个例子:

3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

虽然这里的后面一部分0 6与原题一致,但它并不满足前置子序列有序,因此它不是插入排序,后面的测试用例就有一个测试点来卡这种情况。

对于如何判断是否使用归并排序则相对麻烦,考虑到题目中明确指出测试用例是合法的并且只能是归并和插入排序两种之一,所以这里使用排除法来确定归并排序.

如何根据测试用例的类型再迭代一次运算

对于插入排序

这个就非常简单了,如果明白了插入排序的算法,直接从上面记录下的点进行再迭代一次即可。

对于归并排序

这个相对要麻烦一些,其关键步骤是确定归并段的长度。有的同学想到像插入排序一样从头开始寻找最长有序子序列,这是不对的,因为题意中归并排序是迭代一轮后才得到题目序列,即题目序列被分为若干归并段,每一小段都是有序的,因此若原文前一段本身已经有序,那么进行归并后得到的序列一定也是整体有序的,那么也就无法通过通过前置子序列的最大有序长度来代表所有归并段的长度。比如下面这个例子:

10
2 1 8 3 7 5 9 4 0 6
1 2 3 8 5 7 4 9 0 6

显然我们无法从1 3 2 8是最长前置有序子列就判断出归并段的长度为4。正确答案应该是2

有的同学使用模拟法,即对原序列进行分步归并排序,每迭代一次都与题目序列进行比较,直到发现匹配的情况为止。 这种方法在题目所给的时间限制下也能通过,但本着认真负责的态度,我们应该寻找一种更加聪明的办法来确定

通过陈越姥姥的启发,我们总结出一下步骤判断最大归并段的长度:

  1. 假设每个归并段的长度为l, (l的初始值为2,因为一个元素不存在有序无序的概念);
  2. 对所有相邻两个归并段相连的两个元素进行比较,若该两元素仍有序,则归并段的长度l *= 2; 否则终止循环,l即为要确定的最大归并段长度。

程序实现起来就是通过for(l=2; l<=N; l*=2)这个大循环内部完成的。

当确定了最大归并段长度,余下的工作就变得简单了,直接再迭代归并一次即可。
具体代码可以参考最后的AC代码。

如何处理边界测试

PAT的题目测试不给出测试数据以及测试提示,比较考验同学们的程序测试能力,本渣在通过这道题时前后想了很久,也提交了很多次,还是在看了陈越姥姥的讲解后才知道测试数据的提示,测试数据包含一下几类:

  1. 最小N(N = 4,因为只有当N >= 4时才能区分出归并排序与插入排序中间子列).
    • 插入排序第1步,什么都没改变;
    • 归并排序第1步,什么都变了;
  2. 尾部子列无变化,但是前面变了(归并).
  3. 最大N.

有了如上提示,加上前面的讲解,相信读者一定能够独立AC这道题了。

AC代码:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
//#include <fstream>
using std::cin;
using std::cout;
using std::endl;
int main()
{
// std::ifstream cin("in.txt");
int N;
cin >> N;
int *Orig = new int[N];
for(int i=0; i!=N; ++i){
cin >> Orig[i];
}
int *tmp = new int[N];
for(int i=0; i!=N; ++i){
cin >> tmp[i];
}
int k(0);
for(int i=k; i!=N-1; ++i){
if( tmp[i] > tmp[i+1] ){
k = i;
break;
}
}
bool IsInsertion(true);
for(int i=++k; i!=N; ++i){
if( tmp[i] != Orig[i] ){
IsInsertion = false;
break;
}
}
if( IsInsertion ){
cout << "Insertion Sort" << endl;
for(int i=k; i!=0; --i){
if( tmp[i] < tmp[i-1] ){
int t = tmp[i];
tmp[i] = tmp[i-1];
tmp[i-1] = t;
}else break;
}
for(int i=0; i!=N-1; ++i){
cout << tmp[i] << " ";
}cout << tmp[N-1] << endl;
}else{
cout << "Merge Sort" << endl;
bool Identified = false;
for(int l=2; l<=N; l*=2){
for(int i=l; i<N; i += 2*l){
if( tmp[i-1] > tmp[i] ){
Identified = true;
break;
}
}
if( Identified ){
k = l;
break;
}
}
// cout << "k = " << k << endl;
for(int i=0; i<N; i+=k*2){
int *tmpArr = new int[k*2];
int lef = i;
const int mid = ( lef+k < N ) ? lef+k : N;
const int rig = ( mid+k < N ) ? mid+k : N;
int cur = mid;
int j=0;
while( lef < mid and cur < rig ){
if( tmp[lef] < tmp[cur] ){
tmpArr[j++] = tmp[lef++];
}else{
tmpArr[j++] = tmp[cur++];
}
}
while( lef < mid ){
tmpArr[j++] = tmp[lef++];
}
while( cur < rig ){
tmpArr[j++] = tmp[cur++];
}
for(int t=0; t!=j; ++t){
tmp[i+t] = tmpArr[t];
}
delete[] tmpArr;
}
for(int i=0; i!=N-1; ++i){
cout << tmp[i] << " ";
}cout << tmp[N-1] << endl;
}
return 0;
}