题目
根据维基百科的定义：
插⼊排序是迭代算法，逐⼀获得输⼊数据，逐步产⽣有序的输出序列。每步迭代中，算法从输⼊序列中取出⼀元素，将之插⼊有序序列中正确的位置。如此迭代直到全部元素有序。归并排序进⾏如下迭代操作：⾸先将原始序列看成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
题目分析
已知原始数组a，和对a排序过程中数组b，判断是归并排序还是插入排序，并打印再进行一轮排序后的结果
解题思路
判断是归并排序还是插入排序--插入排序过程中数组特点：第一个非升序数字（假设其索引为i）后的剩余数字都与原数组中相同位置数字相同
思路 01
- 如果是插入排序，对[0,i+1]的数字进行排序就是下一轮插入排序的结果
- 如果是归并排序，从原始数组使用非递归归并代码执行归并过程，并在每一轮判断排序结果是否已经是题目中已知的数组b，若是，则再进行一轮归并即可得出结果
思路 02
- 对原始数组分别进行插入排序和归并排序，在每一轮结束后，判断排序结果是否已经是题目中已知的数组b，若是，则再进行一轮排序即可得出结果
Code
Code 01
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// 1 接收输入
int n, a[100], b[100], i, j;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
// 2 判断是哪种排序
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 {// 归并排序
cout << "Merge Sort" << endl;
int k = 1, flag = 1;
while(flag) {
flag = 0;
for (i = 0; i < n; i++) {
if (a[i] != b[i])
flag = 1;
}
k = k * 2;
for (i = 0; i < n / k; i++) // 对左边模拟归并排序
sort(a + i * k, a + (i + 1) * k);
sort(a + n / k * k, a + n); // 如果有右边剩余，对齐进行排序
}
}
// 3 打印数组
for (j = 0; j < n; j++) {
if (j != 0) printf(" ");
printf("%d", a[j]);
}
return 0;
}
Code 02
#include <iostream>
#include <algorithm>
using namespace std;
const int N=111;
int origin[N],tempOri[N],changed[N];
int n; //元素个数
// 判断数组是否相等
bool isSame(int A[],int B[]) {
for(int i=0; i<n; i++)
if(A[i]!=B[i])return false;
return true;
}
// 打印数组
void showArray(int A[]) {
for(int i=0; i<n; i++) {
printf("%d",A[i]);
if(i<n-1)printf(" ");
}
printf("
");
}
// 插入排序
bool insert_sort() {
bool flag = false;
for(int i=1; i<n; i++) {
if(i!=1&&isSame(tempOri,changed)) {
flag = true;
}
// 写法一：
int j,temp = tempOri[i];
for(j=i-1; j>=0; j--) {
if(temp>=tempOri[j])break;
else tempOri[j+1]=tempOri[j];
}
tempOri[j+1]=temp;
// 写法二：
// int j=i,temp = tempOri[i];
// while(j>0&&tempOri[j-1]>temp){
// tempOri[j]=tempOri[j-1];
// j--;
// }
// tempOri[j]=temp;
if(flag)return true;
}
return false;
}
// 归并排序
void merge_sort() {
bool flag = false;
for(int step=2; step/2<=n; step*=2) { // 每次步长扩大一倍
if(step!=2&&isSame(tempOri,changed))
flag = true;
for(int i=0; i<n; i+=step) // 一轮排序，分成很多step组
sort(tempOri+i,tempOri+min(i+step,n)); //每个step组升序排序
if(flag) {
showArray(tempOri);
return;
}
}
}
int main(int argc, char * argv[]) {
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d",&origin[i]);
tempOri[i]=origin[i];
}
for(int i=0; i<n; i++) {
scanf("%d",&changed[i]);
}
if(insert_sort()) {
printf("Insertion Sort
");
showArray(tempOri);
} else {
printf("Merge Sort
");
for(int i=0; i<n; i++) {
tempOri[i]=origin[i]; //还原tempOri数组
}
merge_sort();
}
return 0;
}