1035 插入与归并 (25分)
根据维基百科的定义:
插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作:首先将原始序列看成 N 个只包含 1 个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法?
输入在第一行给出正整数 N (≤100);随后一行给出原始序列的 N 个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
首先在第 1 行中输出Insertion Sort
表示插入排序、或Merge Sort
表示归并排序;然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行首尾不得有多余空格。
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Insertion Sort
1 2 3 5 7 8 9 4 6 0
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
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;
}
原文:https://www.cnblogs.com/bigageyuan/p/13908374.html