[PAT] A1098 Insertion or Heap Sort

（重要！堆！）

题目大意

给出n和n个数的序列a和b，a为原始序列，b为排序其中的一个步骤，问b是a经过了堆排序还是插入排序的，并且输出它的下一步。

坑

测试点2：插入排序时，要考虑输入的两个序列是相同的情况。即第一次判断时原序列的第一个数和第二个数本身有序（题目保证了答案唯一，所以不会出现连续几个本身都有序的情况）。一开始我写错了，是因为先判断了序列是否相同再进入循环。

化简

找到两个排序中那个最容易分辨出来——明显是插入排序。在判断是否为插入排序时，无需模拟插入排序的过程。插入排序的特点是：b数组前面的顺序是从小到大的，后面的顺序不一定，但是一定和原序列的后面的顺序相同。所以只要遍历一下前面几位，遇到不是从小到大的时候，开始看b和a是不是对应位置的值相等，相等就说明是插入排序，否则就是堆排序。这样也可避免上面说到的两个输入序列相同的情况。
插入排序的下一步就是把第一个不符合从小到大的顺序的那个元素插入到前面已排序的里面的合适的位置，那么只要对前几个已排序的+后面一位这个序列sort排序即可。找到第一个不满足条件的下标p并且赋值给index。数组下标从1开始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1);后的b数组。
当确认是使用堆排序方法时，也不用模拟一遍堆排序过程了（即不用管序列a。序列a只是用于判断a到b的过程用的是什么方法。既然已经知道了方法，直接从b求下一步就行，也就是在b的基础上继续进行一次向下调整的步骤）。因为序列b的前几项（即还没排序的部分）一定已经是一个大顶堆，它的特点是最大值在第一个数b[1]。从后往前找到第一个没排好序的数b[p]，让它与b[1]交换，再让b[1...p-1]做一次downAdjust即可。

AC代码

1 精简后的代码

求下一步的结果均有两种解法，注释的部分可以替换它下面的代码段。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 102
int n, initial[N], part[N];
void downAdjust(int low, int high) {
    int i = low, j= low * 2 + 1;
    while (j <= high) {
        if (j + 1 <= high && part[j + 1] > part[j])j = j + 1;
        if (part[j] > part[i]) {
            swap(part[j], part[i]);
            i = j;j = 2 * i + 1;
        }
        else break;
    }
}
int main() {
    int i, j, k;
    scanf("%d", &n);
    for (i = 0;i < n;i++)scanf("%d", &initial[i]);
    for (i = 0;i < n;i++)scanf("%d", &part[i]);
    i = 1;
    while (i < n && part[i - 1] <= part[i])i++;//这里的<=中的等号不能少（相等情况也要继续循环），否则测试点4过不了。
    k = i;
    while (i < n && initial[i] == part[i])i++;
    if (i == n) {//插入排序
        /*int x = part[k];k--;
        while (k >= 0 && part[k] > x) {
            part[k + 1] = part[k];
            k--;
        }
        part[k + 1] = x;
        printf("Insertion Sort\n%d", part[0]);
        for (k = 1;k < n;k++)printf(" %d", part[k]);
        */
        sort(initial, initial + k + 1);
        printf("Insertion Sort\n%d", initial[0]);
        for (k = 1;k < n;k++)printf(" %d", initial[k]);
    }
    else {
        printf("Heap Sort\n");
        /*
        k = n - 1;
        while(k > 1 && part[0] < part[n - 1])k--;
        */
        sort(initial, initial + n);
        k = n - 1;
        while (k > 0 && part[k] == initial[k])k--;
        swap(part[0], part[k]);
        downAdjust(0, k - 1);
        printf("%d", part[0]);
        for (k = 1;k < n;k++)printf(" %d", part[k]);
    }
    return 0;
}

2 原始代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <cstdio>
#include <vector>
#include<algorithm>
using namespace std;
#define N 102
vector<int>initial, part, heap, insert;
void downAdjust(int low, int high) {
    int i = low, j = i * 2 + 1;
    while (j <= high) {//如果存在孩子(孩子还没越过边界)
        if (j + 1 <= high && heap[j + 1] > heap[j])
            j = j + 1;
        if (heap[i] < heap[j]) {
            swap(heap[i], heap[j]);
            i = j;
            j = i * 2 + 1;
        }
        else break;//一旦孩子不比父子大，往下不用再比了。因为下面的都是已经排好了更小的。
    }
}
int main() { 
    int n, i, j;    
    scanf("%d", &n); 
    initial.resize(n);
    insert.resize(n);
    part.resize(n);
    heap.resize(n);
    for (i = 0;i < n;i++)scanf("%d", &initial[i]);
    for (i = 0;i < n;i++)scanf("%d", &part[i]);
    heap = initial;
    insert = initial;
    i = 1;
    while (i < n) {
//这里一定不能先判断insert和part是否相同。因为可能是经历了几次后结果还是和原来一样（题目说了不可能是0次）。如果一开始就判断的话，会直接不进入循环
        for (j = i;j > 0;j--) {
            if (insert[j] < insert[j - 1])
                swap(insert[j], insert[j - 1]);
        }
        i++;
        if (insert == part)break;
    }
    if (i < n) {
        printf("Insertion Sort\n");
        for (j = i;j > 0;j--) {
            if (insert[j] < insert[j - 1])
                swap(insert[j], insert[j - 1]);
        }
        printf("%d", insert[0]);
        for (j = 1;j < n;j++)
            printf(" %d", insert[j]);
    }
    else {
        printf("Heap Sort\n");
        for (i = (n - 1) / 2; i >= 0; i--) {
            downAdjust(i, n - 1);
        }
        i = n - 1;
        while (heap != part) {
            swap(heap[i], heap[0]);
            downAdjust(0, i - 1);
            i--;
        }
        swap(heap[i], heap[0]);
        downAdjust(0, i - 1);
        printf("%d", heap[0]);
        for (j = 1;j < n;j++)
            printf(" %d", heap[j]);
    }
    return 0; 
}