个人练习- PAT甲级-1098 Insertion or Heap Sort

本文主要是介绍个人练习- PAT甲级-1098 Insertion or Heap Sort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接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;
}