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 resuling 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
题目大意：判断插入排序还是堆排序。第一行给定一个数字n，接着给出n个数，表示原始序列，接着再给出n个数，表示尚未完成排序的序列，要求判断这个尚未完成排序的序列使用的是插入排序还是堆排序，如果是插入排序，输出Insertion Sort，堆排序则输出Heap Sort，并另起一行给出下一步排序的序列
这是一个排序算法类问题，考察插入排序和堆排序的过程，插入排序的特征是前面的序列是有序的，后面的序列和原始序列相同，堆排序的特征是后面的序列是有序的，前面的序列形成一个大顶堆。但是判断是不是大顶堆需要建堆操作，过程比较繁琐，所以只需要判断是不是插入排序即可，不是插入排序则一定是堆排序了。
在求解下一步排序的序列时，如果是插入排序，则找到第一个无序数字的位置，将其插入到序列中。（答案中偷懒了，没有使用插入排序，使用了sort自带的排序），而堆排序，序列中第一个是堆顶，下一步要插入到其后继数字的前面的位置，使用swap交换后继数字前面的数字和堆顶即可，接着对前面的无序序列执行一个向下调整即可。
提示：测试点0、2、4是插入排序，1、3、5是堆排序
注意：特别注意插入排序中有相同的数字，例如12333465下一步是12333456而不是12333465。如果倒数第二个测试点出现问题，要特别注意是不是并列数字的判断上出了问题。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 110
int ori[MAXN], input[MAXN];
void Print(int arr[], int n){
for(int i = 1; i <= n; i++){
cout << arr[i];
if(i != n) cout << ' ';
}
}
void DownAdjust(int low, int high){
int i = low, j = low * 2; //i=>要调整的节点，j=>其左叶子
if(j > high) return; //i节点是叶子节点，直接返回
int max_idx = i;
if(input[j] > input[i]) max_idx = j; //如果左叶子比根节点大，最大下标为左孩子
if(j + 1 <= high) //如果右叶子存在
if(input[j + 1] > input[max_idx]) max_idx = j + 1; //并且右叶子比刚刚找到最大的还大，更新最大下标
if(max_idx == i) return; //如果堆的顺序已经正确，则直接返回
swap(input[i], input[max_idx]); //执行交换
DownAdjust(max_idx, high);
}
int main(){
int sum;
cin >> sum;
//读取数据
for(int i = 1; i <= sum; i++)
cin >> ori[i];
for(int i = 1; i <= sum; i++)
cin >> input[i];
//判断是不是插入排序
int p = 2, index;
while(p <= sum && input[p] >= input[p - 1]) p++; //这里不加等于号，倒数第二个测试点过不去
index = p;
while(p <= sum && input[p] == ori[p]) p++;
if(p == sum + 1){
//插入排序
cout << "Insertion Sort" << endl;
if(index <= sum) //如果index <= sum说明序列不是有序的
sort(input + 1, input + index + 1);
}else{
//堆排序
cout << "Heap Sort" << endl;
int top = input[1];
int prev;
for(prev = sum; input[prev] > top && prev >= 1; prev--);
swap(input[prev], input[1]);
DownAdjust(1, prev-1);
}
Print(input, sum);
cout << endl;
return 0;
}//0 2 4 ins