1089. Insert or Merge -25[插入和归并排序]

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1089

2. 思路：

3. 源码：

#include<iostream>#include<algorithm>//使用sort函数#include<vector>using namespace std;int N;//元素数目vector<int> ini;//初始序列vector<int> jud;//待判断序列int isInsert();//判断是否插入排序，若是，进行下一步排序void merge();//归并序列void print();//输出结果int main(void){	//freopen("in.txt", "r", stdin);	cin >> N;	ini.resize(N);//重定义容器大小	jud.resize(N);	for (int i = 0; i < N; i++)		cin >> ini[i];	for (int i = 0; i < N; i++)		cin >> jud[i];	if (isInsert() == 1)//是插入排序		return 0;	else		merge();//归并	return 0;}int isInsert()//判断是否插入排序，若是，进行下一步排序{	int pos;	for (pos = 0; jud[pos] <= jud[pos + 1]; pos++);//求出无序元素的位置	pos += 1;		for (int i = pos; i < N; i++)//判断后面的元素是否和待判断的一致。若是，则为插入	{		if (ini[i] != jud[i])			return 0;	}	cout << "Insertion Sort/n";	sort(ini.begin(), ini.begin() + pos + 1);//直接用的sort排序。可以自己写插入算法	print();	return 1;}void merge()//归并序列{	int k = 2, flag = 1;//分别为归并段的元素数， 两序列是否相等的标记	while (flag == 1)//1为不等，继续处理	{		flag = 0;		for (int j = 0; j < N; j++)		{			if (ini[j] != jud[j])			{				flag = 1;				break;			}		}		vector<int>::iterator it = ini.begin();		int i;		for (i = k; i <= N; i += k)//用sort对每个归并段排序，可以自己写merge算法			sort(it + i - k, it + i);		if ((i -= k) < N)			sort(it + i, ini.end());//处理多余的		k <<= 1;//归并段数*2	}	cout << "Merge Sort/n";	print();	return;}void print()//输出结果{	for (int i = 0; i < N; i++)	{		if (i == 0)			cout << ini[i];		else			cout << ' ' << ini[i];	}	cout << endl;}