https://www.qianwen.com/share/chat/16477a26b93a41ee99da56220c20a726https://www.qianwen.com/share/chat/16477a26b93a41ee99da56220c20a726

7-1 Insertion or Heap Sort

分数 8

作者 陈越

单位 浙江大学

According to Wikipedia:

Insertion sortiterates, 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 sortdivides 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 non-decreasing. 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

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

这是一道非常经典的算法逻辑题，考察的并不是让你从零写一个排序算法，而是考察你对插入排序（Insertion Sort）和堆排序（Heap Sort）内部执行过程（中间状态）的深刻理解。

这道题的核心思路是：通过观察“中间序列”的特征，反推它到底是哪种排序算法，并模拟该算法再走一步。

以下是这道题涉及的详细知识点拆解：

1. 插入排序（Insertion Sort）的特征与模拟

• 核心特征：插入排序的过程是将数组分为“已排序”和“未排序”两部分。在每一轮迭代中，它会把未排序部分的第一个元素插入到已排序部分的正确位置。

• 中间序列的判别特征：
  • 数组的前一部分是有序的（从小到大）。
  • 数组的后一部分与原始数组完全相同（还没被处理过）10。
  • 例如 Sample 1 中，中间序列是1 2 3 7 8 5 9 4 6 0。你会发现1 2 3 7 8是有序的，而从5开始的后面部分5 9 4 6 0和原始数组3 1 2 8 7 5 9 4 6 0的后半部分完全一样。这就暴露了它是插入排序。
• 如何“再走一步”：
  • 找到已排序部分的下一个元素（即第一个破坏有序的元素），将其插入到前面已排序序列的正确位置。在代码实现中，直接对前面那一段有序部分再多排一个元素即可（比如用sort函数对前i+1个元素排序）6。

2. 堆排序（Heap Sort）的特征与模拟

• 核心特征：堆排序（这里指升序排序）通常使用最大堆（Max-Heap）。它会将堆顶的最大元素与当前未排序部分的最后一个元素交换，然后缩小堆的范围，并对新的堆顶进行“向下调整（Down Adjust / Heapify）”1。
• 中间序列的判别特征：
  • 数组的后一部分是有序的，并且这部分元素是整个数组中最大的那几个（因为每次都是把最大值交换到末尾）2。
  • 数组的前一部分是一个最大堆（虽然看起来乱序，但满足父节点大于子节点的性质）5。
  • 例如 Sample 2 中，中间序列是6 4 5 1 0 3 2 7 8 9。你会发现末尾的7 8 9是全局最大的三个数且有序，而前面的6 4 5 1 0 3 2则构成了一个最大堆。
• 如何“再走一步”：
  • 找到当前堆的最后一个元素（也就是有序部分的前一个元素）。
  • 将堆顶元素（数组第1个）与这个元素交换。
  • 对交换后的堆顶元素，在前面的未排序区域内执行一次向下调整（Down Adjust）操作，使其重新满足最大堆的性质2。

3. 最大堆的向下调整算法（Down Adjust）

这是堆排序中最核心的操作。假设父节点的下标是i，它的左右孩子下标分别是2*i+1和2*i+2（如果是下标从0开始）。

• 操作逻辑：
  1. 比较父节点与左右孩子，找出三者中的最大值。
  2. 如果最大值是孩子节点，则将父节点与该孩子节点交换。
  3. 交换后，继续以新的位置为父节点，重复上述过程，直到父节点比孩子都大，或者已经下沉到叶子节点为止2。

4. 解题的整体算法流程

1. 输入：读取原始数组origin和中间数组partial。
2. 判断：
   • 先遍历partial数组，找到第一个破坏升序的位置i。
   • 检查partial从i+1到末尾的部分，是否和origin完全一致。
   • 如果一致→→ 是插入排序。直接对partial的前i+1个元素排序并输出。
   • 如果不一致→→ 是堆排序。
3. 模拟堆排序下一步：
   • 从后往前找，找到第一个小于堆顶（partial）的元素位置k（这就是当前堆的最后一个元素）。
   • 交换partial和partial[k]。
   • 对partial数组的[0, k-1]范围执行一次向下调整（Down Adjust）。
   • 输出结果。

掌握以上这些知识点，这道题就能迎刃而解了。如果你需要具体的 C/C++ 代码实现，也可以随时告诉我！