【PAT甲级 - C++题解】1098 Insertion or Heap Sort

1098 Insertion or Heap Sort

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
• 1
• 2
• 3

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
• 1
• 2
• 3

Sample Output 2:

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

题意

根据维基百科：

插入排序迭代，每次将一个插入元素插入到排好序的输出序列中，每次迭代插入排序都会从输入数据中移除一个元素，并在已排好序的序列中找到它所属的位置，然后将其插入。直到没有输入元素剩余为止。

堆排序将其输入分为已排序和未排序两个区域，并通过提取未排序区域中的最大元素并将其移至已排序的区域来迭代地缩小未排序的区域。它通过使用堆数据结构而非线性时间搜索来找到最大值。

现在给定两个数组，第一个数组是初始数组，第二个数组是已经进行过排序的数组，但是还没有排完序，需要我们去判断这个还没排完序的数组它是用了插入排序还是堆排序的方法。

然后输出对应的排序方法，并用该排序方法再往后进行一次迭代，并输出。

思路

快速排序： 迭代数组前面的元素是有序的，后面的元素是无序的。

堆排序： 迭代数组后面的元素是有序的，前面元素在堆中即无序的。

具体步骤如下：

输入两个数组 a 和 b 。

不管三七二十一，我都先把数组 b 当做前面是有序的，然后找到数组中从前往后哪个地方开始是无序的。然后用 k 保存该位置，再继续往后对比 b 数组中 k 以后的元素是否与 a 数组中 k 以后的元素都相同，因为如果是插入排序，每次迭代都只会往后取一位元素跟前面排好序的元素进行对比，其后面的元素是没被动过的；而堆排序每次迭代都要将堆顶元素放到数组后面，所以不会跟原数组一样。

判断是哪个排序，然后进行对于排序的下一次迭代操作。

输出迭代后的数组。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N], b[N];
//堆排序操作
void down(int u, int len)
{
    //找到当前结点与其左右结点中的最大值
    int t = u;
    if (u * 2 <= len && b[t] < b[u * 2])   t = u * 2;
    if (u * 2 + 1 <= len && b[t] < b[u * 2 + 1])   t = u * 2 + 1;
    if (t != u)    //如果最大值在其孩子结点，则进行交换并继续递归
    {
        swap(b[u], b[t]);
        down(t, len);
    }
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)   cin >> a[i];
    for (int i = 1; i <= n; i++)   cin >> b[i];
    int p = 2;
    while (p <= n && b[p] >= b[p - 1])   p++;    //如果b前面有序，找到分界线位置
    int k = p;
    while (p <= n && a[p] == b[p]) p++;    //如果是插入排序，k往后a和b都应该相等
    if (p == n + 1) //如果是插入排序
    {
        cout << "Insertion Sort" << endl;
        while (k >= 1 && b[k] < b[k - 1])    swap(b[k], b[k - 1]), k--;
    }
    else    //如果是堆排序
    {
        cout << "Heap Sort" << endl;
        p = n;    //找到b后面有序的分界线位置
        while (b[1] <= b[p])   p--;    //堆顶元素要比已排好序的元素要小
        swap(b[1], b[p]);
        down(1, p - 1);
    }
    //输出下一趟排序的序列
    cout << b[1];
    for (int i = 2; i <= n; i++)  cout << " " << b[i];
    cout << endl;
    return 0;
}