1035 插入与归并
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
输入样例 1：
103 1 2 8 7 5 9 4 6 01 2 3 7 8 5 9 4 6 0
输出样例 1：
Insertion Sort1 2 3 5 7 8 9 4 6 0
输入样例 2：
103 1 2 8 7 5 9 4 0 61 3 2 8 5 7 4 9 0 6
输出样例 2：
Merge Sort1 2 3 8 4 5 7 9 0 6 题解：这道题看上去是考插入排序和归并排序，但是其实根据题目意思，只要稍微了解这两个算法，就完全能做出来了。 插入排序如题目所说是一个一个插入，所以如果是使用插入排序的数据，一定是前面有序，后面无序的。 归并排序则是先将相邻两组进行排序，完成后，再将相邻两组进行排序，直到将整个数列规整为一组。，使用归并排序的数据，一定是前n个有序，中间n个有序，后n个有序。 这道题目判断是插入排序还是归并排序的方法有许多，我采用的是从无序的第一个元素开始，与初始元素对比，若存在和初始元素不一样的，则是归并排序，否则是插入排序。。 这道题的一个坑点在于，在判断为归并排序后，不能直接进行下一步操作，必须重新计算。 代码如下：
1 #include2 #include 3 using namespace std; 4 int a[105], b[105], c[105]; 5 int main() 6 { 7 int n, j, temp = 0; 8 bool flag = true; 9 scanf("%d",&n);10 for(int i = 0; i < n; i++){11 scanf("%d",&a[i]);12 }13 for(int i = 0; i < n; i++){14 scanf("%d",&b[i]);15 c[i] = b[i];16 }17 temp = b[0];18 for( j = 0; j < n; j++){19 if(temp <= b[j])20 temp = b[j];21 else{22 temp = j;23 break; 24 }25 } 26 for( int k = temp+1; k < n; k++){27 if(b[k] != a[k]){28 flag = true;29 break;30 }31 if( k == n-1)32 flag = false;33 }34 if(flag){35 printf("Merge Sort\n");//不能直接归并，必须重新计算 36 temp = 1;37 bool flag3 = 1;38 while(flag3){39 flag3 = 0;40 for(int i = 0; i < n; i++){41 if( a[i] != b[i] ){42 flag3 = 1;43 break;44 }45 }46 temp *= 2;47 for( int i = 0; i < n; i+=temp){48 if(i+temp < n)49 sort(a+i,a+i+temp);50 else51 sort(a+i,a+n);52 }53 }54 }55 else{56 sort(a,a+temp+1);57 printf("Insertion Sort\n");58 }59 bool flag2 = false;60 for( int i = 0; i < n; i++){61 if(!flag2)62 flag2 = true;63 else64 printf(" ");65 printf("%d",a[i]); 66 }67 return 0;68 }