重写二路归并排序

2019-09-23 08:42:04来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

重写二路归并排序

利用两个数组互相作为对方的辅助数组来实现,先二路划分,再从单个元素开始归并。代码如下:

/*
    二路归并排序,采用了递归的做法,它首先将整个队列划分为两个部分,再一次对这两个部分进行二分操作,
    直到每个部分只包含一个元素为止,然后再依次对这些只包含一个元素的部分开始进行归并,然后递归操作会依次向上
    进行回溯,最后返回已排好序的队列,排序完成。
    时间复杂度n*log2n  
*/
#include <iostream>
using namespace std;

void merge(int * b,int * t,int s,int mid,int e){
    int i=s;
    int j=mid+1;
    int idx=s;
    while(i<=mid&&j<=e)
    {
        if(b[i]<b[j])
        {
            t[idx++]=b[i++];
        }
        else
        {
            t[idx++]=b[j++];
        }
    }
    while(i<=mid)
    {
        t[idx++]=b[i++];
    }
    while(j<=e)
    {
        t[idx++]=b[j++];
    }
}
void TwoGuiBing(int * a,int * t,int s,int e){
    if(s==e)
    {
        t[s]=a[s];
        return;
    }
    int mid=(s+e)/2;
    TwoGuiBing(t,a,s,mid);
    TwoGuiBing(t,a,mid+1,e);
    merge(a,t,s,mid,e);
    
    for(int i=s;i<=e;i++)
    {
        cout<<t[i]<<" ";
        //a[i]=t[i];
    }
    cout<<endl;
    
}
int main(){
    int s[10]={4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 
    int t[10];
    for(int i=0;i<10;i++)
    {
        t[i]=s[i];
    }
    TwoGuiBing(s,t,0,9);
    for(int i=0;i<10;i++){
        cout<<t[i]<<" ";
    }
    cout<<endl;
    return 0;
}

 


原文链接:https://www.cnblogs.com/JsonZhangAA/p/11566241.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:类中的函数重载

下一篇:CodeForces-1152C-Neko does Maths