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; }