題目描述

根據(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ù)字間以空格分隔，且行末不得有多余空格。

輸入例子:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

輸出例子:
Insertion Sort
1 2 3 5 7 8 9 4 6 0

答案

寫(xiě)了兩個(gè)半小時(shí)，沒(méi)寫(xiě)出歸并排序（后附失敗代碼）。后來(lái)發(fā)現(xiàn)可能是我對(duì)歸并排序的理解有問(wèn)題。歸并排序本來(lái)是一個(gè)時(shí)間復(fù)雜度沒(méi)有那么高的排序方法，強(qiáng)行“迭代”“歸并”后反而更復(fù)雜。

別人的答案寫(xiě)的真好，用sort就解決了

#include <algorithm> #include <iostream> using namespace std; int n, a[110], s[110]; void mergesort(int(&a)[110], int s[], int n) { //注意引用數(shù)組的寫(xiě)法int step = 1, flag = 1;while (flag) { //flag表示數(shù)組的中間步驟是否與中間數(shù)組相同flag = 0;for (int i = 0; i < n; i++) {if (a[i] != s[i])flag = 1;}step *= 2; //不斷的歸并排序，直到與中間數(shù)組相同，再排序一次并退出for (int i = 0; i < n; i += step)sort(a + i, a + min(i + step, n)); //不像插入排序一樣只用一次處理。是因?yàn)榕袛鄽w并的有序 區(qū)間大小比較復(fù)雜} } int main() {int i, j;cin >> n;for (i = 0; i < n; i++)cin >> a[i];for (i = 0; i < n; i++)cin >> s[i];for (i = 0; i < n - 1 && s[i] <= s[i + 1]; i++); //找出中間數(shù)組的有序部分for (j = i + 1; a[j] == s[j] && j < n; j++); //判斷排序類(lèi)型if (j == n) {cout << "Insertion Sort" << '\n';sort(a, a + i + 2); //直接用sort函數(shù)代替插入排序（注意下標(biāo)） }else {cout << "Merge Sort" << '\n';mergesort(a, s, n);}for (int i = 0; i < n; i++) {cout << a[i];if (i != n - 1) cout << " ";}return 0; }

附：失敗的歸并排序
貌似10個(gè)元素的時(shí)候可以成功

#include<iostream> #include<vector> using namespace std; int main() {int n;cin >> n;vector<int> arr1;vector<int> arr2;int t;int i;for (i = 0; i < n; i++){cin >> t;arr1.push_back(t);}for (i = 0; i < n; i++){cin >> t;arr2.push_back(t);}vector<int> temp;int j1, j2;int part = 0;//第幾段int curPush = 0;for (i = 1; i < n; i *= 2){part = 0;for (j1 = 0, j2 = 0; j1 < i || j2 < i; ){if ((part + 1)*i + j2 >= n){for (int t = 0; part*i + j1 + t < n; t++){temp.push_back(arr1[part*i + j1 + t]);if (temp.size() == n)break;}break;}if (arr1[part*i + j1] < arr1[(part + 1)*i + j2]){temp.push_back(arr1[part*i + j1]);curPush++;j1++;}else if (arr1[part*i + j1] >= arr1[(part + 1)*i + j2]){temp.push_back(arr1[(part + 1)*i + j2]);curPush++;j2++;}if (curPush == i * 2 - 1)//push剩下的元素{if (j1 < j2)temp.push_back(arr1[part*i + j1]);else if (j1 > j2)temp.push_back(arr1[(part + 1)*i + j2]);part += 2;j1 = 0;j2 = 0;curPush = 0;}}//復(fù)制for (int k = 0; k < n; k++){arr1[k] = *temp.begin();temp.erase(temp.begin());}}cout << endl;for (int k = 0; k < n; k++){cout << arr1[k] << " ";}cout << endl;system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的牛客网_PAT乙级_1025插入与归并(25)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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