浙大数据结构：09-排序2 Insert or Merge

这道题我们采用先判断是不是insert如果不是再用merge算一下
机翻

1、条件准备

首先存元素个数n，然后oldnum存原始数组，newnum存新数组

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int n;
vector<int> oldnum;
vector<int> newnum;

2、主函数

先输入数据，然后判断是不是insert，如果不是则调用merge 来判断

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){int a;cin>>a;oldnum.push_back(a);}for(int i=0;i<n;i++){int a;cin>>a;newnum.push_back(a);}if(!judgeinsert())merge();return 0;
}

3、judgeinsert函数

首先递增遍历一下，直到不递增为止 ，然后比对后面的元素是否都一样，不一样则为merge。
否则为insert，然后根据tag的值来再迭代一次插入排序，然后输出。

bool judgeinsert()
{int tag=0;for(int i=0;i<n-1;i++)if(newnum[tag]<=newnum[tag+1])tag++;tag++;for(int i=tag;i<n;i++)if(oldnum[i]!=newnum[i])return 0;cout<<"Insertion Sort\n";int tmp=newnum[tag]; int i;for( i=tag-1;i>=0&&newnum[i]>tmp;i--)newnum[i+1]=newnum[i];newnum[i+1]=tmp;for(int i=0;i<n-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];return 1;
}

4、numofmerge函数

这个函数是对每lun个元素进行排序，相当于对oldnum数组分块，是merge中的一步，但这里我们单拎出来并只是判断是否迭代到当前了。

int  numofmerge(int lun)
{vector<int> tmpnew=oldnum;for(int i=0;i<tmpnew.size();i+=lun)if(i+lun>tmpnew.size())sort(tmpnew.begin()+i,tmpnew.end());else  sort(tmpnew.begin()+i,tmpnew.begin()+i+lun);for(int i=0;i<tmpnew.size();i++)if(newnum[i]!=tmpnew[i])return 0;return 1;
}

5、merge函数

merge中不同次之间其实就是对2的多少次幂分块再排序，我们从1开始，迭代到按num数量分块的排序产生的数组与newnum一样，然后输出。
接着我们再迭代一次，最后输出。
注意尾部不足num的数量的块则直接到end就行

void merge()
{int num=1;for(;!numofmerge(num);num*=2);cout<<"Merge Sort"<<endl;num*=2;for(int i=0;i<newnum.size();i+=num)if(i+num>newnum.size())sort(newnum.begin()+i,newnum.end());else  sort(newnum.begin()+i,newnum.begin()+i+num);for(int i=0;i<newnum.size()-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];
}

6、总结

这道题难度还行，也算比较有意思的一道题
完整代码如下

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int n;
vector<int> oldnum;
vector<int> newnum;bool judgeinsert()
{int tag=0;for(int i=0;i<n-1;i++)if(newnum[tag]<=newnum[tag+1])tag++;tag++;for(int i=tag;i<n;i++)if(oldnum[i]!=newnum[i])return 0;cout<<"Insertion Sort\n";int tmp=newnum[tag]; int i;for( i=tag-1;i>=0&&newnum[i]>tmp;i--)newnum[i+1]=newnum[i];newnum[i+1]=tmp;for(int i=0;i<n-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];return 1;
}
int  numofmerge(int lun)
{vector<int> tmpnew=oldnum;for(int i=0;i<tmpnew.size();i+=lun)if(i+lun>tmpnew.size())sort(tmpnew.begin()+i,tmpnew.end());else  sort(tmpnew.begin()+i,tmpnew.begin()+i+lun);for(int i=0;i<tmpnew.size();i++)if(newnum[i]!=tmpnew[i])return 0;return 1;
}
void merge()
{int num=1;for(;!numofmerge(num);num*=2);cout<<"Merge Sort"<<endl;num*=2;for(int i=0;i<newnum.size();i+=num)if(i+num>newnum.size())sort(newnum.begin()+i,newnum.end());else  sort(newnum.begin()+i,newnum.begin()+i+num);for(int i=0;i<newnum.size()-1;i++)cout<<newnum[i]<<' ';cout<<newnum[n-1];
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){int a;cin>>a;oldnum.push_back(a);}for(int i=0;i<n;i++){int a;cin>>a;newnum.push_back(a);}if(!judgeinsert())merge();return 0;
}