題目鏈接：https://www.patest.cn/contests/pat-b-PRactise/1035 根據維基百科的定義：
插入排序是迭代算法，逐一獲得輸入數據，逐步產生有序的輸出序列。每步迭代中，算法從輸入序列中取出一元素，將之插入有序序列中正確的位置。如此迭代直到全部元素有序。
歸并排序進行如下迭代操作：首先將原始序列看成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
#include<cstdio>#include<algorithm>using namespace std;const int N=110;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;} bool 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; for(int i=1;i<n;i++){ if(i!=1&&isSame(tempOri,changed)){//每插入一輪，進行一次比較 flag=true; } //開始插入 int temp=tempOri[i],j=i; while(j>0&&tempOri[j-1]>temp){ tempOri[j]=tempOri[j-1]; j--; } tempOri[j]=temp; if(flag==true){ return true; } } return false;}void merge(int A[],int L1,int R1,int L2,int R2){ int i=L1,j=L2; int temp[N],index=0; while(i<=R1&&j<=R2){ if(A[i]<=A[j]){ temp[index++]=A[i++]; }else{ temp[index++]=A[j++]; } } while(i<=R1) temp[index++]=A[i++]; while(j<=R2) temp[index++]=A[j++]; for(int i=0;i<index;i++){ A[L1+i]=temp[i]; } }void mergeSort(){ 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){// sort(tempOri+i,tempOri+min(i+step,n));//在考試時，只要運行不超時，可以用sort代替merge函數， int mid=i+step/2-1; if(mid+1<n){ merge(tempOri,i,mid,mid+1,min(i+step,n)-1); } } if(flag==true){ showArray(tempOri); return; } }} int main(){ 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(insertSort()){//如果插入排序中找到目標數組 printf("Insertion Sort/n"); showArray(tempOri); }else{//或者就是歸并排序 printf("Merge Sort/n"); for(int i=0;i<n;i++){ tempOri[i]=origin[i];//因為剛才insertSort()時改變了tempOri數組，所以要現在要還原 } mergeSort(); } return 0;}新聞熱點
疑難解答
