题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805368847187968
排序题，有点惭愧忘了堆排序的内容。。赶紧复习了下。
题目大意：给一个原序列和一个部分排序了的序列，判断后者是用插入排序还是堆排序，并给出下一轮该排序的结果。
插排：整个arr里，左边是排好序的，右边是没排好序的。排好序的部分长度为len。每次抽一个新元素key，从【排好序的部分】的末尾开始比较，如果arr[j]比key大，说明arr[j]要【往后移了】，因为key必然排在他们前面；反之，如果arr[j]比key小，那么key就找到自己的位置了，应该排在arr[j]其后。
void insertOne(vector<int>& arr, int len) {
int key = arr[len+1];int j;for (j = len; j >= 0; j--) {
if (key < arr[j])arr[j+1] = arr[j];elsebreak;}arr[j+1] = key;
}【一个细节】：开始时想着从【排好序的部分】的开头开始比较，但比key小的部分实际上不需要位移，而比key大的部分无论如何都要位移，这样就算找到了key的位置，key后面的那些大的部分依然要再扫描过，时间为O(N)，有点浪费时间了。而如果从【排好序的部分】的末尾开始比较的话，一般只用O(N/2)。
堆排序：
- 首先要先建好堆，并且是一个大顶堆，所以最上面的元素
arr[0]是最大的 - 然后把这个最大元素和末尾元素交换
- 执行
percolateDown()，下滤，此举是为了保持大顶堆的特性，也是为了再次将剩下部分的最大元素放到顶端。注意此时堆的size已经减小了1，因为末尾的元素（上一轮的最大元素）已经是排好序的一部分了，它不再参与下滤！ - 重复2、3直至堆的size为0
在堆下滤时，是从【最后一个父节点】开始的，和儿子们比较后，若父亲比儿子们都大，那无事发生；否则，将更大的儿子与父亲交换。重点在于：交换后，【其子树不一定保持堆堆特性了】，所以要要从交换后的子树开始又滤到底！
while (child <= end) {
if (child+1 <= end && arr[child] < arr[child+1])child++;if (arr[dad] > arr[child])return;else {
int tmp = arr[dad];arr[dad] = arr[child];arr[child] = tmp;dad = child;child = dad * 2 + 1;}}
总结：实质上还是考两种排序算法，搞清楚他们每一轮做了什么就行。
完整代码
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>using namespace std;void outputArr(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
if (i == 0)printf("%d", arr[i]);elseprintf(" %d", arr[i]);}
}void insertOne(vector<int>& arr, int len) {
int key = arr[len+1];int j;for (j = len; j >= 0; j--) {
if (key < arr[j])arr[j+1] = arr[j];elsebreak;}arr[j+1] = key;
}void percolateDown(vector<int>& arr, int dad, int end) {
int child = dad * 2 + 1;while (child <= end) {
if (child+1 <= end && arr[child] < arr[child+1])child++;if (arr[dad] > arr[child])return;else {
int tmp = arr[dad];arr[dad] = arr[child];arr[child] = tmp;dad = child;child = dad * 2 + 1;}}
}void buildHeap(vector<int>& arr) {
for (int i = arr.size()/2 - 1; i >= 0; i--)percolateDown(arr, i, arr.size()-1);
}void heapOne(vector<int>& arr, int it_times) {
int tmp = arr[0], last_idx = arr.size() - it_times - 1;arr[0] = arr[last_idx];arr[last_idx] = tmp;percolateDown(arr, 0, last_idx-1);
}bool cmpFun(vector<int>& arr1, vector<int>& arr2) {
for (int i = 0; i < arr1.size(); i++) {
if (arr1[i] != arr2[i])return false;}return true;
}int main() {
int N, tmp;scanf("%d", &N);vector<int> arr_is;for (int i = 0; i < N; i++) {
scanf("%d", &tmp);arr_is.push_back(tmp);}vector<int> arr_hp(arr_is);vector<int> part;for (int i = 0; i < N; i++) {
scanf("%d", &tmp);part.push_back(tmp);}bool is_is = false;int it_times;for (it_times = 0; it_times < N; it_times++) {
if (it_times != N-1)insertOne(arr_is, it_times);if (cmpFun(part, arr_is)) {
is_is = true; break;}}if (is_is) {
printf("Insertion Sort\n");insertOne(arr_is, it_times+1);outputArr(arr_is);}else {
printf("Heap Sort\n");buildHeap(arr_hp);it_times = 0;while (cmpFun(part, arr_hp) == false) {
heapOne(arr_hp, it_times);it_times++;}heapOne(arr_hp, it_times);outputArr(arr_hp);}return 0;
}