插入与归并(PAT)

1.题目描述:

根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。

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

2.输入描述:

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

3.输出描述:

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

4.输入例子:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

5.输出例子:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

6.解题思路:

1. 做这道题我们首先要会《插入排序》和《归并排序》俩种排序算法
(不知道这两种排序的可以单独学习，注意该题要用的是迭代法而不是递归方法)；
>2. 然后我们只需要在两种排序中的每一轮次排序中加入判断；
3. 判断每一轮次所排序后的序列是否产生了用例中所给出的中间序列
4. 最后在下一轮排序后输出该轮次的序列
(最后要注意的是测试用例中有一例关于插入排序的问题)

10
3 1 2 8 7 5 9 4 6 0
1 2 3 5 7 8 9 4 6 0
//正确输出
Insertion Sort
1 2 3 4 5 7 8 9 6 0
//错误输出
Insertion Sort
1 2 3 5 7 8 9 4 6 0

错误原因：当我们查找到中间序列时，我们就输出它的下一轮排序后的序列，但是我们发现它的下一轮排序后的序列并未发生改变，因为下一轮排序乃至后面的几轮过程中，我们所要排序的那一部分序列本身就是已经排好循序了的，如下为该用例排序过程：

初始：    3 (1) 2  8  7  5  9  4  6  0
第一轮：  1  3 (2) 8  7  5  9  4  6  0
第二轮：  1  2  3 (8) 7  5  9  4  6  0
第三轮：  1  2  3  8 (7) 5  9  4  6  0
第四轮：  1  2  3  7  8 (5) 9  4  6  0
第五轮：  1  2  3  5  7  8 (9) 4  6  0//中间序列
第六轮：  1  2  3  5  7  8  9 (4) 6  0//该轮次与第五轮序列重复轮空，错误答案
第七轮：  1  2  3  4  5  7  8  9 (6) 0//正确答案
....

7.源代码:

#include<stdio.h>
#include<stdlib.h> 
int main()
{
	int i,j,k,m,n=0,N;
	int	*Init_list1,*Init_list2,*Mid_list,temp;
	scanf("%d",&N);//序列大小
	Init_list1=(int*)malloc(N*(sizeof(int)));//初始序列1-插入排序
	Init_list2=(int*)malloc(N*(sizeof(int)));//初始序列2-归并排序
	Mid_list=(int*)malloc(N*(sizeof(int)));//中间序列 
	for(i=0;i<N;i++)
		scanf("%d",&Init_list1[i]);//输入初始序列1
	for(i=0;i<N;i++)
		scanf("%d",&Mid_list[i]);//输入中间序列
	for(i=0;i<N;i++)
		Init_list2[i]=Init_list1[i];//复制初始序列1->初始序列2

	
	for(i=1;i<N;i++)//插入排序
	{
		m=0;
		for(k=0;k<N;k++)//遍历序列1和中间序列
			if(Init_list1[k]!=Mid_list[k])
			{
				m=1;//判断序列1和中间序列是否相等
				break;
			}
		if(m==0)
			n=1;//中间序列存在
		//单轮次 插入排序
		temp=Init_list1[i];
		j=i-1;
		while(temp<Init_list1[j])
		{
			Init_list1[j+1]=Init_list1[j];
			j--;
		}
		Init_list1[j+1]=temp;
		//输出部分
		if(n==1&&j<i-1)//(m==0)确定中间序列存在
		{//(j<i-1)确定中间序列后的序列不轮空，即序列发生了位置交换
			printf("Insertion Sort\n");
			for(k=0;k<N;k++)//输出排序后的序列1
				printf("%d ",Init_list1[k]);
			break;
		}
	}
	
	int L_start=0,L_end=0;
	int R_start=0,R_end=0;
	int *sort_arr;	
	sort_arr=(int*)malloc(N*(sizeof(int)));
	for(i=1;i<N;i*=2)//归并排序
	{
		n=0;
		for(k=0;k<N;k++)//同理
			if(Init_list2[k]!=Mid_list[k])
			{
				n=1;
				break;
			}
		//单轮次 归并排序
		for(L_start=0;L_start<N-i;L_start=R_end)
		{
			L_end=L_start+i;
			R_start=L_start+i;
			R_end=R_start+i;
			if(R_end>N)
				R_end=N;
			k=0;
			while( L_start < L_end && R_start < R_end)
				if(Init_list2[L_start]<Init_list2[R_start])
					sort_arr[k++]=Init_list2[L_start++];
				else
					sort_arr[k++]=Init_list2[R_start++];
			while(L_start<L_end)
				sort_arr[k++]=Init_list2[L_start++];

			while(k>0)
				Init_list2[--R_start]=sort_arr[--k];
			
		}
		//输出部分
		if(n==0)
		{
			printf("Merge Sort\n");
			for(k=0;k<N;k++)
				printf("%d ",Init_list2[k]);
			break;
		}	
	}
	return 0;
}