题目描述

给出序列A, B，请判断使用了哪种排序方法，能从A得到B.

样例

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

算法1

(模拟) 最坏$O(nlgn)$

先判断是否是插入排序：[0, idx]区间升序，(idx, n)区间和原序列顺序一致

如果是插入排序，则将[0, idx + 1]排序即可

如果是堆排序，则找到idx，使得(idx, n) 区间恒大于[0]，然后交换[0]和[idx]，并进行shrink()

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 10, INF = 0x3f3f3f3f;

int arr[N], back[N];
int n;

void shrink(int x, int size) { // 将x位置的数字放到合适的位置
    int t = x;
    if (2 * x + 1 < size && back[t] < back[2 * x + 1]) t = 2 * x + 1; // 啊，一开始t写成了x，T...T
    if (2 * x + 2 < size && back[t] < back[2 * x + 2]) t = 2 * x + 2;

    if (t != x) {
        swap(back[t], back[x]);
        shrink(t, size);
    } 
}
int main() {

    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> arr[i];
    for (int i = 0; i < n; ++ i) cin >> back[i];

    //判断是否是插入排序
    bool is_insert = true;
    int idx = 0;
    while (idx == 0 || (idx < n && back[idx-1] <= back[idx])) idx++;
    for (int i = idx; i < n; ++ i) {
        if (arr[i] != back[i]) {
            is_insert = false;
            break;
        }
    }

    if (is_insert) {
        puts("Insertion Sort");
        sort(back, back + idx + 1);
    } else {
        //heap排序
        puts("Heap Sort");
        int tail = n - 1;
        while (back[tail] > back[0]) tail--;

        swap(back[0], back[tail]);
        // [0, tail）
        shrink(0, tail);
    }
    // output
    for (int i = 0; i < n; ++ i) {
        if (i) printf(" ");
        printf("%d", back[i]);
    }
    return 0;
}