PAT A1098 Insertion or Heap Sort (25分)(初始序列不參與是否與目標序列相同&&堆排序)

題目大意：給出n和n個數的序列a和b，a為原始序列，b為排序其中的一個步驟，問b是a經過了堆排序還是插入排序的，并且輸出它的下一步～

分析：插入排序的特點是：b數組前面的順序是從小到大的，后面的順序不一定，但是一定和原序列的后面的順序相同～所以只要遍歷一下前面幾位，遇到不是從小到大的時候，開始看b和a是不是對應位置的值相等，相等就說明是插入排序，否則就是堆排序啦～

插入排序的下一步就是把第一個不符合從小到大的順序的那個元素插入到前面已排序的里面的合適的位置，那么只要對前幾個已排序的+后面一位這個序列sort排序即可～while(p <= n && b[p - 1] <= b[p]) p++；int index = p；找到第一個不滿足條件的下標p并且賦值給index，b數組下標從1開始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1)后的b數組～

堆排序的特點是后面是從小到大的，前面的順序不一定，又因為是從小到大排列，堆排序之前堆為大頂堆，前面未排序的序列的最大值為b[1]，那么就可以從n開始往前找，找第一個小于等于b[1]的數字b[p]（while(p > 2 && b[p] >= b[1]) p--；），把它和第一個數字交換（swap(b[1], b[p])；），然后把數組b在1~p-1區間進行一次向下調整（downAdjust(b, 1, p - 1)；）～向下調整，low和high是需要調整的區間，因為是大頂堆，就是不斷比較當前結點和自己的孩子結點哪個大，如果孩子大就把孩子結點和自己交換，然后再不斷調整直到到達區間的最大值不能再繼續了為止～

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 110;
vector<int> list,target,temp;
int n;

bool insertsort(){
    temp = list;
    for(int i = 1;i<n;i++){
        sort(temp.begin(),temp.begin()+i);
        if(i!=1&&temp==target){
            sort(temp.begin(),temp.begin()+i+1);
            return true;
        }
    }
    return false;
    
}
void downadjust(int low,int high){
    int i  = low,j = 2*i+1;
    while(j<=high){
        if(j+1<=high&&temp[j+1]>temp[j]){
            j = j+1;
        }
        if(temp[j]>temp[i]){
            swap(temp[j],temp[i]);
            i = j;
            j = 2*i+1;
        }else{
            break;
        }
    }
    
}

bool heapsort(){
    temp = list;
    for(int i = n/2;i>=0;i--){
        downadjust(i,n-1);
    }
    for(int i  = n-1;i>0;i--){
        if(i!=n-1&&temp==target){
           swap(temp[i],temp[0]);
            downadjust(0,i-1);
            return true;
        }
        swap(temp[i],temp[0]);
        downadjust(0,i-1);
    }
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        int num;
        scanf("%d",&num);
        list.push_back(num);
    }
    for(int i = 0;i<n;i++){
        int num;
        scanf("%d",&num);
        target.push_back(num);
    }    
    //insertsort
    if(insertsort()==true){
        printf("Insertion Sort\n");
        for(int i = 0;i<n;i++){
            printf("%d",temp[i]);
            if(i!=n-1) printf(" ");
        }
    }else if(heapsort()==true){
        printf("Heap Sort\n");
        for(int i = 0;i<n;i++){
            printf("%d",temp[i]);
            if(i!=n-1) printf(" ");
        }        
    }
    return 0;
}