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



代码讲解:这题值得深思熟虑一下，这题的数据范围很小，当然你可以把归并和插入排序都写出来，像我例子一一样，但是用c写起来
特别的麻烦，考场上极容易写错，第二种就是用排序函数去模拟她们，代码量会减少很多，不容易出错


#include<stdio.h>                              //排序和归并都写了出来，相当费劲。。。考试中估计。。不推荐
int compare(int a[],int b[],int n)
{
 int i;
 for(i=0;i<n;i++)
 {
  if(a[i]!=b[i])
  return 0;
 }
 return 1;
 
}
void sort(int *a,int a_len,int *b,int b_len)
{
 int i,j;
 int m[a_len];
 int n[b_len];
 for(i=0;i<a_len;i++)
 {
  m[i]=a[i];
  
 }
 for(i=0;i<b_len;i++)
 {
  n[i]=b[i];
 }
 int count=0;
 for(i=0,j=0;i<a_len&&j<b_len;)
 {
  if(m[i]>n[j])
  {
   a[count++]=n[j++];   
  }
  else
  {
   a[count++]=m[i++];
  }
 }
 while(i<a_len)a[count++]=m[i++];
 while(j<b_len)a[count++]=n[j++];
 
}
void merge(int a[],int k,int n)
{
     int start_a=0,start_b,end_a=k,end_b; 
     int i;
        while(end_a<n)
        {
        start_b=start_a+k;
        end_b=start_b+k-1;
        if(end_b>n-1)
        end_b=n-1;
      sort(a+start_a,k,a+start_b,end_b-start_b+1);
      start_a=end_b+1;
  end_a=start_a+k-1;
     }
 
}
int main()
{
 int n;
 scanf("%d",&n);
 int a[n];
 int b[n];
 int c[n];
 int i,j;
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);
  c[i]=a[i];
 }
 for(i=0;i<n;i++)
 {
  scanf("%d",b+i);
 }
 int t=0,temp;
    for(i=1;i<n;i++)
    {
     temp=a[i];
     for(j=i-1;j>=0&&a[j]>temp;j--)
     a[j+1]=a[j];
     a[j+1]=temp;
     if(compare(a,b,n))
     {
     t=1;
        } 
  if(t)
  {
  printf("Insertion Sort\n");
  temp=b[i+1];
  for(;i>=0&&b[i]>temp;i--)
  {
   b[i+1]=b[i];
  }
  b[i+1]=temp;
  break; 
   }
    
 }
   if(t==0) 
 {
  printf("Merge Sort\n");
    
  int len=1;
  for(i=1;i<n;i=i*2)
  {
  merge(c,i,n);
  if(compare(c,b,n))
  {
   merge(b,i*2,n);
   break;
     }
     }
  
 }
 for(i=0;i<n;i++)
 {
  if(i!=n-1)
  printf("%d ",b[i]);
  else
  printf("%d\n",b[i]);
 }
 return 0;
}


版本二用排序模拟:

#include<stdio.h>
#include<stdlib.h>
int compare(int a[],int b[],int n)
{
 int i;
 for(i=0;i<n;i++)
 {
  if(a[i]!=b[i])
  return 0;
 }
 return 1;
 
}
int cmp(const void *a,const void *b)
{
 return *(int *)a-*(int *)b;
 } 
int main()
{
 int n;
 scanf("%d",&n);
 int a[n];
 int b[n];
 int c[n];
 int i,j;
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);
  c[i]=a[i];
 }
 for(i=0;i<n;i++)
 {
  scanf("%d",b+i);
 }
 int t=0,temp;
    for(i=1;i<n;i++)
    {
     qsort(a,i+1,sizeof(int),cmp);
     if(compare(a,b,n))
     {
     t=1;
        } 
  if(t)
  {
  printf("Insertion Sort\n");
     qsort(b,i+2,sizeof(int),cmp);
  break; 
   }   
 }
   if(t==0) 
 {
  printf("Merge Sort\n");  
  int count;
  for(i=2;i<=n;i=i*2)
  {
  count=n/i;
  for(j=0;j<count;j++)
  qsort(c+j*i,i,sizeof(int),cmp);
  if(j*i<n)
  qsort(c+j*i,n-j*i,sizeof(int),cmp);
  if(compare(c,b,n))
  {
   i=i*2;
       count=n/i;
      for(j=0;j<count;j++)
     qsort(b+j*i,i,sizeof(int),cmp);
      if(j*i<n)
     qsort(b+j*i,n-j*i,sizeof(int),cmp);
   break;
     }
     } 
 }
 for(i=0;i<n;i++)
 {
  if(i!=n-1)
  printf("%d ",b[i]);
  else
  printf("%d\n",b[i]);
 }
 return 0;
}