浙大数据结构：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;
}