【日志】归并排序

归并排序

步骤代码应用

求逆序数

归并排序使用了“分而治之”的思想， 把大的区间分解为一个个小的区间，小的区间再分解为更小的区间，直到这个区间不再可分，那么可以保证这个最小区间一定是有序的，接着将小区间归并为大区间，从而完成排序。

分割区间
运用分治的思想，将原本大区间分割为小区间，直到区间不再可分，此时可以保证这样的区间一定是有序的区间。归并区间
对两个子区间合并为一个大区间(合并的结果位于转移数组内)，基于上面的分割结果，得到的两个区间一定是有序的结果，合并区间的时候也是按有序归并。转移区间
将归并好的区间(此时在转移数组里)重新转移至原区间内。

下面代码给的是以 [ l l ,   r r ) [ll, ,rr) [ll,rr)这样一个左闭右开的区间进行排序的归并排序。

//递归版归并排序
//arr是待排序的数组，t是转移数组
void mergeSort(const int ll, const int rr){
    //判断该区间是否可再分
    if (rr - ll <= 1) return;
    //分割区间
    int mid = ll + ((rr - ll) >> 1);
    mergeSort(ll, mid);  //左区间
    mergeSort(mid, rr);  //右区间
    //合并
    int tpos = ll, lpos = ll, rpos = mid;
    //开始从两个子区间内进行合并
    //左区间[ll, mid)，右区间[mid, rr)
    while (lpos < mid && rpos < rr){
        //这里是从两个区间挑小的
        if (arr[lpos] > arr[rpos]){
            t[tpos ++] = arr[rpos ++];
        }else{
            t[tpos ++] = arr[lpos ++];
        }
    }
    //对两个区间整理完后如果还有碎片，再清理一下
    while (lpos < mid) t[tpos ++] = arr[lpos ++];
    while (rpos < rr) t[tpos ++] = arr[rpos ++];
    //最后将t数组里面合并完成的区间把原数组的区间覆盖
    for (int i = ll; i < rr; ++ i) arr[i] = t[i];
}

由于每次分割时是将原区间一分为二，直到区间不可再分，因此每一次执行归并排序的时间复杂度都为 O ( n log ⁡ 2 n ) O(nlog_{2}{n}) O(nlog2​n)。同时，由于需要一个辅助数组暂时存储合并后的区间，其空间复杂度为 O ( n ) O(n) O(n)。

有这样一个很经典的求逆序数的例子。

int cnt = 0;
for (int i = 0; i < n - 1; ++ i){
    for (int j = i + 1; j < n; ++ j){
        if (arr[i] > arr[j]) cnt ++;
    }
}

这样的确可以求出逆序数，但是需要 O ( n 2 ) O(n^2) O(n2)的时间复杂度(事实上这个就是个冒泡排序)。在归并排序的归并操作中，正好有一步进行了比较，就可以正好利用这个比较从而求出逆序数。

因为左边序列一定比右边小，所以在左边找到一个数字比右边指着的位置的数字大的话左边序列的后面的数字一定与右边指向的数字产生逆序对，结果就是右边序列开头减去左边出现逆序对的数字，即从这个位置开始数直到左序列结束数字的个数。

long long cnt = 0;  //求逆序数
void mergesort(int ll, int rr){
    if (rr - ll <= 1) return;
    int mid = ll + ((rr - ll) >> 1);
    mergesort(ll, mid); mergesort(mid, rr);
    int tpos = ll, apos = ll, bpos = mid;
    while (apos < mid && bpos < rr){
        if (arr[apos] > arr[bpos]){
            t[tpos ++] = arr[bpos ++];
            //就加上这一步
            cnt += mid - apos;
        }else{
            t[tpos ++] = arr[apos ++];
        }
    }
    while (apos < mid) t[tpos ++] = arr[apos ++];
    while (bpos < rr) t[tpos ++] = arr[bpos ++];
    for (int i = ll; i < rr; ++ i) arr[i] = t[i];
}