題目信息
根據(jù)維基百科的定義：
插入排序是迭代算法旨椒，逐一獲得輸入數(shù)據(jù)抖苦，逐步產(chǎn)生有序的輸出序列。每步迭代中坦敌，算法從輸入序列中取出一元素倦蚪，將之插入有序序列中正確的位置希坚。如此迭代直到全部元素有序。
歸并排序進(jìn)行如下迭代操作：首先將原始序列看成N個(gè)只包含1個(gè)元素的有序子序列陵且，然后每次迭代歸并兩個(gè)相鄰的有序子序列吏够，直到最后只剩下1個(gè)有序的序列。
現(xiàn)給定原始序列和由某排序算法產(chǎn)生的中間序列滩报，請(qǐng)你判斷該算法究竟是哪種排序算法锅知？
輸入格式：
輸入在第一行給出正整數(shù)N (<=100)；隨后一行給出原始序列的N個(gè)整數(shù)脓钾；最后一行給出由某排序算法產(chǎn)生的中間序列售睹。這里假設(shè)排序的目標(biāo)序列是升序。數(shù)字間以空格分隔可训。
輸出格式：
首先在第1行中輸出“Insertion Sort”表示插入排序昌妹、或“Merge Sort”表示歸并排序；然后在第2行中輸出用該排序算法再迭代一輪的結(jié)果序列握截。題目保證每組測試的結(jié)果是唯一的飞崖。數(shù)字間以空格分隔，且行末不得有多余空格谨胞。
輸入樣例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
分析
寫出兩種排序的每一趟結(jié)果固歪，再比對(duì)。雖然看起來有點(diǎn)麻煩，但思路簡單牢裳。
代碼
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,i,j,g=0;
cin >> n;
int a[n],b[n],c[n][n],d[n][n],a1[n];
for(i=0;i<n;i++){
cin >> a[i];a1[i]=a[i];
}
for(i=0;i<n;i++) cin >> b[i];
//先檢測是否為插入排序
for(i=1;i<n;i++){ //從a[1]到a[n-1]共n-1趟排序
int temp=a[i];int j=i-1;//臨時(shí)存放a[i],j從i-1開始往前枚舉
while(temp<a[j]&&j>=0){
a[j+1]=a[j];
j--;//把a(bǔ)[j]后移一位
}
a[j+1]=temp; //插入位置為j+1
for(int k=0;k<n;k++) c[i][k]=a[k]; //這里把一輪的結(jié)果數(shù)組存在c里
}
for(i=1;i<n;i++){
for(j=0;j<n;j++){
if(b[j]!=c[i][j]) break;
}
if(j==n) break;
}
if(i<n-1){
cout<<"Insertion Sort"<<endl;
for(int k=0;k<n-1;k++) cout<<c[i+1][k]<<" ";
cout<<c[i+1][n-1];
}
//再檢測是否為歸并排序
for(int step=2;step/2<=n;step*=2){
for(i=0;i<n;i+=step){
sort(a1+i,a1+min(i+step,n));
}
for(int k=0;k<n;k++) d[g][k]=a1[k]; //這里把一輪的結(jié)果數(shù)組存在d里
g++;
}
for(i=0;i<g;i++){
for(j=0;j<n;j++){
if(b[j]!=d[i][j]) break;
}
if(j==n) break;
}
if(i<g-1){
cout<<"Merge Sort"<<endl;
for(int k=0;k<n-1;k++) cout<<d[i+1][k]<<" ";
cout<<d[i+1][n-1];
}
return 0;
}
測試結(jié)果
