插入还是归并
-
这道题判断插入还是跟上一题相同。判断归并方法如下:
-
归并的第一步排序的步长为 $2$ ,之后第 $n$ 次为 $2^n$ 。因此可以先按照步长为2的来做,如果和结果不匹配,则翻倍步长, 直到发现
origin
和after
完全匹配为止。 -
代码如下
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 110;
int n;
int origin[N], after[N];
bool check()
{
for (int i = 0; i < n; i ++ )
if (origin[i] != after[i])
return false;
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> origin[i];
for (int i = 0; i < n; i ++ ) cin >> after[i];
int p = 1;
while (p < n && after[p] >= after[p - 1]) p ++ ;
int k = p;
while (p < n && origin[p] == after[p]) p ++ ;
if (p == n)
{
cout << "Insertion Sort" << endl;
sort(after, after + k + 1);
cout << after[0];
for (int i = 1; i < n; i ++ ) cout << " " << after[i];
}
else
{
cout << "Merge Sort" << endl;
k = 1; // 用来指示2^k
bool flag = false;
while (1)
{
int len = 1 << k;
for (int i = 0; i < n; i += len)
{
int l = i;
int r = min(n, i + len);
sort(origin + l, origin + r);
}
if (flag) break;
if (check()) flag = true;
k ++ ;
}
cout << origin[0];
for (int i = 1; i < n; i ++ ) cout << " " << origin[i];
}
return 0;
}