快速排序题解

归并排序的核心思想基于分治理念。

1、算法原理（以升序为例）：

以中间点为界，将数组一分为二，进行递归排序。
并在每次递归排序结束后将两个排序好的子数组归并到原数组中。

2、代码主体框架：

与快排类似，归并排序的主体框架也是一个递归函数，其核心逻辑如下：

void m_soRt(int a[],int L,int R){
    //递归的基准条件
    if(L>=R) Return;

    //以中间点为界，将数组一分为二，进行递归
    int mid = L+R>>1;
    m_soRt(a,L,mid);
    m_soRt(a,mid+1,R);

    //合并排序完毕的两个子数组[L,mid]和[mid+1，R]
}

3、子数组合并的具体步骤：

1）循环比较两个子数组元素，依次将较小值存入临时数组。
2）将其中一个数组中剩余的元素复制到临时数组中。
3）将临时数组的值复制到原数组的[L,R]区间。

//循环比较两个子数组元素，依次将较小值存入临时数组
int k=0,i=L,j=mid+1;
while(i<=mid && j<=R){
    if(a[i]>a[j]) tmp[k++]=a[i++];
    else tmp[k++]=a[j++];
}
//将两个子数组中有剩余的元素，存入到临时数组
while(i<=mid) tmp[k++]=a[i++];
while(j<=R) tmp[k++]=a[j++];

//将临时数组的元素复制到原数组[L,R]区间
for(int i=0,j=L;j<=R;i++,j++) a[j] = tmp[i];

4、完整代码

void m_sort(int a[],int L,int R){
    if(L>=R) return;//递归基准条件

    //以中间点为界分为两个数组递归
    int mid = L+R>>1;
    m_sort(a,L,mid);
m_sort(a,mid+1,R);

    //循环比较两个子数组元素，依次将较小值存入临时数组
    int k=0,i=L,j=mid+1;
    while(i<=mid && j<=R){
        if(a[i]<a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
}

    //将两个子数组中有剩余的元素，存入到临时数组
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=R) tmp[k++]=a[j++];

    //将临时数组的元素复制到原数组[L,R]区间
    for(int i=0,j=L;j<=R;i++,j++) a[j] = tmp[i];
}