算法分析

首先，归并排序和选择排序是有点相似的，两者都是基于分治的思想，

• 归并排序的分界点是下标，取的是 mid = l+r>>1 ，难点是在于合并区间
• 快速排序的分界点是 q[l]-q[r] 数组中随意一个值，而不是下标，其难点在于分界点的选择和区间调整

归并排序主要分为三个部分：

• 分界点的选择 mid = l+r>>1 ，分为 [l, mid]，[mid+1, r]
• 递归排序两个区间
• 区间调整，即区间数据按照大小插入临时数组
• 区间合并，即临时数组中的数据赋值到原数组的 q[l]-q[r] 位置

模板

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 k = 1, i = l, j = mid + 1;
    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 = 1; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

完整代码

#include<iostream>
using namespace std;
const int N = 1e6+5;
int q[N], tmp[N];
int n;

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 k = 1, i = l, j = mid+1;
    while(i<=mid && j<=r)
    {
        if(q[i]<q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }

    // 如果左或右没有遍历完，再次读入到 tmp 中
    while(i<=mid) tmp[k++] = q[i++];
    while(j<=r) tmp[k++] = q[j++];

    for(i = l, j=1; i<=r; i++,j++) q[i] = tmp[j]; 
    // 临时数组 tmp 中的数是 q[l]-q[r]，所以这里 i 是l-r
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>q[i];
    merge_sort(q, 1, n);
    for(int i=1;i<=n;i++) cout<<q[i]<<" ";
    return 0;
}