题目链接：https://pintia.cn/problem-sets/1110537862649819136/problems/1110537981575114765
题目大意：
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
堆排序也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
具体思路：对于这里的插入排序，我们直接从左往有移动，看哪一个先不符合递增，然后再对这一段进行排序就好了（看样例猜的）。
然后堆排序，先讲一下原理吧，具体的大顶堆，就是第一个形成的堆第一个元素是这一段区间中的最大的。然后每一个我们选出最大的，放在最后。如果一个序列有n个元素的话，我们操作n-1次就可以了，每一次从[1,i]区间选择最大的。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e4+100; 6 int a[maxn]; 7 int b[maxn]; 8 void cal(int l,int r){ 9 int i=l,j=i*2; 10 while(j<=r){ 11 if(j+1<=r&&b[j]<b[j+1]) 12 j++; 13 if(b[j]>b[i]){ 14 swap(b[i],b[j]); 15 i=j; 16 j=i*2; 17 } 18 else 19 break; 20 } 21 } 22 int main() 23 { 24 int n; 25 scanf("%d",&n); 26 for(int i=1; i<=n; i++) 27 { 28 scanf("%d",&a[i]); 29 } 30 for(int i=1; i<=n; i++) 31 { 32 scanf("%d",&b[i]); 33 } 34 int flag=-1; 35 int i; 36 for( i=1; i<=n; i++) 37 { 38 if(i==1) 39 continue; 40 else if(b[i]>=b[i-1]) 41 continue; 42 else 43 { 44 flag=i; 45 break; 46 } 47 } 48 if(flag!=2) 49 { 50 sort(b+1,b+flag+1); 51 printf("Insertion Sort "); 52 for(int i=1; i<=n; i++) 53 { 54 if(i==1) 55 printf("%d",b[i]); 56 else 57 printf(" %d",b[i]); 58 } 59 printf(" "); 60 } 61 else 62 { 63 printf("Heap Sort "); 64 int pos=n; 65 while(pos>=2&&b[pos]>b[pos-1]) 66 pos--; 67 swap(b[1],b[pos]); 68 cal(1,pos-1); 69 for(int i=1; i<=n; i++) 70 { 71 if(i==1) 72 printf("%d",b[i]); 73 else 74 printf(" %d",b[i]); 75 } 76 printf(" "); 77 } 78 return 0; 79 }