算法笔记--归并排序-白红宇

算法笔记--归并排序

阅读量：6819 次

发布时间：2019-06-26

本文共 2081 字，大约阅读时间需要 6 分钟。

很简单的一个排序，先通过递归划分区间到最小（因为一个元素具有单调性），然后再合并两个单调区间为一个单调区间，具体看代码

模板：

void Merge(int l,int m,int r){    int i=l;    int j=m+1;    int k=l;    while(i<=m&&j<=r)    {        if(a[i]>a[j])        {            temp[k++]=a[j++];        }        else temp[k++]=a[i++];    }    while(i<=m)temp[k++]=a[i++];    while(j<=r)temp[k++]=a[j++];    for(int i=l;i<=r;i++)    a[i]=temp[i];}void Merge_sort(int l,int r){    if(l
     
      >1;        Merge_sort(l,m);        Merge_sort(m+1,r);        Merge(l,m,r);    }}

例题1：

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e3+5;int a[N];int temp[N];int cnt;void Merge(int l,int m,int r){ int i=l; int j=m+1; int k=l; while(i<=m&&j<=r) { if(a[i]>a[j]) { temp[k++]=a[j++]; cnt+=m-i+1; } else temp[k++]=a[i++]; } while(i<=m)temp[k++]=a[i++]; while(j<=r)temp[k++]=a[j++]; for(int i=l;i<=r;i++) a[i]=temp[i];}void Merge_sort(int l,int r){ if(l
               
                >1; Merge_sort(l,m); Merge_sort(m+1,r); Merge(l,m,r); }}int main(){ ios::sync_with_stdio(false); cin.tie(0); int T,n; cin>>T; int cs=0; while(T--) { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cnt=0; Merge_sort(1,n); cout<<"Scenario #"<<++cs<<":"<
                
                 <
                 
                  <
                  
                   <

View Code

例题2：Codeforces

归并排序逆操作

#include
      
       using namespace std;#define ll long long#define ls rt<<1,l,m#define rs rt<<1|1,m+1,r#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;const int INF=0x3f3f3f3f;int k,n;int a[N];void Merge_sort(int l,int r){    if(!k)return ;    if(l+1
       
        >1;        swap(a[m],a[m-1]);        k--;        k--;        if(k)        {            Merge_sort(l,m);            Merge_sort(m,r);        }    }    else return ;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>k;    if(k&1)    {        for(int i=0;i

View Code

转载于:https://www.cnblogs.com/widsom/p/8005702.html

你可能感兴趣的文章

关于域证书的发布CA和CRL的内容（Windows 2008 Server R2 SP1）

查看>>

软件测试英语专业词汇汇总

查看>>

Java实现word文档在线预览，读取office(word,excel,ppt)文件