题目:
根据维基百科的定义:
插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作:首先将原始序列看成 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
思路:
本题的关键在于找到 归并排序 和 插入排序 的迭代过程中数列的变化规律。(具体思路仔细阅读代码)
把握好输入的两行数列(初始状态,排序的中间状态)的关系
代码:
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int A[105],B[105],C[105]; int main(){ int n,k,h; cin>>n; for(int i=0; i<n; i++){ scanf("%d",&A[i]); } for(int i=0; i<n; i++){ scanf("%d",&B[i]); } for(k=0; k<n && B[k]<=B[k+1]; k++); for(h=k+1; h<n && A[h]==B[h]; h++); if(h == n){ cout<<"Insertion Sort"<<endl; if(k+2 <= n){ sort(A,A+k+2); }else{ sort(A,A+n); } }else{ cout<<"Merge Sort"<<endl; int w=1,flag=1; while(flag){ flag = 0; for(int i=0; i<n; i++){ if(A[i] != B[i]){ flag = 1; } } w = w * 2; for(int i=0; i<n/w; i++){ sort(A+i*w, A+i*w+w); } sort(A+n/w*w,A+n); } } for(int i=0; i<n; i++){ if(i!=0){ printf(" "); } printf("%d",A[i]); } return 0; }
标签:归并,迭代,插入,算法,序列,排序,输入,1035 From: https://www.cnblogs.com/yccy/p/16839200.html