插入与归并(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. 做这道题我们首先要会《插入排序》和《归并排序》俩种排序算法
<mark>(不知道这两种排序的可以单独学习，注意该题要用的是迭代法而不是递归方法)</mark>；
>2. 然后我们只需要在两种排序中的每一轮次排序中加入判断；
3. 判断每一轮次所排序后的序列是否产生了用例中所给出的中间序列
4. 最后在下一轮排序后输出该轮次的序列
<mark>(最后要注意的是测试用例中有一例关于插入排序的问题)</mark>
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
<mark>错误原因：当我们查找到中间序列时，我们就输出它的下一轮排序后的序列，但是我们发现它的下一轮排序后的序列并未发生改变，因为下一轮排序乃至后面的几轮过程中，我们所要排序的那一部分序列本身就是已经排好循序了的，如下为该用例排序过程：</mark>
初始： 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;
}
