归并排序

跟着小闫老师的思路

看代码
void merge_sort(int q[],int l,int r)
{
if(l>=r) return ; //同样是比较数组是否存在

int mid=l+r>>1;  //归并排序需要一个中间值

merge_sort(q,l,mid);  //分别给中间值两边的数字排序

merge_sort(q,mid+1,r);

int i=l,j=mid+1,tmp[N],k=0;  //设立i,j,以及中间数组tmp
//比较过程

while(i<=mid&&j<=r)
{
    if(q[i]<=q[j])  tmp[k++]=q[i++];
    else  tmp[k++]=q[j++];
}

while(i<=mid)
    tmp[k++]=q[i++];

while(j<=r)
    tmp[k++]=q[j++];

for(i=l,j=0;i<=r;i++,j++)  //因为我们是把比较完的结果赋予给tmp,所以最后需要给q 
    q[i]=tmp[j];

}
详细过程
同样以一个例子证明
3 1 2 4 5
n=5
mid=l+r>>1=(l+r)/2=2
所以我们需要分别给q[2]左右两侧排序
即merge_sort(q,l,mid)
merge_sort(q,mid+1,r)
即3 1 2 4 5
1 2 3 4 5

1 2 3 4 5
i j
这个例子可能举的不是很好
1<4
tmp 序列 1
1 2 3 4 5
i j
2<4
tmp 序列 1 2
1 2 3 4 5
i j
3<4
tmp 序列 1 2 3
i以及走到mid位置所以把j后面的并到tmp
即1 2 3 4 5
最后把tmp的值赋予q