1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805377432928256
给出数字个数，然后给出初始序列和排序的中间序列，要求判断这是用了归并排序还是插入排序（也只有这两种可能）。
2.思路
首先模拟直接插入排序的每一趟的过程，并进行判断每一趟的序列和给出的第二个序列是否相同，若不相同则一定是归并排序，直接对第一个序列进行归并排序一趟并输出。
（1）归并排序可以使用非递归版本（更少）；
（2）用到了一个tempOri数组（排序时均是用这个数组），而如果是归并排序，则需要利用origin[i]赋值给tempOri[i]数组（还原tempOri数组）。
（3）搞了3个数组：原始数组origin[]，原始数组备份tempOri[]（排序过程在这个数组上进行），change[]为输入给出的第二个中间过程数组。
注意插入排序的代码：
bool insertSort(){ //插入排序 bool flag=false; //记录是否在数组中间步骤与changed数组相同 for(int i=1;i<n;i++){ //进行n-1趟排序 if( i != 1&& isSame(tempOri,changed)){ flag=true; //中间步骤与目标相同，!!且不是初始序列!!(这里理解一下) } //以下为插入部分 int temp=tempOri[i], j=i; //temp临时存放tempOri[i],j从i开始往前遍历 while(j>0 && tempOri[j-1] > temp){ //只要temp小于前一个元素tempOri[j-1] tempOri[j] = tempOri[j-1]; j--; } tempOri[j]=temp; //插入位置j if(flag == true){ return true; //说明已经到达目标目标数组，返回true //另注意：这里的return不能放在最上面的if里面(因后面要输出下一步的序列) } } return false; //无法达到目标数组，返回false }
3.完整代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; 判断一个"中间"序列是插入/归并排序产生的，注意输出的是下一步会产生的序列 如果判断出不是插入排序则确定是归并 const int N=111; int origin[ N] ,tempOri[N],changed[N] ;//原始数组，原始数组备份，目标数组 int n; //元素个数 bool isSame(int A[],int B[]){ //判断数组A与数组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("\n"); } bool insertSort(){ //插入排序 bool flag=false; //记录是否在数组中间步骤与changed数组相同 for(int i=1;i<n;i++){ //进行n-1趟排序 if( i != 1&& isSame(tempOri,changed)){ flag=true; //中间步骤与目标相同，!!且不是初始序列!!(这里理解一下) } //以下为插入部分 int temp=tempOri[i], j=i; //temp临时存放tempOri[i],j从i开始往前遍历 while(j>0 && tempOri[j-1] > temp){ //只要temp小于前一个元素tempOri[j-1] tempOri[j] = tempOri[j-1]; j--; } tempOri[j]=temp; //插入位置j if(flag == true){ return true; //说明已经到达目标目标数组，返回true //另注意：这里的return不能放在最上面的if里面(因后面要输出下一步的序列) } } return false; //无法达到目标数组，返回false } void mergeSort(){ //归并排序 bool flag=false; //记录是否存在数组中间步骤与changed数组相同 //以下为归并排序部分 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){ sort(tempOri+i,tempOri + min(i+step,n)); } if(flag == true){ //已到达目标数组，输出tempOri数组 showArray(tempOri); return; } } } int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&origin[i]); //输入起始数组 tempOri[i]=origin[i]; //tempOri数组为备份，排序过程在tempOri上进行 } for(int i=0;i<n;i++){ scanf("%d",&changed[i]); } if(insertSort()){ //如果插入序列中找到目标数组 printf("Insertion Sort\n"); showArray(tempOri); }else{ //到达此处时一定是归并排序 printf("Merge Sort\n"); for(int i=0;i<n;i++){ tempOri[i]=origin[i]; //还原tempOri数组,因为前面已经if内insertSort过 } mergeSort(); //归并排序 } system("pause"); return 0; }
