【PAT甲级】1098 Insertion or Heap Sort (25分)

解题过程的小记录，如有错误欢迎指出。

难度：五星（关于堆的模板要会背默）

题目分析

给出一串数列的原始数列，和中间排序数列，判断原始数列数通过插入排序还是堆排序达到中间数列，并给出下一状态的数列

注意点

原始数列不参与比较（因为会出现有前两位刚好是递增的情况，如果算入原始数列，那么 第一次和第二次插入排序的都是一样的数列，对于下一步数列的输出就会有歧义）

我的解题过程

思路

1. 用vector数组保存原始数列，中间数列，以及经过插入排序变化的中间序列或者经过堆排序的中间序列
2. 先判断是否是插入序列，采用sort从前往后，把每个阶段的结果和中间数列进行比较，如果一样，则输出下一情况，结束程序
3. 如果步骤2一直到循环结束都没有进行输出，那么说明是堆排序，在堆排序之前需要先建立堆，然后再进行中间步骤和给出数列的判断并输出下一步骤

bug

原来是不会写堆的部分，只写插入也能得一半的分数，后来看了参考，写的时候在downAdjust中应该是<=high都可以继续向下循环

代码

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;vector<int> d, before, comp1, comp2;void downAdjust(int low, int high) {int i = low, j = 2 * i;while (j <= high) {//****注意一下这个板块的边界问题if (j + 1 <= high&&comp2[j + 1] > comp2[j]) {j = j + 1;}if (comp2[i] < comp2[j]) {swap(comp2[i], comp2[j]);i = j;j = 2 * i;}else break;}
}void createHeap(int n) {for (int i = n / 2; i >= 1; i--) {downAdjust(i, n);}
}int main()
{int n;scanf("%d", &n);d.resize(n + 1);before.resize(n + 1);for (int i = 1; i <= n; i++) {scanf("%d", &d[i]);}for (int i = 1; i <= n; i++) {scanf("%d", &before[i]);}int i = 2;for (i; i <= n; i++) {comp1 = d;sort(comp1.begin() + 1, comp1.begin() + 1 + i);if (comp1 == before) break;}if (i < n) {//Insertion Sortprintf("Insertion Sort\n");i++;sort(comp1.begin() + 1, comp1.begin() + 1 + i);for (int j = 1; j <= n; j++) {if (j != 1) printf(" ");printf("%d", comp1[j]);}return 0;}//Heap Sortprintf("Heap Sort\n");comp2 = d;createHeap(n);for (i = n; i > 1; i--) {swap(comp2[i], comp2[1]);downAdjust(1, i - 1);if (comp2 == before) {i--;swap(comp2[i], comp2[1]);downAdjust(1, i - 1);for (int j = 1; j <= n; j++) {if (j != 1) printf(" ");printf("%d", comp2[j]);}return 0;}}return 0;
}

dalao的代码

全部代码因版权原因不放出来，大家可以自行去柳神博客购买或者参考晴神的上机笔记~

借鉴点

1. 去背算法笔记上的模板
2. 本题的参考柳神的简便方法，在比较插入的时候先找到非递增的第一个点，然后看从这点开始是否与原始数组一致，如果一致则说明是插入排序，如果不是则说明是堆排序。堆排序的话从后面开始往前扫描，扫描到第一个不递减的点，因为给出的中间序列已经是堆排序中间的步骤了，说明已经是堆的结构，只要从第一个不递减的点开始与第一个点交换然后再downAdjust一下就是所求数列（简洁优美，i了i了）