立志用更少的代碼做更高效的表達(dá)

---

PAT乙級(jí)最優(yōu)題解——>傳送門(mén)

---

根據(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é)果序列。題目保證每組測(cè)試的結(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

---

解析

最初的思路是把插入和歸并排序?qū)懗鰜?lái)，然后判斷每一階段數(shù)組是否相等，若相等則輸出下一階段的數(shù)組。
但后來(lái)發(fā)現(xiàn)它的歸并， 和我常寫(xiě)的歸并有差異。于是換了種思路。

利用algorithm頭文件中的sort數(shù)組進(jìn)行定格排序。
輸出指定序列即可。

#include<bits/stdc++.h> using namespace std; int N,A[105],initial[105],target[105]; int main(){scanf("%d",&N);for(int i=0;i<N;++i)//讀取原始序列scanf("%d",&initial[i]);for(int i=0;i<N;++i)//讀取中間序列scanf("%d",&target[i]);memcpy(A,initial,sizeof(initial));//將原始序列拷貝給A數(shù)組bool f=false;for(int i=1;i<N;++i){//進(jìn)行插入排序sort(A,A+i+1);//第一趟排序應(yīng)該是排序前兩個(gè)數(shù)，第i趟排序分別排序前i+1個(gè)數(shù)if(equal(A,A+N,target)){//equal是C++標(biāo)準(zhǔn)庫(kù)中函數(shù)，如果兩個(gè)序列對(duì)應(yīng)位置上的元素都相等，則返回truef=true;printf("Insertion Sort\n");sort(A,A+i+2);//進(jìn)行下一趟排序break;}}if(!f){//不是插入排序printf("Merge Sort\n");memcpy(A,initial,sizeof(initial));for(int i=2;i<N;i*=2){//將每i個(gè)元素歸并為一個(gè)非遞減序列for(int j=0;j<N;j+=i)sort(A+j,j+i<N?A+j+i:A+N);if(equal(A,A+N,target)){for(int j=0;j<N;j+=i*2)//進(jìn)行下一趟排序sort(A+j,j+i*2<N?A+j+i*2:A+N);break;}}}for(int i=0;i<N;++i)//輸出下一趟排序結(jié)果printf("%s%d",i>0?" ":"",A[i]);return 0; }

---

耗時(shí)

---

每日一句

每個(gè)不曾起舞的日子，都是對(duì)生命的辜負(fù)。

總結(jié)

以上是生活随笔為你收集整理的【简便解法】1035 插入与归并 (25分)_37行代码AC的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。