[数据结构与算法]PTA (乙级）1035 插入与归并 (25 分)

简单概括下题目意思，给定初始数组，在经过若干次排序后，判断该排序方式是插入或者是归并，并且输出下一次排序的结果。
解题思路：
因为插入排序相对与归并更好判断，所以先判断是否是插入排序
判断方法如下：因为插入排序后半部分是不变的，假设数组在下标为$i$的时候开始无序，那么从这个地方开始判断后半部分是否相同，如果后半部分相同，则是插入排序，否则是归并排序。归并排序需要知道当前归并子列的长度，通过判断子列间的有序型得出子列长度

原数组
4 2 1 3 13 14 12 11 8 9 7 6 10 5
排序后数组
1 2 3 4 11 12 13 14 6 7 8 9 5 10
通过前面的判断，该排序方式为归并排序，因为进行过若干次排序，则初始子列长度$\ge$ 2，则判断相邻子列的有序性，如2-3，跳过2*长度，12-13.以此类推，如果都满足有序，则将子列长度乘以2，直到条件不满足为止
AC代码如下

#include<cstdio>
using namespace std;
int a[110],b[110];
void Merge(int b[],int a[],int L,int R,int RightEnd) //归并排序
{
	int leftEnd=R-1;
	int Tmp=L;
	int start=L;
	while(L<=leftEnd&&R<=RightEnd)
	{
		if(b[L]<b[R]) a[Tmp++]=b[L++];
		else a[Tmp++]=b[R++];
	}
	while(L<=leftEnd) a[Tmp++]=b[L++];
	while(R<=RightEnd) a[Tmp++]=b[R++];
}
void Travers(int a[],int n)	//输出数组
{
	for(int i=0;i<n;i++)
	{
	printf("%d",a[i]);
	if(i!=n-1) printf(" ");
	}
	
}
int main()
{
	int n,p,p2;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	for(int j=0;j<n;j++)
	scanf("%d",&b[j]);
	for(int i=1;i<n;i++)		//判断无序开始的位置
	{
		if(b[i]>=b[i-1]) continue;	//坑，没有等于号则测试点4无法通过
		else 
		{
		p=i;
		break;
		}
	}
	p2=p;
	while(p2<n)		//判断后续数组是否相同，
	{
		if(a[p2]==b[p2]) 
		{
			p2++;
		}
		else break;
	}
	if(p2==n)	//如果相同，那么是插入排序
	{
		printf("Insertion Sort\n");
		int j,Tmp=b[p];
		for(j=p;j>0&&b[j-1]>Tmp;j--)
		{
			b[j]=b[j-1];
		}
		b[j]=Tmp;
		Travers(b,n);
	}
	else{		//否则是归并排序
		printf("Merge Sort\n");
		bool flag=true;
		int length,k;
		for(length=2;length<=n;length*=2)
		{
			k=length;
			while(k<n)
			{
				if(b[k-1]<b[k])
				{
					k+=2*length;
				}else{
					flag=false;
					break;
				}
			}
			if(!flag) break;
		}		
		int i;
		for(i=0;i<=n-2*length;i+=length*2)
		{
			Merge(b,a,i,i+length,i+length*2-1);
		}
		if(i+length<n) Merge(b,a,i,i+length,n-1);
		else for(int j=i;j<n;j++) a[j]=b[j];
		Travers(a,n);
	}
	return 0;
}