void merge_sort(int q[],int l,int r)
{
if(l>=r) return ;//分治终止条件
int mid=(r+l)/2;
int i=l;//左指针
int j=mid+1;//右指针
int k=0;//k为中间数组temp的计数器,不能定义为全局变量
merge_sort(q,l,mid);//左排序。通过递归把数组分成一个个数字,再对一个个数字进行归并排序。
merge_sort(q,mid+1,r);
while(i<=mid&&j<=r)//归并过程
{
if(q[i]<=q[j]) temp[k]=q[i];//对数字进行排序,把它们按照顺序添加入中间数组
else temp[k]=q[j];
}
while(i<=mid) temp[k]=q[i];//扫尾。因为while(i<=mid&&j<=r),只要有一个指针达到目标,就会跳出循环,但是另一个指针此时不一定遍历完它要遍历的目标。
while(j<=r) temp[k]=q[j];
for(i=l,j=0;i<=r;i,j)
{
q[i]=temp[j];
}
}