PAT 甲级1089 原题链接 以下是过不了测试点4的代码。非常冗长，仅用以指出错误的地方，精简后的代码见最下。
#include<stdio.h> #include<algorithm> using namespace std; int num1[110],num2[110],num3[100]; void func(int arr[],int left1,int right1,int left2,int right2){ int i=left1,j=left2; int temp[110],index=0; while(i<=right1 && j<=right2){ if(arr[i]<=arr[j]) temp[index++]=arr[i++]; else temp[index++]=arr[j++]; } while(i<=right1) temp[index++]=arr[i++]; while(j<=right2) temp[index++]=arr[j++]; for(i=0;i<index;i++) arr[i+left1]=temp[i]; } int main(){ int n,i,k,j; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&num1[i]); } for(i=0;i<n;i++){ scanf("%d",&num2[i]); } i=0; while(i<n && num2[i]<num2[i+1]) i++;//问题在这里！仅仅用<判断足够吗？NO！请看下面的测试数据； k=i+1; for(i=k;i<n;i++){ if(num1[i]!=num2[i]) break; } if(i==n){ printf("Insertion Sort\n"); for(i=0;i<n && num2[i]<num2[k];i++) num3[i]=num2[i]; num3[i]=num2[k]; for(;i<k;i++) num3[i+1]=num2[i]; for(i+=1;i<n;i++) num3[i]=num2[i]; for(i=0;i<n;i++){ if(i<n-1) printf("%d ",num3[i]); else printf("%d\n",num3[i]); } } else{ printf("Merge Sort\n"); int step,flag=0; for(step=2;step/2<=n;step*=2){ for(i=0;i<n;i+=step){ int mid=i+step/2-1; if((mid+1)<=(n-1)){ func(num1,i,mid,mid+1,min(i+step-1,n-1)); } } if(flag==0){ for(i=0;i<n;i++){ if(num2[i]!=num1[i]) break; } if(i==n) flag=1; } else break; } for(i=0;i<n;i++){ if(i<n-1) printf("%d ",num1[i]); else printf("%d\n",num1[i]); } } return 0; }测试数据： 7 3 2 4 3 7 8 6 2 3 3 4 7 8 6 当原数列中有重复数据时，升序意味着前一个数 <= 后一个数； 同时，用sort函数对插入和归并进行简化，AC代码：
#include<stdio.h> #include<algorithm> using namespace std; int num1[110],num2[110]; int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&num1[i]); } for(i=0;i<n;i++){ scanf("%d",&num2[i]); } for(i=0;i<n-1 && num2[i]<=num2[i+1];i++); for(j=i+1;j<n && num1[j]==num2[j];j++); if(j==n){ printf("Insertion Sort\n"); sort(num1,num1+i+2); } else{ printf("Merge Sort\n"); int step,flag=0;//flag判断该次归并后的数列是否与中间数列等同 for(step=2;step/2<=n;step*=2){ for(i=0;i<n;i+=step){ sort(num1+i,num1+min(i+step,n)); } if(flag==0){ for(i=0;i<n;i++){ if(num2[i]!=num1[i]) break; } if(i==n) flag=1;//该次结果与中间数列等同，再进行一次归并后退出 } else break; } } for(i = 0; i < n; i++) { if(i < n - 1) printf("%d ", num1[i]); else printf("%d\n", num1[i]); } return 0; }