归并排序

• 1 基本思想
• 2 代码

https://www.acwing.com/activity/content/introduction/11/

知识点对应的题目为：https://www.acwing.com/problem/content/789/

1 基本思想

归并排序与快速排序有相似的地方，主要的区别在于，归并排序先对子序列进行排序，然后合并。具体来说，步骤为：

1. 确定分界点x： m i d = ( l + r ) / 2 mid = (l + r) / 2 mid=(l+r)/2， l l l表示左边界， r r r表示右边界
2. 递归排序，分别对两个子序列排序（ l — — m i d   & m i d + 1 — — r ） l ——mid~\& mid+1——r） l——mid &mid+1——r）
3. 归并：将两个子序列合并（关键点）

第3步合并时最关键的一步，主要实现的方法为双指针：

1. 指针初始位置为两个子序列的开头
2. 指针处的值进行比较，较小值进入结果数组，同时对应的指针右移
3. 如果指针都达到末尾，则停止；如果一个序列的指针先到达末端，则直接把另一个序列剩余的数据插入到结果数组的尾端即可

时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)，这是因为双指针每做一次递归需要遍历n个数据；而归并数组不断拆分原数组为原来的一半，执行 log ⁡ n \log n logn次之后就结束：

2 代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int q[N];
int n;
int temp[N];

void mergeSort(int q[], int l, int r){
    if (l >= r) return;
    int mid = (l + r) / 2;
    
    mergeSort(q,l, mid);
    mergeSort(q,mid + 1, r);
    
    int left = l;
    int right = mid + 1;
    int k = 0;
    while (left <= mid && right <= r)
        if (q[left] < q[right]) temp[k++] = q[left++];
        else temp[k++] = q[right++];
    while (right <= r)  temp[k++] = q[right++];
    while (left <= mid)  temp[k++] = q[left++];
    
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d",&q[i]);
    mergeSort(q,0,n-1);
    for (int i = 0; i < n; i++) printf("%d ",q[i]);
    
    
}