归并排序(二路归并)

归并排序思想

1、确定分界点

找分界点的方式一般都为找中点即 mid = l + r >> 1

2、递归左区间和右区间

注意：快速排序中是先调整好区间再进行递归调用

3、合二为一(难点)

需要一个额外的数组来暂存合并好的数组

归并排序模板

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];
}

逆序对的数量—题目讲解

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

可能有的朋友第一次读完题后觉得很莫名奇妙，这和归并排序有关？什么玩意？

但这确实是一道归并排序的模板题。

在此之前我们首先要搞清楚什么是逆序对，在2,1,4,5,3像<2,1>, <4,3>, <5,3>这样的即为逆序对

在搞清楚什么是逆序对之后我们就需要考虑它的出现方式，假设我们将一个数列划分为左右两个区间，那么逆序对出现的情况无非就三种

1、两个数均在左区间

2、两个数均在右区间

3、一个数在左区间一个数在右区间

欸！看到这里是不是马上想到了如果将一个区间视为一个新的数列，那我们实际只需要考虑第三种情况了！

假如数列的区间划分为为 4 5 6| 1 2 3，那么很明显如果右区间的最大数小于左区间的最小数，那么立马就能用简单的数学运算得出这个数与左区间形成的逆序对数量 ;

所以现在的问题是如何找到每次各区间的最小最大数

~~这多简单？两个for循环不就搞定了？~~ 很显然这样的时间复杂度是o(n^2)

而归并排序不就恰好能实现这一点吗？而且相应的时间复杂度是o(nlogn)

所以其实这道题就只需要在归并排序原基础上添加一行代码

while(i <= mid && j <= r){
    if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    else {
        tmp[k ++ ] = q[j ++ ];
        nums += mid - l + 1;//新添加的一行代码
    }
}