PAT 1098 Insertion or Heap Sort

题目链接

解题思路

这个题目就是要分别模拟插入排序和堆排序，然后判断，这里使用vector存储数字，方便比较。然后在排序的时候使用flag来记录当前如果相等，就接着再进行一次迭代。

注意

注意堆排序下标要从1开始！！

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
int n;
vector<int> init,part,temp;
void printArr(vector<int> v){
    for(int i=0;i<v.size();i++){
        if (i!=0) printf(" ");
        printf("%d",v[i]);
    }
}

bool insertSort(){
    bool flag=false;
    for(int i=1;i<n;i++){
        sort(init.begin(),init.begin()+i+1);
        if(init==part){
            flag= true;
        }
        if (flag){//如果是插入排序，再打印下一步
            sort(init.begin(),init.begin()+i+2);
            break;
        }
    }
    return flag;
}

void downAdjust(int l,int r){
    int i=l,j=2*i;
    while(j<=r){
        if(j+1<=r&&init[j]<init[j+1]){//比较左右两个节点，用较大的那个与这个根节点比较
            j=j+1;
        }
        if (init[j]>init[i]){//如果根节点比左右子树小，就向下调整
            swap(init[i],init[j]);//交换
            i=j;//向下调整，还是指向欲调整的节点
            j=2*i;//继续向下调整，保持j为i的左孩子
        }else{//如果大于左右子树，说明是这个子树的最大值了，不需要调整了
            break;
        }
    }
}

void heapSort(){
    bool flag=false;
    //1、建堆
    for(int i=n/2;i>=1;i--){
        downAdjust(i,n);
    }
    //2、逐个排序--大的往后调
    for(int i=n;i>1;i--){
        swap(init[i],init[1]);//将根节点与最后面的节点交换位置
        downAdjust(1,i-1);//然后从1到i-1举个排序
        if (init==part){
            flag=true;
        }
        if (flag){//如果是堆排序，就在求下一个迭代
            swap(init[i-1],init[1]);
            downAdjust(1,i-2);
            return;
        }
    }

}


int main(){
    scanf("%d",&n);
    int x;
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        init.push_back(x);
    }
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        part.push_back(x);
    }
    temp=init;
    if(insertSort()){
        printf("Insertion Sort\n");
        printArr(init);
    }else{
        printf("Heap Sort\n");
        init=temp;
        init.insert(init.begin(),-1);//-1填充第0位，使下标从0开始
        part.insert(part.begin(),-1);
        heapSort();
        init.erase(init.begin());
        printArr(init);
    }

    return 0;
}