1035. 插入与归并(25)-PAT乙级真题

前言

这应该会是一个会持续很长时间的主题，要上研究生了，总感觉自己的基本功很差，而如果真的要有所成就，这基本功就是必要的东西了，而且这也不是一天两天能完成的事情，急不得，whatever，要步履不停啊。

这题是PAT乙级的关于插入与归并算法的一题，需要真正的搞清楚各个排序算法的特点，并搞清楚各个算法的不同之处，看来不仅仅是要会写代码，还要会精通。

题目描述

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确
的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩
下1个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入描述:

输入在第一行给出正整数N (<=100)；随后一行给出原始序列的N个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以
空格分隔。

输出描述:

首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试
的结果是唯一的。数字间以空格分隔，且行末不得有多余空格。

输入例子:

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

解析

首先最重要的就是搞清楚插入排序和归并排序的特点及区别：

从序列的第一个一直到最后一个循环，然后在已有的序列里面找到该数字的位置插进去。从这里就可以发现，插入排序的特点就是前面一段有序，而后面一段与原序列相同。从这个地方就可以将之区分开来。

所以先找到从左到右满足从小到大顺序的最后一个数字的坐标，然后从这个坐标后面开始找，若后面的序列都相同，就说明是排序，不然就是归并。

其次就是要在搞清楚排序种类后，输出下一次的排序结果：

插入排序好计算，但是难的是归并排序，因为其实归并算法的代码是递归的，先排完左边，再排完右边的，但是本题要求要左边右边一起排列。而根据归并排序的特点，所以最后只能从最开始归并，直到找到给出的序列，就能得到下一次的序列。

代码如下：

#include <iostream>
#include <algorithm> // 要用到Sort函数，就要用到Algorithm 记住
using namespace std;

int main(){
    int n, a[100], b[100], i, j;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (i = 0; b[i] <= b[i + 1] && i < n - 1; i++);
    for (j = i + 1; a[j] == b[j] && j < n; j++);
    if (j == n){
        cout << "Insertion Sort" << endl;
        sort(a, a + i + 2);
    } else {
        cout << "Merge Sort" << endl;
        int k = 1, flag = 1;
        while (flag){
            flag = 0;
            for(i = 0; i < n; i++)
                if (a[i] != b[i]) flag = 1;
            k = k * 2;
            for (i = 0; i < n / k; i++)
                sort(a + i * k, a + (i + 1) * k);
            sort(a + n / k * k, a + n); // 最后还要有这一步
        }
    }
    for (i = 0; i < n - 1; i++)
        cout << a[i] << " ";
    cout << a[n - 1];
    return 0;   
}