1035 插入与归并 (25分)
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
输入样例 1：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
输出样例 1：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
输入样例 2：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
输出样例 2：
Merge Sort 1 2 3 8 4 5 7 9 0 6
思路：
初始数组-----a 中间数组-----b 初始数组副本-----c
一、判断直插还是归并
1.首先找到直插和归并的不同，我找的是直插b的倒数元素与a的倒数元素必然相同
2.按照上述规律进行判断，首先判断b倒数元素与a倒数元素，找到其首个不同的元素的下标n并记为n_p，然后将c的前n个元素升序排列，并将a与c的前n个元素进行比较
3.若比较结果完全相同则判定为直插
4.补充：直插有一个特殊情况，即a与b完全相同，此时要直接去找所要操作的那个数组元素下标n_p
二、直插操作
找到所要操作的数组下标进行直插并输出
三、归并操作
因为不知道是几路归并，但知道N<=100，因此采用笨办法，将a先2路归并再4路归并再8路归并......，每次归并完后与b比较，若相同，则在进行一次归并即可。
首次通过代码:
1 #include<stdio.h> 2 //对数组[begin,end]区间进行直接插入排序 3 void Sort(int *c,int begin,int end){ 4 if(begin==end) return ; 5 for(int i=begin+1;i<=end;i++){ 6 for(int j=i;j>begin;j--){ //出错点2：j>begin写成j>0 7 if(c[j]<c[j-1]) { 8 int swap; 9 swap=c[j]; 10 c[j]=c[j-1]; 11 c[j-1]=swap; 12 } 13 else break; 14 } 15 } 16 } 17 //直接插入排序 18 void Insertion_Sort(int *a,int n_p,int sum){ 19 printf("Insertion Sort "); 20 //if(sum>1) 21 for(int i=n_p;i>=1;i--){ 22 if(a[i]<a[i-1]){ 23 int c; 24 c=a[i]; 25 a[i]=a[i-1]; 26 a[i-1]=c;//出错点1：a[i-1]写成a[i] 27 } 28 else break; 29 } 30 for(int i=0;i<sum;i++) { 31 printf("%d",a[i]); 32 if(i!=sum-1) printf(" "); 33 } 34 } 35 //归并排序 36 void Merge_Sort(int *a,int *b,int sum){ 37 printf("Merge Sort "); 38 int x=1;int flag=1; 39 for(int i=1;i<10;i++){ 40 x*=2;flag=1; 41 for(int j=0;;j+=x){ 42 if(j+x<=sum) 43 Sort(a,j,j+x-1); 44 else { 45 Sort(a,j,sum-1); 46 break; 47 } 48 } 49 for(int j=0;j<sum;j++){ 50 if(a[j]!=b[j]) { 51 flag=0;break; 52 } 53 } 54 if(flag) i=8; 55 } 56 for(int i=0;i<sum;i++){ 57 printf("%d",a[i]); 58 if(i!=sum-1) printf(" "); 59 } 60 } 61 int main(){ 62 int sum; 63 int n_p=1; 64 int a[101]; 65 int b[101]; 66 int c[101]; 67 scanf("%d",&sum); 68 //输入原始序列 69 for(int i=0;i<sum;i++){ 70 scanf("%d",&a[i]); 71 c[i]=a[i]; 72 } 73 //输入所给排序后的序列 74 for(int i=0;i<sum;i++){ 75 scanf("%d",&b[i]); 76 } 77 //将数组b前面序列与数组c比较，后面序列与数组a比较（符合直接插入排序的特征） 78 int flag1=1;//1为与数组a比较，0为与数组c比较 79 for(int i=sum-1;i>=0;i--){ 80 //先与有序数组c进行比较直到找到第一个不匹配的数组下标 81 if(flag1){ 82 if(b[i]!=a[i]){ 83 n_p=i+1; 84 flag1=0; 85 Sort(c,0,i); 86 i++; 87 } 88 } 89 //然后与初始数组a进行比较 90 else { 91 if(b[i]!=c[i]) { 92 Merge_Sort(a,b,sum); 93 return 0; 94 } 95 } 96 } 97 //错误点3：特殊情况：原始序列与排序后序列完全相同，此时需要找到直接插入排序的位置 98 if(flag1) 99 for(int i=0;i<sum;i++){ 100 if(b[i]>b[i+1]){ 101 n_p=i+1;break; 102 } 103 } 104 //上述比较全部满足则一定是直接插入排序 105 Insertion_Sort(b,n_p,sum); 106 return 0; 107 }