个人练习-PAT甲级-1089 Insert or Merge_综合

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805377432928256

感觉是以前做过的题目。。第一次做超时了，于是看了柳神的解答，发现判断插排可以更快一点。改了后还是超时，于是在归并排序那debug了挺久，发现while循环里忘了给次数自增。。还有别的一些bug，但最终还是过了。

判断插排：
插排一共走N-1趟，它的特征是第p( $1\le p\le N-1$ )趟时，位置0到位置 $p ? 1$ 的元素是排好序的【注意它们只是相对于这 $p$ 个元素内排好序，并不一定是最终结果排好序】。
那么我们从给出的中间序列fin[]中找到第一个不符合fin[i]<=fin[i+1]的数字，就知道【如果这是快排，这应该是第几趟了】。
然后再从原序列arr[]中，从i+1开始对比，如果后面的数都相同，那就是插排。因为这些之后的数还没有进行过插入，所以如果是插排，它们的序列是和原序列一样没有变化过的。
判断是插排后，直接用sort把原序列第0到第i+1的数字排序，因为下一趟插入是第i+1个数字插入。输出。

    int i, j;for (i = 0; i < N - 1; i++) {
    if (fin[i] > fin[i + 1])break;}for (j = i + 1; j < N; j++) {
    if (arr[j] != fin[j])break;}if (j == N) {
    printf("Insertion Sort\n");sort(arr.begin(), arr.begin() + i + 2);Output(arr);}

归并排序，用sz表示每次归并后，一个sublist的大小，初始为2，每次归并后*2。在变成和中间序列相同之前一直归并。

    else {
    int sz = 2;while (1) {
    MergeSort(arr2, sz);if (isSame(arr2, fin)) {
    printf("Merge Sort\n");MergeSort(arr2, sz*2);Output(arr2);break;}sz *= 2;}}

归并过程，即使序列最后没有sz个元素，也要将其内部排好序。cnt为归并前一个sublist的大小

void MergeSort(vector<int>& arr, int sz) {
    int cnt = sz / 2;int tm = arr.size() / sz;for (int i = 0; i < tm; i++)Merge(arr, i * sz, (i + 1) * sz, cnt);      if (arr.size() > tm * sz)Merge(arr, tm * sz, arr.size(), cnt);
}

两个sublist的合并我没有用STL的sort，因为直接用原算法快一点( $O (N)$ )

void Merge(vector<int>& arr, int head, int rear, int cnt) {
    vector<int> tmp;int p1 = head, p2 = head + cnt;while (p1 < head + cnt && p2 < rear) {
    if (arr[p1] <= arr[p2]) {
    tmp.push_back(arr[p1]);p1++;}else {
    tmp.push_back(arr[p2]);p2++;}}while (p1 < head + cnt) {
    tmp.push_back(arr[p1]);p1++;}while (p2 < rear) {
    tmp.push_back(arr[p2]);p2++;}for (int i = head; i < rear; i++)arr[i] = tmp[i - head];
}

完整代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string.h>
#include <string>using namespace std;void Merge(vector<int>& arr, int head, int rear, int cnt) {
    vector<int> tmp;int p1 = head, p2 = head + cnt;while (p1 < head + cnt && p2 < rear) {
    if (arr[p1] <= arr[p2]) {
    tmp.push_back(arr[p1]);p1++;}else {
    tmp.push_back(arr[p2]);p2++;}}while (p1 < head + cnt) {
    tmp.push_back(arr[p1]);p1++;}while (p2 < rear) {
    tmp.push_back(arr[p2]);p2++;}for (int i = head; i < rear; i++)arr[i] = tmp[i - head];
}void MergeSort(vector<int>& arr, int sz) {
    int cnt = sz / 2;int tm = arr.size() / sz;for (int i = 0; i < tm; i++)Merge(arr, i * sz, (i + 1) * sz, cnt);      if (arr.size() > tm * sz)Merge(arr, tm * sz, arr.size(), cnt);
}bool isSame(vector<int> arr, vector<int> fin) {
    for (int i = 0; i < arr.size(); i++) {
    if (arr[i] != fin[i])return false;}return true;
}void Output(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) {
    if (i)printf(" ");printf("%d", arr[i]);}
}int main() {
    int N;scanf("%d", &N);vector<int> arr(N);vector<int> fin(N);for (int i = 0; i < N; i++)scanf("%d", &arr[i]);for (int i = 0; i < N; i++)scanf("%d", &fin[i]);vector<int> arr2(arr);int i, j;for (i = 0; i < N - 1; i++) {
    if (fin[i] > fin[i + 1])break;}for (j = i + 1; j < N; j++) {
    if (arr[j] != fin[j])break;}if (j == N) {
    printf("Insertion Sort\n");sort(arr.begin(), arr.begin() + i + 2);Output(arr);}else {
    int sz = 2;while (1) {
    MergeSort(arr2, sz);if (isSame(arr2, fin)) {
    printf("Merge Sort\n");MergeSort(arr2, sz*2);Output(arr2);break;}sz *= 2;}}    return 0;
}