PAT 甲级 刷题日记|A 1089 Insert or Merge (25 分)

思路

考察经典的排序算法

判断merge的下一轮 没有一个很好的特征作为条件，直接去模拟的思路非常妙！

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int ori[maxn], aft[maxn];

int main() {
    int n;
    cin>>n;
    for (int i = 0; i < n; i++) {
        cin>>ori[i];
    }
    for (int i = 0; i < n; i++) {
        cin>>aft[i];
    }
    int q = 1;
    while (aft[q] >= aft[q - 1] && q < n) q++;
    int k = q;
    while (ori[q] == aft[q] && q < n) q++;

    if (q == n) {
        cout<<"Insertion Sort"<<endl;
        if (k == n) k--;
        sort(aft, aft + k + 1);
        for (int i = 0; i < n; i++) {
            cout<<aft[i];
            if (i != n - 1) cout<<" ";
            else cout<<endl;
        }
    } else {
        cout<<"Merge Sort"<<endl;
        k = 1;
        int flag = 0;
        while (1) {
            for (int i = 0; i < n; i += (k * 2)) {
                int t = min(i + 2 * k, n);
                sort(ori + i, ori + t);
            }
            if (flag == 1) break;
            int j;
            if (flag == 0) {
                for (j = 0; j < n; j++) {
                    if (ori[j] != aft[j]) break;
                }
                if (j == n) flag = 1;
            }
            k *= 2;
        }
        for (int i = 0; i < n; i++) {
            cout<<ori[i];
            if (i != n - 1) cout<<" ";
            else cout<<endl;
        }   
    }
}