归并排序学有所得

emmmmmm.......
写了好久好久终于写出来了归并排序,在写出来之前,对二分的理解只有理论上的,只有当把归并排序写出来时才能稍微理解到一些二分的应用,虽然归并排序的速度并没有快排来的快但是却能有效的帮助我了解二分。
//
归并排序的原理简单来说就是把一个无序的数组从中间砍开,分成两半,再把这两半延中间砍开,再分成两半,单分到只有一个元素时,那么这个数组就自然有序了,接着再按着顺序将其两两,连接在一起,知道恢复原来的长度。其实在刚开始我傻傻的认为要开动态数组?其实不然,只要巧妙的运用递归思想,就不用那么麻烦了;
接下来我们看代码::

#include<iostream>
using namespace std;
#define N 10000006
int a[N];
int b[N];
void gui(int l,int mid,int r){

    int p1=l,p2=mid+1;
    for(int i=l;i<=r;i++){
    if((a[p1]<=a[p2])||(p2>r)&&(p1<=mid)){
        b[i]=a[p1];
        p1++;
    }else{
        b[i]=a[p2];
        p2++;
    }
    }
for(int i=l;i<=r;i++){
    a[i]=b[i];
}
}
void erfen(int l,int r){//递归进行二分,直到单个元素,再回到原长。
    int mid=(l+r)>>1;
    if(l<r){
        erfen(l,mid);
        erfen(mid+1,r);
    }
    gui(l,mid,r);
}

int main(){
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    erfen(1,m);
for(int i=1;i<=m;i++){
    cout<<a[i]<<" ";
}
    return 0;
}
全部评论

相关推荐

程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
qq乃乃好喝到咩噗茶:院校后面加上211标签,放大加粗,招呼语也写上211
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务