1035 插入与归并 (25 point(s))

判断是插入还是归并函数。题目所说“保证每组测试的结果是唯一的”，所以判断其中一个即可。而判断插入函数，由于插入排序必然使得

所以插入排序满足前面的元素有序，而后面的元素待排元素与原始序列相等。所以由以下代码来判断。

a[j] == b[j]

if(j == n)

当后面待排元素和原始序列都满足相等的条件，那么就可以用 j == n 来判断为插入排序。

sort(a, a + i + 2);

当时想了半天为什么这里要+2。对于插入排序来说，再迭代一轮就将已排序末尾的后一个未排序元素拉进来。而前面由

for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);

给出了已排序元素的下标位置。但是下标 i 与后一个元素相差1。而 sort 是 sort (first, last) 对 [first, last) 范围内的元素进行排序范围内排序，不包括 last 所以要在下一个待排序元素的下标 i + 1 基础上再 + 1。

以前都是 (a, a + n) 直接 + n 的，忽略了这样用的真正原因是什么。

同时这里还学到，当有某些部分不理解的时候，需要将这部分里面的细节拆开理解。比如前面的 sort 里有一个 i，当时不理解这个 i 是干什么的。所以就用了 cout 将这个 i 及其它对应的元素打印出来。这才知道这个东西在这里具有什么意义。

int k = 1, flag = 1;

k 是每次归并排序时，组的元素的个数，初始化为 1每一次进入循环时会对组的个数加倍。加倍后再进行归并和排序。

k *= 2;

for(i = 0; i < n; i++)
	if(a[i] != b[i])
		flag = 1;

flag用来标记是否进行下一次循环，初始时设为1进入第一次循环，然后进入后初始化为 flag = 0，如果可以判断为当前序列已经与中间序列 b[] 相等，那么就不需要设 flag = 1，即不再进行下一次循环。本循环再排序迭代一次即结束。

for(i = 0; i < n / k; i++)
	sort(a + i * k, a + (i + 1) * k);
sort(a + n / k * k, a + n);

这代码里面出现两次 n / k ，而因为 n 和 k 都是整数所以 n / k 的结果会向下取正。比如 n = 10，k = 3时，n / k = 3。

如果当最后一个组非 k 倍数时，比如上面的情况，那么 for 循环会对前面整的组进行归并和排序，而留下最后一个组单独 sort 排序。

而单独 sort 排序的话同样有 n / k 并且还 * k，但同样因为整型除法的向下取正，所以这里的结果就是最后的组的首元素位置 n / k * k = 9。

当最后一个组为 k 倍数时，比如 n = 9， k = 3。那么 for 循环刚好把三个组排序，而单独的 sort 因为 n / k * k = 9， n = 9，所以只是对单一元素处理，不会导致其他的结果。

参考代码

参考理解

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, a[100], b[100], i, j;
	cin >> n;
	for(i = 0; i < n; i++)
		cin >> a[i];
	for(i = 0; i < n; i++)
		cin >> b[i];
	// 判断是否是插入排序 
	for(i = 0; i < n && b[i] <= b[i+1]; i++);
	for(j = i + 1; j < n && a[j] == b[j]; 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 *= 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; i++)
		cout << (i ? " " : "") << a[i];
}

1035 插入与归并 (25 point(s))

原文：https://www.cnblogs.com/Atl212/p/15206011.html