1098 Insertion or Heap Sort （25 分）（堆）

佚名 5年前 (2018-12-11) 算法 2088人围观抢沙发百度已收录

这里的第二序列相当于是排序还没拍好的序列

对于第二个样例的第二个序列其实已经是大顶堆了然后才进行的堆排序知道这个就好做了

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>

using namespace std;
vector<int>a,b;
int n;
void downAdjust(int low,int high)
{
    int i=low;
    int j=i*2;
    while(j<=high){
        if(j+1<=high&&b[j]<b[j+1]){
            j=j+1;
        }
        if(b[j]>b[i]){
            swap(b[j],b[i]);
            i=j;
            j=i*2;
        }
        else break;
    }
}
int main()
{
    scanf("%d",&n);
    a.resize(n+1);
    b.resize(n+1);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    int flag=2;
    while(flag<=n&&b[flag]>=b[flag-1]) flag++;
    int index=flag;
    while(flag<=n&&a[flag]==b[flag]) flag++;
    if(flag==n+1){
        printf("Insertion Sort\n");
        sort(b.begin()+1,b.begin()+1+index);
        for(int i=1;i<=n;i++){
            if(i!=1) printf(" ");
            printf("%d",b[i]);
        }
    }
    else{
        printf("Heap Sort\n");
        int f=n;
        while(f>1&&b[f-1]<=b[f]){
            f--;
        }

        swap(b[1],b[f]);
        downAdjust(1,f-1);
        for(int i=1;i<=n;i++){
            if(i!=1) printf(" ");
            printf("%d",b[i]);
        }
    }
    return 0;
}