当前位置：首页 > backend >正文

PAT 1089 Insert or Merge

backend 2025/9/2 9:34:42

在这里插入图片描述

这一题给出了一个原始的序列，然后给出一个还未完全排的序列，让我们判断采用的是插入排序还是归并排序，并且输出下一趟的排序序列。
思路很简单，只需要模拟排序的过程，然后判断给出的那个未完全排的序列是不是符合其中的一趟即可，并且输出下一趟的排序序列。
因此我们需要对插入排序和归并排序很清楚才行
对于插入排序一文讲透：

算法：插入排序

对于归并排序一文讲透：

算法：归并排序

而解决这一题只需要模拟这两个排序算法即可，我是先判断它是不是插入排序，如果是就输出，如果不是，就让它模拟归并排序，再输出。
完整代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
int n;
vector<int> initalsq(105);
vector<int> tempsq(105);
bool isinsert_sort(vector<int>& initalsq,vector<int>& tempsq)
{bool flag=0;for(int i=1;i<n;i++){int k=0;int x=initalsq[i];int j;for(j=i;j>0;j--){if(initalsq[j-1]>x){initalsq[j]=initalsq[j-1];}else{break;}}initalsq[j]=x;if(flag==1){for(int q=0;q<n;q++){if(q!=0)cout<<" ";cout<<initalsq[q];}}if(initalsq==tempsq){flag=1;//说明是插入排序cout<<"Insertion Sort"<<endl;}}if(flag==1){return true;}else{return false;}
}
void merge(vector<int>&a,int step,int n,vector<int>& tempsq)
{vector<int> temp(a);for(int i=0;i+step<n;i+=2*step){int l=i;int m=i+step;int r=min(i+2*step,n);inplace_merge(temp.begin()+l,temp.begin()+m,temp.begin()+r);}a=temp;}
void merge_sort(vector<int>& initalsq,int n,vector<int>& tempsq)
{bool flag=0;for(int i=1;i<n;i*=2){merge(initalsq,i,n,tempsq);if (flag) { for (int k = 0; k < n; k++) {if (k) cout << " ";cout<<initalsq[k];}return;}if (initalsq==tempsq) flag = true;}}
void ismerge_sort(vector<int>& initalsq,vector<int>& tempsq)
{merge_sort(initalsq,n,tempsq);
}
int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(cin>>n;for(int i=0;i<n;i++){cin>>initalsq[i];}for(int i=0;i<n;i++){cin>>tempsq[i];}vector<int> t=initalsq;if(isinsert_sort(initalsq,tempsq)){}else{cout<<"Merge Sort"<<endl;ismerge_sort(t,tempsq);}return 0;}