PAT-1025.插入与归并（25）

#include<iostream>

#include<algorithm>

using namespace std;

int N;

int inser(int i,int A[],int B[]);

int main()

{

  int A[100],B[100],C[100];

  int i,j,k,temp; 

  cin>>N;

  for(i=0;i<N;i++)

  {cin>>A[i];C[i]=A[i];}

  for(i=0;i<N;i++)

 cin>>B[i];

  for(i=1;i<N;i++)

  {

sort(A,A+i);

 if(inser(i,A,B))

 {

cout<<"Insertion Sort"<<endl;

 for(j=0;j<N-1;j++)

       cout<<A[j]<<" ";

     cout<<A[j];

 break;

 }

  }

  if(i==N&&N!=0)

  {

 cout<<"Merge Sort"<<endl;

 temp=2;

 while(1)

 {

 for(i=0;i<N;i=i+temp)

 {

     if(i+temp<=N)

 sort(C+i,C+i+temp);

 else

 {sort(C+i,C+N);break;}

 }

    temp*=2;

for(j=0;j<N;j++)

if(C[j]!=B[j])

break;

if(j==N)

{

for(i=0;i<N;i=i+temp)

{

if(i+temp<=N)

sort(C+i,C+i+temp);

else

{sort(C+i,C+N);break;}

}

for(i=0;i<N-1;i++)

cout<<C[i]<<" ";

cout<<C[i];

break;

}

 } 

  }

return 0;

}

int inser(int i,int A[],int B[])

{

int j;

for(j=0;j<N;j++)

if(A[j]!=B[j])

break;

if(j==N)

{

i++;

  sort(A,A+i);

inser(i,A,B);

return 1;

}

return 0;

}

将数组先分步进行插入排序，若产生的新数组和输入的样例数组相同，则在进行一步插入排序，输出数组。当排序完全之后还是无法和样例匹配上则为归并排序。

归并排序要特别注意数组最后一段的归并，若是比此时要归并的数段小，则将剩下的全排，不分类判断的话会有可能造成数组越界导致段错误。