算法初步—— two pointers B1035/A1089 Insert or Merge （内含插入排序和归并排序）

#include <bits/stdc++.h>
#include<math.h>
#include <string>
using namespace std;
const int N = 111;
int origin[N],tempOri[N],changed[N];//原始数组，原始数组备份，目标数组
int n;//元素个数
bool isSame(int A[],int B[]){
    for(int i =0;i<n;++i){
        if(A[i] != B[i]){
            return false;
        }
    }
    return true;
}
bool showArray(int A[]){//输出数组
    for(int i = 0;i<n;++i){
        cout<<A[i];
        if(i<n-1){
            cout<<" ";
        }
    }
    cout<<endl;
}
bool insertSort(){//插入排序
    bool flag = false;
    for(int i=1;i<n;++i){//进行n-1趟排序
        if(i != 1 && isSame(tempOri,changed)){
            flag = true;
        }
        //以下为插入部分
        int temp = tempOri[i],j = i;
        while(j > 0 && tempOri[j - 1]>temp){
            tempOri[j] = tempOri[j-1];
            j--;
        }
        tempOri[j] = temp;
        if(flag == true){
            return true;
        }
    }
    return false;
}
void mergeSort(){
    bool flag = false;//记录是否存在数组中间步骤与changed数组相同
    //以下为归并排序部分
    for(int step = 2;step/2<=n;step *= 2){
        if(step != 2 && isSame(tempOri,changed)){
            flag = true;
        }
        for(int i =0;i<n;i += step){
            sort(tempOri+i,tempOri+min(i+step,n));
        }
        if(flag == true){
            showArray(tempOri);
            return;
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>origin[i];
        tempOri[i] = origin[i];//tempOri数组为备份，排序过程在tempOri上进行
    }
    for(int i =0;i<n;++i){
        cin>>changed[i];
    }
    if(insertSort()){
        printf("Insertion Sort\n");
        showArray(tempOri);
    }else{
        printf("Merge Sort\n");
        for(int i=0;i<n;++i){
            tempOri[i] = origin[i];//还原tempOri数组
        }
        mergeSort();
    }
    system("pause");
    return 0;
}