天天看点

PAT(Advance) 1098. Insertion or Heap Sort (25)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> orignal,target,result;

bool InsertSort(){
    int flag = ;
    //result.clear();
    result = orignal;
    for(int i = ;i<result.size()&&flag<;i++){
        if(flag)
            flag++;
        int j = i-;
        int ele = result[i];
        while(j>=&&result[j]>ele){
            result[j+] = result[j];
            j--;
        }
        result[j+] = ele;
        if(result == target)
            flag = ;
    }
    if(flag == )
        return true;
    else return false;
}

void PrecDown(int i,int end){
    int tmp,child;
    for(tmp = result[i];*i + <end;i = child){
        child = *i +;
        if(child!=end-&&result[child]<result[child+])
            child++;
        if(tmp<result[child])
            result[i] = result[child];
        else break;
    }
    result[i] = tmp;
}

void HeapSort(){
    result = orignal;
    for(int i = result.size()/;i>=;i--)
        PrecDown(i,result.size());
    int flag = ;
    for(int i = result.size()-;i>=&&flag<;i--){
        //if(flag)
          //  flag++;
        if(result == target)
            flag = ;
        int tmp = result[];
        result[] = result[i];
        result[i] = tmp;
        PrecDown(,i);
    }
}

int main(){
    int numofarr;
    cin >> numofarr;
    int ele;
    for(int i = ;i<numofarr;i++){
        cin >> ele;
        orignal.push_back(ele);
    }
    for(int i = ;i<numofarr;i++){
        cin >> ele;
        target.push_back(ele);
    }
    if(InsertSort()){
        cout << "Insertion Sort"<<endl;
    }
    else {
        cout << "Heap Sort" << endl;
        HeapSort();
    }
    for(int i = ;i<result.size();i++){
        cout << result[i];
        if(i == result.size() - )
            cout << endl;
        else cout << ' ';
    }
    return ;
}
           
PAT