首页 > 其他 > 详细

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

时间:2021-09-02 00:42:56      阅读:14      评论:0      收藏:0      [点我收藏+]

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

技术分享图片

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

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!