1098 Insertion or Heap Sort (25 分)

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
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个数字的数列，第二个数列是第一个经过某种排序的中间序列，要求你判断是通过插入排序还是桶排序来的，并输出下一步

算法分析：
经过插入排序的数列，前面几个数是从小到大排序的，后面几个数和原数列一一对应，我们可以按照这个特点判断是不是插入排序。若是，则将后面遇见的第一个不符合从小到大特征的数加入排序，可以直接用sort；若不满足该特点，则是堆排序。堆排序后面几个数是从大到小的，找到第一个不满足从大到小的数，其编号作为上界，进行一次向下调整（这里用到了大顶堆向下调整的模板）

AC代码：

#include<bits/stdc++.h>
using namespace std;
int num;
//大顶堆向下调整模板 
void downAdjust(vector<int> &des,int low,int high){
	int a=1,b=2*a;
	while(b<=high){
		if(des[b+1]>des[b]&&b+1<=high)b=b+1;//注意不要越界 
		if(des[a]>=des[b])break;
		swap(des[a],des[b]);
		a=b;//是从大顶堆调整过来的，没动过的一边就不用改了 
		b=2*a;
	}
}
int main()
{
	cin>>num; 
	vector<int> initial(num+1),des(num+1);
	for(int i=1;i<=num;i++)scanf("%d",&initial[i]);
	for(int i=1;i<=num;i++)scanf("%d",&des[i]);
	//这里一定要从1开始，因为后面有对大顶堆的调整，如果根结点编号设为0就出问题了 
	int temp=2;
	while(temp<=num&&des[temp]>=des[temp-1])temp++;
	int index=temp;
	for(;temp<=num;temp++){
		if(des[temp]!=initial[temp])break;
	}
	//判断前面的数列是否从小到大，后面的数列是否和原来的一样 
	if(temp==num+1){
		printf("Insertion Sort\n");
		sort(des.begin()+1,des.begin()+index+1);//注意sort第二个参数是取不到的，所以要加一 
	}
	else{
		printf("Heap Sort\n");
		for(temp=num;temp>2;temp--){
			if(des[temp]<des[1])break;
		}
		swap(des[1],des[temp]);//找到第一个小于des[1]的数字，和des[1]交换 
		downAdjust(des,1,temp-1);
	} 
	printf("%d",des[1]);
	for(int i=2;i<=num;i++)printf(" %d",des[i]); 
}