根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 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解题思路：
两种排序详见：插入排序（Insertion_sort）,归并排序（Merge_sort）
写了一整天，一大坨100多行终于过了
首先使insertion_sort，只要设置一个bool参数和begin位置，进行排序一次后用参数跳出并更新开始位置即可
bool temp = true;
void Insertion_sort(int *arr,int begin,int size)
{
int i,j;
for(i = begin;i < size && temp;++i)//第一个元素不用排序
{
int t = arr[i];
for(j = i-1;j >= 0 && arr[j] > t;--j)
{
arr[j+1] = arr[j];//直接覆盖，速度更快（将前一个覆盖到后面）
}
::temp = false;
arr[j+1] = t;//因为是覆盖，所以要最后赋值
}
::temp = true;
}而Merge_sort就需要模拟了，因为他的常用的实现方法是用递归，不好暂停后进行下一步，所以用模拟的方法更好实现，当然也是一大坨
//模拟merge
int num = 2;
while(is_unsort(try2,n))
{
i = 0;
while(i+num < n)
{
sort(try2 + i,try2 + i + num);
i += num;
}
while(i < n)
{
sort(try2 + i,try2 + n);
i += num;
}
num *= 2;
if(is_func(try2,arrb,n))
{
cout << "Merge Sort\n";
i = 0;
while(i+num < n)
{
sort(try2 + i,try2 + i + num);
i += num;
}
while(i < n)
{
sort(try2 + i,try2 + n);
i += num;
}
print_arr(try2,n);
return 0;
}
}然后还需要写一个用于判断函数是否已经排好序的函数和一个判断两个数组相等的函数
最后的代码总结如下：
#include <bits/stdc++.h>
using namespace std;
int arra[999];
int arrb[999];
bool temp = true;
bool bb = true;
void print_arr(int *arr,int size)
{
for(int i = 0;i < size;++i)
{
cout << arr[i];
if(i != size-1)
{
cout << " ";
}
}
}
bool is_unsort(int *a,int length)
{
for(int i = 0;i < length-1;++i)
{
if(a[i] > a[i+1])
{
return true;
}
}
return false;
}
bool is_func(int *a,int *b,int length)
{
for(int i = 0;i < length;++i)
{
if(a[i] != b[i]) return false;
}
return true;
}
void Insertion_sort(int *arr,int begin,int size)
{
int i,j;
for(i = begin;i < size && temp;++i)//第一个元素不用排序
{
int t = arr[i];
for(j = i-1;j >= 0 && arr[j] > t;--j)
{
arr[j+1] = arr[j];//直接覆盖，速度更快（将前一个覆盖到后面）
}
::temp = false;
arr[j+1] = t;//因为是覆盖，所以要最后赋值
}
::temp = true;
}
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;++i)
{
cin >> arra[i];
}
for(int i = 0;i < n;++i)
{
cin >> arrb[i];
}
int try1[n],try2[n];
for(int i = 0;i < n;++i)
{
try1[i] = arra[i];
}
for(int i = 0;i < n;++i)
{
try2[i] = arra[i];
}
//使用改进的insert排序
int i = 1;
while(is_unsort(try1,n))
{
Insertion_sort(try1,i++,n);
if(is_func(try1,arrb,n))
{
cout << "Insertion Sort\n";
Insertion_sort(try1,i++,n);
print_arr(try1,n);
return 0;
}
}
//模拟merge
int num = 2;
while(is_unsort(try2,n))
{
i = 0;
while(i+num < n)
{
sort(try2 + i,try2 + i + num);
i += num;
}
while(i < n)
{
sort(try2 + i,try2 + n);
i += num;
}
num *= 2;
if(is_func(try2,arrb,n))
{
cout << "Merge Sort\n";
i = 0;
while(i+num < n)
{
sort(try2 + i,try2 + i + num);
i += num;
}
while(i < n)
{
sort(try2 + i,try2 + n);
i += num;
}
print_arr(try2,n);
return 0;
}
}
}
/*
用于测试手搓的样例
9
3 1 2 8 7 5 9 4 6
1 3 2 8 5 7 4 9 6
1 2 3 8 4 5 7 9 6
*/