【算法】Insert or Merge

发表于 | 分类于
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

昨天在练习算法的时候，看到了一道有意思的题目：

B1035/A1089.Insert or Merge(25)

1
2
3
4
5
6
根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

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

输入格式：

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

输出格式：

1
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
1
2
3
4
5
6
7
8
输入样例 1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
1
2
3
4
5
6
7
8
输入样例 2：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：
Merge Sort
1 2 3 8 4 5 7 9 0 6

思路

先进行插入排序，如果执行中发现与给定序列吻合，那么说明是插入排序，计算出下一步的序列后结束算法；如果不是插入排序，那么一定是归并排序，模拟归并排序的过程，如果执行过程中发现与给定序列吻合，那么计算出下一步的序列后结束算法。

注意点

初始序列不参与是否与目标序列相同的比较。如果不考虑这一点可能会导致双解。比如下面一组数据：

1
2
3
4
5
6
7
//input
4
3 4 2 1
3 4 2 1
//output
Insertion Sort
2 3 4 1

优化

这里提供一个比较简单的方法。由于数据范围比较小，在写排序算法的时候可以考虑用sort代替其中比较复杂的部分。

插入排序的特点是，每次插入操作后，数组前i个数一定是有序的，基于这一点，我们可以在写插入排序的时候每次用sort()函数排列前i个数得出插入排序的中间序列，这样就不需要用到复杂的插入操作。

归并排序的特点是，每个步长的数组块一定是有序的，我们可以使用for循环，每次循环i+=step，每次循环用sort()函数直接对步长范围内的数据排序即可得到归并排序的中间序列。

代码

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
#include <iostream>
#include <cstdio>
#include<algorithm>
using namespace std;

bool isEqule(int N1[], int N2[],int n)
{
	for (int i = 0; i < n; i++)
	{
		if (N1[i] != N2[i])
		{
			return false;
		}
	}
	return true;
}

void Insertion(int n, int N[],int error[])
{
	for (int i = 1; i < n; i++)//插入排序的优化操作
	{
		sort(N, N + i);
		if (isEqule(N,error,n))//如果相等再进行一轮排序
		{
			cout << "Insertion Sort" << endl;
			i++;
			sort(N, N + i);
			for (int j = 0; j < n; j++)
			{
				cout << N[j] << ' ';
			}
			break;
		}
	}
}

void MergeSort(int n, int N[],int error[])
{
	for (int step = 2; step / 2 <= n; step *= 2)//Merge排序的优化操作
	{
		for (int i = 0; i < n; i+=step)//对每个步长进行排序
		{
			sort(N + i, N + min(i + step, n - 1));
		}
		if (isEqule(N, error, n))
		{
			cout << "Merge Sort" << endl;
			step *= 2;
			for (int i = 0; i < n; i += step)
			{
				sort(N + i, N + min(i + step, n - 1));
			}
			for (int i = 0; i < n; i++)
			{
				cout << N[i] << ' ';
			}
			break;
		}
	}
}

int main()
{
	int n;
	int N1[100], N2[100];
	int error[100];
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> N1[i];
		N2[i] = N1[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> error[i];
	}
	MergeSort(n, N1, error);
	Insertion(n, N2, error);
	return 0;
}
0%