PAT甲级1098. Insertion or Heap Sort

题意：

根据维基百科：

插入排序迭代，消耗一个输入元素每次重复，并增加排序的输出列表。在每次迭代中，插入排序从输入数据中删除一个元素，在排序列表中找到它所属的位置，并将其插入到其中。它重复，直到没有输入元素保留。

堆排序将其输入分成排序和未排序的区域，并且通过提取最大的元素并将其移动到排序的区域来迭代地缩小未排序的区域。它涉及使用堆数据结构而不是线性时间搜索来查找最大值。

现在给出整数的初始序列，

连同一些序列，这是一些排序方法的几次迭代的结果，你能告诉我们使用哪种排序方法吗？

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行给出正整数N（<= 100）。然后在下一行中，给出N个整数作为初始序列。

最后一行包含N个数的部分排序顺序。假设目标序列总是上升。一行中的所有数字都以空格分隔。

输出规格：

对于每个测试用例，在第一行打印“插入排序”或“堆排序”以指示用于获取部分结果的方法。

然后运行这个方法再进行一次迭代，并在第二行输出修改序列。确保每个测试用例的答案是唯一的。一行中的所有数字必须用一个空格分开，并且行尾不能有额外的空格。

思路：

要了解堆排序的原理。

堆排序

ac代码：

C++

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<stdio.h>

#include<map>

#include<cmath>

#include<unordered_map>

#include<unordered_set>

using namespace std;

int main()

{

	int n;

	scanf("%d", &n);

	vector<int> list1(n);

	vector<int> list2(n);

	for (int i = 0; i < n; i++) scanf("%d", &list1[i]);

	for (int i = 0; i < n; i++) scanf("%d", &list2[i]);

	int pos = 0;

	for (int i = 1; i < n; i++)

	{

		if (list2[i] < list2[i - 1])

		{

			pos = i;

			break;

		}

	}

	bool flag = true;

	for (int i = pos; i < n; i++)

	{

		if (list1[i] != list2[i]) flag = false;

	}

	if (flag)

	{

		printf("Insertion Sort\n");

		sort(list2.begin(), list2.begin() + pos + 1);

		for (int i = 0; i < n - 1; i++)

			printf("%d ", list2[i]);

		printf("%d\n", list2[n - 1]);

	}

	else

	{

		printf("Heap Sort\n");

		sort(list1.begin(), list1.end());

		pos = n - 1;

		while (pos >= 0 && list1[pos] == list2[pos]) pos--;

		int now = 1;

		list2.insert(list2.begin(), 0);

		pos++;

		while (2 * now + 1 <= pos)

		{

			int next;

			if (list2[2 * now + 1] > list2[2 * now]) next = 2 * now + 1;

			else next = 2 * now;

			swap(list2[now], list2[next]);

			now = next;

		}

		swap(list2[now], list2[pos]);

		for (int i = 1; i < n; i++)

			printf("%d ", list2[i]);

		printf("%d\n", list2[n]);

	}

    return 0;

}