PAT乙級—1035. 插入與歸并(25)-native

根據維基百科的定義：

插入排序是疊代算法，逐一獲得輸入資料，逐漸産生有序的輸出序列。每步疊代中，算法從輸入序列中取出一進制素，将之插入有序序列中正确的位置。如此疊代直到全部元素有序。

歸并排序進行如下疊代操作：首先将原始序列看成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

思路：此題必須深刻了解插入排序與歸并排序，除了判斷前面升序，後面與原數列相同的方法，有的同學會去模拟插入排序，與每一次進行比對，這裡要注意，測試點2應該是當你輸入相同的已進行部分插入排序的數列，再進行下一次插入的時候，要看好已經有多少排好序了，比如輸入2 3 4 1和2 3 4 1，要注意輸出應該是1 2 3 4 。

#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
bool equal(int a[],int b[],int N){  //判斷是否相等
    for(int k=;k<N;k++)
        if(a[k]!=b[k])
            return false; 
    return true;
}
void merger(int a[],int b[],int N){ //edge為步長，1,2,4,8……
    int edge=;
    for(;;edge*=){             //步長每次乘以2
        bool istrue=true;
        istrue=equal(a,b,N);    //先判斷是否相等，再進行歸并，這樣若為真的話，在後面判斷則會多進行一次歸并
        for(int j=;j<N;j+=edge){//每edge個元素進行一次排序
            int temp=edge+j;    
            if(temp>N)          //若最後元素個數不足步長，則最大為N即可
                temp=N;
            sort(a+j,a+temp);
        }
        if(istrue){             //如果相等則輸出，并跳出循環
            cout<<"Merge Sort"<<endl;
            break;
        }   
    }
}
int main(){
    int N;
    cin>>N;
    int A1[N+],A2[N+];
    for(int i=;i<N;i++)
        cin>>A1[i];
    for(int i=;i<N;i++)
        cin>>A2[i];
    int i,j;
    for( i=; A2[i]<=A2[i+] && i<N-; i++ ) ;       // i作為有序序列最後一個元素下标退出循環  
        for( j=++i; A1[j]==A2[j] && j<N; j++  ) ;    // A1 A2從 第一個無序的元素開始 逐一比對  
    if( j==N ){                         // 前半部分有序而後半部分未改動可以确定是插入排序  
        cout<<"Insertion Sort"<<endl;  
        sort( A1, A1+i+ );  
    } 
    else merger(A1,A2,N);
    for(int k=;k<N;k++){   
        if(k!=)
        cout<<" ";
        cout<<A1[k];
    }
    return ;
}
           

題目連結：

https://www.patest.cn/contests/pat-b-practise/1035