题目描述
根据维基百科:
插入排序迭代,每次将一个插入元素插入到排好序的输出序列中,每次迭代插入排序都会从输入数据中移除一个元素,并在已排好序的序列中找到它所属的位置,然后将其插入。直到没有输入元素剩余为止。
归并排序的工作方式如下:将未排序的序列划分为 N 个子序列,每个子序列包含 1 个元素(将 1 个元素的序列视为已排序)。然后重复合并两个相邻的子序列以产生新的排序子序列,直到仅剩 1 个子序列为止。
现在,给定初始序列,以及经过某种排序方法多次迭代后的序列,请你判断我们使用的哪一种排序方法。
输出格式
第一行输出 Insertion Sort 或 Merge Sort,以指明所采用的具体排序方法。
运用此方法再进行一次迭代,并在第二行输出本次迭代后的序列。
数据保证答案唯一。
样例
输入样例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
算法
分析:先将i指向中间序列中满⾜从左到右是从⼩到⼤顺序的最后⼀个下标,再将j指向从i+1开始,第
⼀个不满⾜a[j] == b[j]的下标,
如果j顺利到达了下标n,说明是插⼊排序,再下⼀次的序列是sort(a, a+i+2);否则说明是归并排序。归并
排序就别考虑中间序列了,直接对原来的序列进⾏模拟归并时候的归并过程,i从0到n/k,每次⼀段段
得sort(a + i * k, a + (i + 1) * k);最后别忘记还有最后剩余部分的sort(a + n / k * k, a + n);这样是⼀次归并的
过程。直到有⼀次发现a的顺序和b的顺序相同,则再归并⼀次,然后退出循环~
注意:⼀开始第三个测试点⼀直不过,天真的我以为可以模拟⼀遍归并的过程然后在过程中判断下⼀
步是什么。。然⽽真正的归并算法它是⼀个递归过程。。也就是先排左边⼀半,把左边的完全排列成
正确的顺序之后,再排右边⼀半的。。⽽不是左右两边⼀起排列的。。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],b[N];
int main() {
int n, i, j;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++); //寻找递增序列的最后一个位置
for (j = i + 1; a[j] == b[j] && j < n; j++); //从递增序列的下一个位置开始对比剩余序列与原序列,如果不等则结束遍历
if (j == n) { //如果能遍历到数组的最后一个位置,则说明是插入排序
cout << "Insertion Sort" << endl;
sort(a, a + i + 2); } //排序原数组的增序列
else{
int k=1,flag=1;
cout<<"Merge Sort"<<endl;
while(flag) //如果匹配成功则多排一次
{
flag=0;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i])
flag=1;
}
int len=1<<k;
for(int i=0;i<n;i+=len)
sort(a+i,a+min(n,i+len));
k++;
}
}
for (i = 0; i < n; i++) {
if (i != 0) printf(" ");
printf("%d", a[i]);
}
return 0;
}