本文共 909 字，大约阅读时间需要 3 分钟。

【题意】

给定一个序列的初始状态和经过某种排序几个步骤之后的结果，要求判断是插入排序还是堆排序，并输出执行下一个步骤之后的结果。

【题解】

不清楚插入排序和堆排序的请移步：

首先，我们根据排序过程中得到的序列判断是哪种排序。怎么判断呢？如果能把序列分成两段，前一段是有序的，后一段是跟原序列相同的，这样就是插入排序；否则是堆排序。如果是插入排序，那么我们只需要将下一个元素加入到前一段中排个序即可；如果是堆排序，我们只需要寻找到最后一个没完成排序的位置，交换首尾的位置，再把这个位置之前的所有元素依次向下调整为大顶堆即可。

【代码】

#include 
   
    using namespace std;int a[105],b[105];int main(){    int n; scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    for(int i=1;i<=n;i++) scanf("%d",&b[i]);    int l,r,f=1;    for(l=1;l<=n;l++)        if(b[l]>b[l+1]) break;    for(r=n;r>l;r--)        if(a[r]!=b[r]) f=0;    if(f){        printf("Insertion Sort\n");        sort(b+1,b+l+2);    }    else{        printf("Heap Sort\n");        sort(a+1,a+1+n);        for(l=n;b[l]==a[l];l--);        swap(b[1],b[l]);        l--;        for(int i=l/2;i>=1;i--){            int flag=1,pos=i;            while(flag){                int t=pos;                if(pos*2<=l&&b[t]
   

转载地址：http://ehfen.baihongyu.com/