#include<iostream>
#include<algorithm>
using namespace std;
int ori[110], temp[110], ans[110], n;
void show(int a[])
{
for (int i = 0; i < n; i++)
{
printf("%d", a[i]);
if (i != n - 1)printf(" ");
}
}
bool issame(int a[])
{
for (int i = 0; i < n; i++)
{
if (a[i] != ans[i])return false;
}
return true;
}
bool isInsert(int a[])
{
bool flag = false;
for (int i = 1; i < n; i++)
{
if (i != 1 && issame(a))
{
flag = true;
}
int num = a[i], j;
for (j = i-1;j>=0;j--)
{
if (num < a[j])a[j + 1] = a[j];
else break;
}
a[++j] = num;
if (flag)return true;
}
return false;
}
void Mergesort(int a[])
{
bool flag = false;
for (int step = 2; step / 2 <= n; step*=2)
{
if(step!=1&&issame(a))
{
flag = true;
}
for (int i = 0; i < n; i += step)
{
sort(a + i, a + min(i + step, n));
}
if (flag)break;
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &ori[i]);
temp[i] = ori[i];
}
for (int i = 0; i < n; i++)scanf("%d", &ans[i]);
if (isInsert(ori))
{
printf("Insertion Sort\n");
show(ori);
}
else
{
printf("Merge Sort\n");
Mergesort(temp);
show(temp);
}
return 0;
}
1089 Insert or Merge（25 分）
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- PAT-A，题目地址：https://www.patest.cn/contests/pat-a-practise/...
- 插入排序直接用sort即可，第一次的插入排序是前两个元素（因为插入排序是手里先拿着第一个，后序的往里面插入）堆排序...
- 策略模式 一个功能的效果,有不同的算法与策略,根据不同的选择选择不同的结果。 简单来说,只要你写过程序就用过策略模...
