题目就是给两个序列，第一个是排序前的，第二个是排序中的，判断它是采用插入排序还是堆排序，并且输出下一次操作后的序列。
插入排序的特点就是，前面是从小到大排列的，后面就与原序列相同。
堆排序的特点就是，后面是从小到大排列的最大的几个数p~n-1，前面第一位则是p-1。
所以只要先按照插入排序的特点来判断是否为插入排序，接下来再进行操作就可以了，这里要手动写下最大堆的更新操作。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
/* 之前一直WA的原因是，用for循环写寻找idx一开始就写错了。。。
找了整个序列的<，应该是找反例>从而跳出for循环，或者直接加到条件里。
比如：
一开始这么写，
for(int i=0;i<n;i++){
if(num2[i]<=num2[i+1])
idx++;
}
正确应该是:
for(idx=0;idx<n-1 && num2[idx]<=num2[idx+1];idx++);
晕死。。。脑子糊涂了
*/
using namespace std;
const int maxn=;
int heap[maxn];
int heap_size=; void swaps(int &a,int &b){
int tmp;
tmp=a;
a=b;
b=tmp;
}
void heap_update(int i){
int bigger=i;
int l=(i<<)+;
int r=(i<<)+;
if(l<heap_size && heap[l]>heap[i])
bigger=l;
if(r<heap_size && heap[r]>heap[bigger])
bigger=r;
if(bigger!=i){
swaps(heap[i],heap[bigger]);
heap_update(bigger);
}
}
void heap_pop(){
if(heap_size>=){
swaps(heap[],heap[heap_size-]); //take the max to the rear.
heap_size--;
heap_update();
}
} int main()
{
int n;
int num[maxn],num2[maxn]; scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d",&num[i]);
}
for(int i=;i<n;i++){
scanf("%d",&num2[i]);
}
int idx;
for(idx=;idx<n- && num2[idx]<=num2[idx+];idx++);
int p=idx+;
for(;p<n && num[p]==num2[p];p++);
if(p==n){
sort(num2,num2+idx+); //相当于将num[idx+1]插入到前面排序
printf("Insertion Sort\n");
for(int i=;i<n-;i++)
printf("%d ",num2[i]);
printf("%d",num2[n-]);
}
else{
int sortedsize=;
int tmpnum[maxn];
for(int i=;i<n;i++)
tmpnum[i]=num[i];
sort(tmpnum,tmpnum+n);
p=n-;
/*
看了别人网上有写第三行AC的，
但按道理来说，如果样例2的第二个序列是6 4 5 0 1 2 3 7 8 9,那明显第三行就不对额。 10
3 1 2 8 7 5 9 4 6 0
6 4 5 0 1 2 3 7 8 9
Heap Sort
5 4 3 0 1 2 6 7 8 9 (第一行的输出)
5 4 0 6 1 2 3 7 8 9 (第三行的输出)
*/
for(;p>= && num2[p]==tmpnum[p];p--);
//for(;p>=1 && num2[p]>=num2[0];p--);
//for(;p>=1 && num2[p]>=num2[p-1];p--); //个人认为应该是过不了的。。。但却AC了 heap_size=p+;
for(int i=;i<n;i++)
heap[i]=num2[i];
heap_pop();
printf("Heap Sort\n");
for(int i=;i<n-;i++){
printf("%d ",heap[i]);
}
printf("%d",heap[n-]);
}
return ;
}