首页 > 其他 > 详细

1035 插入与归并 (25分)

时间:2020-11-01 09:54:41      阅读:24      评论:0      收藏:0      [点我收藏+]
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;
}

1035 插入与归并 (25分)

原文:https://www.cnblogs.com/bigageyuan/p/13908374.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!