PAT 1035插入與歸併的代碼實現及錯誤分析（C語言）

根據維基百科的定義：

插入排序是迭代演算法，逐一獲得輸入數據，逐步產生有序的輸出序列。每步迭代中，演算法從輸入序列中取出一元素，將之插入有序序列中正確的位置。如此迭代直到全部元素有序。

歸併排序進行如下迭代操作：首先將原始序列看成 N 個只包含 1 個元素的有序子序列，然後每次迭代歸併兩個相鄰的有序子序列，直到最後只剩下 1 個有序的序列。

現給定原始序列和由某排序演算法產生的中間序列，請你判斷該演算法究竟是哪種排序演算法？

輸入在第一行給出正整數 N (≤100)；隨後一行給出原始序列的 N 個整數；最後一行給出由某排序演算法產生的中間序列。這裡假設排序的目標序列是升序。數字間以空格分隔。

首先在第 1 行中輸出Insertion Sort表示插入排序、或Merge Sort表示歸併排序；然後在第 2 行中輸出用該排序演算法再迭代一輪的結果序列。題目保證每組測試的結果是唯一的。數字間以空格分隔，且行首尾不得有多餘空格。

實現思路：

從題目可以看出，並不是讓我們寫完整的插入排序和歸併排序的演算法，而是簡化為進行一次排序操作，即理解原理即可，歸併排序的過程判斷比較複雜，但插入排序比較簡單，即前n項排序完畢，而後面的項原封未動，所以前後兩個循環即可判斷是否為插入排序，不是則認定為歸併排序。插入排序的下一步也比較簡單，不做討論。歸併排序的當前狀態和下一步則比較複雜，有兩種方案，一種是模擬歸併排序的演算法，進行每一步之後逐個與原數組比對，如完全吻合則進行下一步，輸出，但這種方法時效性較差，每一步歸併是一個循環，比對是一個循環，整體歸併還是一個循環，相當於嵌套3層循環；另一種則是從歸併排序的原理入手，即歸併的每一步是對每一塊進行排序，塊的大小逐次增加2倍，所以對中間狀態的數組進行循環比較，找出最小排序塊iCnt，則2^k<iCnt<2^(k+1)中的k+1即是下一次排序的塊大小，歸併排序的逐步演算法寫為（數組，數組大小，塊大小）的函數即可。

代碼如下：

錯誤分析：

易錯點1：插入排序中，從後往前逐個比對時，如果比第一位小，要把第一位置位。

易錯點2：n的判斷要準確。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！