归并排序

算法学习的第二天

算法学习之归并排序

归并排序采用分治的思想

它的基本思想是：选择一个分界点，先进行递归排序两边，再将两个数组合二为一。

归并排序模板

void merge_sort(int q[], int l, int r) //定义一个函数merge_sort包含三个参数q[],l,r l为q[]的左边界，r为q[]的右边界
{
    if (l >= r) return; //如果左边界大于等于右边界，跳出函数

    int mid = l + r >> 1; //取整个区间的中点
    merge_sort(q, l, mid); //递归排序左边
    merge_sort(q, mid + 1, r); //递归排序右边
    
//归并 两个有序的序列合并为一个有序的序列
    int k = 0, i = l, j = mid + 1; // i是指向左半边有序序列的起点，j是指向右半边有序序列的起点。
    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 ++ ) q[i] = tmp[j];//将临时序列里的结果存回数组里面
}

归并排序是稳定的算法。

归并排序平均时间复杂度是O（N *lgN）

例题：

P1177 【模板】快速排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 #include <cstdio>
#include <iostream>

using namespace std;

int n; 
const int N = 1e5;
int q[N],tmp[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 = 0, 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 = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}


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