我的PAT系列文章更新重心已移至Github蚯妇，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容是趴。此處文章目前已更新至與Github Pages同步涛舍。歡迎star我的repo。
題目
根據(jù)維基百科的定義：
插入排序
是迭代算法唆途，逐一獲得輸入數(shù)據(jù)富雅，逐步產(chǎn)生有序的輸出序列。每步迭代中肛搬，算法從輸入序列中取出一元素没佑，將之插入有序序列中正確的位置。如此迭代直到全部元素有序温赔。
歸并排序 進(jìn)行如下迭代操作：首先將原始序列看成 N 個(gè)只包含 1 個(gè)元素的有序子序列蛤奢，然后每次迭代歸并兩個(gè)相鄰的有序子序列，直到最后只剩下 1
個(gè)有序的序列陶贼。
現(xiàn)給定原始序列和由某排序算法產(chǎn)生的中間序列啤贩，請你判斷該算法究竟是哪種排序算法？
輸入格式：
輸入在第一行給出正整數(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
思路
這道題是我唯一看了幾乎網(wǎng)上所有熱門博客都沒有發(fā)現(xiàn)自己錯(cuò)在哪的一道題，提交了10遍啊～差點(diǎn)絕望俘侠。最后乖乖地按照普遍做法改寫了代碼象缀，終于過了。
題中說
題目保證每組測試的結(jié)果是唯一的爷速。
這應(yīng)該有兩點(diǎn)保證：
- 一定能區(qū)分插入排序和歸并排序
- 一定能確定排序的步數(shù)央星，不會(huì)產(chǎn)生某一步排序沒有任何改變的情況
判斷哪種排序方法
- 插入排序：
從后向前找到和原始數(shù)組不同的元素，驗(yàn)證此元素之前是否為排好序的惫东，如果是排好的莉给，則是插入排序毙石，下一步將第一個(gè)相同的元素插入排序 - 歸并排序：
從最初的數(shù)組模擬一步一步的歸并，直至和中間序列相同颓遏，再向下進(jìn)行一步
代碼
最新代碼@github徐矩，歡迎交流
#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int N, origin[100], halfsort[100], i, j, length;
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%d", origin + i);
for(int i = 0; i < N; i++) scanf("%d", halfsort + i);
/* if it is insertion sort, return sorted length if yes, zero otherwise */
for(i = 0; i < N - 1 && halfsort[i] <= halfsort[i + 1]; i++) ;
for(length = ++i; i < N && halfsort[i] == origin[i]; i++) ;
length = i == N ? length + 1 : 0;
if(length) /* insertion sort */
{
puts("Insertion Sort");
qsort(origin, length, sizeof(int), comp);
}
else /* merge sort, operate on the original array */
{
puts("Merge Sort");
for(length = 1, i = 0; i < N && length <= N; length *= 2)
{
/* i == N means identical, also breaks the outer 'for' loop */
for(i = 0; i < N && origin[i] == halfsort[i]; i++) ;
for(j = 0; j < N / length; j++)
qsort(origin + j * length, length, sizeof(int), comp);
qsort(origin + j * length, N % length, sizeof(int), comp);
}
}
for(int i = 0; i < N; i++)
printf("%d%c", origin[i], i == N - 1 ? '\n' : ' ');
return 0;
}
