https://www.qianwen.com/share/chat/16477a26b93a41ee99da56220c20a726https://www.qianwen.com/share/chat/16477a26b93a41ee99da56220c20a7267-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:103 1 2 8 7 5 9 4 6 01 2 3 7 8 5 9 4 6 0Sample Output 1:Insertion Sort1 2 3 5 7 8 9 4 6 0Sample Input 2:103 1 2 8 7 5 9 4 6 06 4 5 1 0 3 2 7 8 9Sample Output 2:Heap Sort5 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函数对前i1个元素排序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*i1和2*i2如果是下标从0开始。操作逻辑比较父节点与左右孩子找出三者中的最大值。如果最大值是孩子节点则将父节点与该孩子节点交换。交换后继续以新的位置为父节点重复上述过程直到父节点比孩子都大或者已经下沉到叶子节点为止2。4. 解题的整体算法流程输入读取原始数组origin和中间数组partial。判断先遍历partial数组找到第一个破坏升序的位置i。检查partial从i1到末尾的部分是否和origin完全一致。如果一致→→ 是插入排序。直接对partial的前i1个元素排序并输出。如果不一致→→ 是堆排序。模拟堆排序下一步从后往前找找到第一个小于堆顶partial的元素位置k这就是当前堆的最后一个元素。交换partial和partial[k]。对partial数组的[0, k-1]范围执行一次向下调整Down Adjust。输出结果。掌握以上这些知识点这道题就能迎刃而解了。如果你需要具体的 C/C 代码实现也可以随时告诉我