PTA甲级 1098 Insertion or Heap Sort (25分)

强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的 算法笔记 全名是

算法笔记 上级训练实战指南 //这本都是PTA的题解 算法笔记

PS 今天也要加油鸭

题目原文

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0

Sample Output 1:

Insertion Sort 1 2 3 5 7 8 9 4 6 0

Sample Input 2:

10 3 1 2 8 7 5 9 4 6 0 6 4 5 1 0 3 2 7 8 9

Sample Output 2:

Heap Sort 5 4 3 1 0 2 6 7 8 9

生词如下:

PS:题目看不懂,但好像又没有生词,就很离谱.

Wikipedia 维基百科 (这个词不重要)

consuming 消耗

iterates 迭代

indicate 指示

unique 唯一的

关键句子

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using

现在给定了整数的初始序列，以及某种排序方法多次迭代的结果，您能否确定我们使用的是哪种排序方法

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

对于每个测试用例，在第一行中“插入排序”或“堆排序”中打印以指示用于获取部分结果的方法。 然后运行此方法再进行一次迭代，并在第二行中输出结果序列。 保证答案对于每个测试用例都是唯一的。 一行中的所有数字都必须用空格隔开，并且行末必须没有多余的空格。

题目大意:

给你一串长度为N的序列

然后给出这个序列.插入排序或是堆排序的一个过程序列.

要你求出这个序列是堆排序还是插入排序.

然后输出对应排序的下一个过程

思路如下:

插入排序,我们可以用一个sort来整

然后判断,这个插入是不是插入

不是插入就是堆排序.

然后再做一次堆排序,就OK了

代码如下:

#include<iostream> #include<algorithm> using namespace std; const int N = 111; int origin[N], tempOri[N], changed[N]; int n; bool isSame(int A[],int B[]) { //判断数组A和数组B是否相同 for (int i = 1; i <= n; ++i) if (A[i] != B[i]) return false; return true; } void showArray(int A[]) { //输出数组 for (int i = 1; i <= n; ++i) { printf("%d", A[i]); if (i < n) printf(" "); } printf("\n"); } bool insertSort() { bool flag = false; for (int i = 2; i <= n; ++i) { if (i != 2 && isSame(tempOri, changed)) flag = true; //插入部分直接用sort代替 sort(tempOri, tempOri + i + 1); if (flag == true) return true; } return false; } //对heap数组在[low,high]范围进行调整 //其中low结点欲为调整结点的数组下标,high一般为堆的最后一个元素的数组下标 void downAdjust(int low, int high) { int i = low, j = i * 2; while (j <= high) { if (j + 1 <= high && tempOri[j + 1] > tempOri[j]) j = j + 1; //如果孩子结点中最大的权值比父亲结点大 if (tempOri[j] > tempOri[i]) { swap(tempOri[j], tempOri[i]); i = j; j = i * 2; } else break; } } void heapSort() { bool flag = false; for (int i = n / 2; i >= 1; --i) downAdjust(i, n); for (int i = n; i > 1; --i) { if (i != n && isSame(tempOri, changed)) flag = true; swap(tempOri[i], tempOri[1]); downAdjust(1, i - 1); if (flag == true) { showArray(tempOri); return; } } } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &origin[i]); //输出起始数组 tempOri[i] = origin[i]; //tempOri数组为备份,排序在tempOri上进行 } for (int i = 1; i <= n; ++i) scanf("%d", &changed[i]); if (insertSort()) { //如果插入排序中找到目标数组 printf("Insertion Sort\n"); showArray(tempOri); } else { printf("Heap Sort\n"); for (int i = 1; i <= n; ++i) { tempOri[i] = origin[i]; //还原tempOri数组 } heapSort(); } return 0; }

柳神的思路如下:

分析：插入排序的特点是：b数组前面的顺序是从小到大的，后面的顺序不一定，但是一定和原序列的后面的顺序相同～所以只要遍历一下前面几位，遇到不是从小到大的时候，开始看b和a是不是对应位置的值相等，相等就说明是插入排序，否则就是堆排序啦～

插入排序的下一步就是把第一个不符合从小到大的顺序的那个元素插入到前面已排序的里面的合适的位置，那么只要对前几个已排序的+后面一位这个序列sort排序即可～while(p <= n && b[p - 1] <= b[p]) p++；int index = p；找到第一个不满足条件的下标p并且赋值给index，b数组下标从1开始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1)后的b数组～

堆排序的特点是后面是从小到大的，前面的顺序不一定，又因为是从小到大排列，堆排序之前堆为大顶堆，前面未排序的序列的最大值为b[1]，那么就可以从n开始往前找，找第一个小于等于b[1]的数字b[p]（while(p > 2 && b[p] >= b[1]) p–；），把它和第一个数字交换（swap(b[1], b[p])；），然后把数组b在1~p-1区间进行一次向下调整（downAdjust(b, 1, p - 1)；）～向下调整，low和high是需要调整的区间，因为是大顶堆，就是不断比较当前结点和自己的孩子结点哪个大，如果孩子大就把孩子结点和自己交换，然后再不断调整直到到达区间的最大值不能再继续了为止～

柳神的代码如下:

#include <iostream> #include <algorithm> #include <vector> using namespace std; void downAdjust(vector<int>& b, int low, int high) { int i = 1, j = i * 2; while (j <= high) { if (j + 1 <= high && b[j] < b[j + 1]) j = j + 1; if (b[i] >= b[j]) break; swap(b[i], b[j]); i = j; j = i * 2; } } int main() { int n, p = 2; scanf("%d", &n); vector<int> a(n + 1), b(n + 1); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); while (p <= n && b[p - 1] <= b[p]) p++; int index = p; while (p <= n && a[p] == b[p]) p++; //这段算插入排序的代码确实是秒啊. //你只要插入排序了,前面排序的部分一定是有序的 //后面的部分a[p] 和 b[p] 就一定是相当的 if (p == n + 1) { printf("Insertion Sort\n"); sort(b.begin() + 1, b.begin() + index + 1); } else { printf("Heap Sort\n"); p = n; while (p > 2 && b[p] >= b[1]) p--; swap(b[1], b[p]); downAdjust(b, 1, p - 1); } printf("%d", b[1]); for (int i = 2; i <= n; i++) printf(" %d", b[i]); return 0; }

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.