深入理解归并排序——从归并排序到CDQ分治、归并树

EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒

本文链接地址: 深入理解归并排序——从归并排序到CDQ分治、归并树


归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  

可以发现合并有序数列的效率是非常高的,有O(N)此时N = len(a)+len(b)。

加上一点分治的想法:
mergesort1

从而对于一个数组,我们可以如下的方式二分分治:
mergesort2

如上图所示,最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次合并的时间为\(O(N)\)。而得到有序的、长度为2的区间后,我们根据它们有序的特点继续合并,那么又在\(O(N)\)的时间内得到了有序的、长度为4的区间。
显然当我们得到最后的排序结果时,一共用了\(O(NlogN)\)的时间,\(O(NlogN)\)的空间。

写成伪代码的形式:
mergesort3

实现代码

下面是归并排序程序的调用程序,但前面的merge函数需要稍加修改:

  • 对a的两个区间进行归并(起点不同)
  • temp的结果需要写回到a中,数组a和temp作为全局变量传入
void mergesort(int l, int r) {  
    if (l < r) {  
        int mid = (first + last) / 2;  
        mergesort(first, mid);    //左边有序  
        mergesort(mid + 1, last); //右边有序  
        merge(first, mid, last); //再将二个有序数列合并  
    }  
}  

void merge(int l,int m,int r)   {
    int i = l;  
    int j = m + 1;  
    int k = l;  
    while(i <= m && j <= r) {  
        if(a[i] > a[j]) tmp[k++] = a[j++];
        else tmp[k++] = a[i++];  
    }  
    while(i <= m) tmp[k++] = a[i++];  
    while(j <= r) tmp[k++] = a[j++];  
    for(int i=l;i<=r;i++)  
        a[i] = tmp[i];  
}  

时间复杂度分析

一共\(logN\)层,每一层都花费\(O(N)\)的时间,故总的时间复杂度为\(O(NlogN)\)

正确性证明

简单地使用loop-invariant technique [R. W. Floyd, 1967](数学归纳法)即可证明。

归并排序求逆序数

通常我们都是通过树状数组计算逆序数的数量。而现在我们通过归并排序的分治也可以解决这个问题。

从逆序数的定义我们可以知道,对于\(a_i\)来说,不妨记当前index为pos2, 排序好的位置是pos1,这里保证pos1<pos2(这样所有统计逆序数的过程都是从后向前交换的过程,而不是向前和向后混合的复杂情况)。那它的逆序数个数就是从pos2逐个交换到pos1过程中,遇到的大于\(a_i\)的数的个数。

考虑归并排序的特点,现在因为归并排序已经将左右两侧的元素都排序好了,所以两侧内部的逆序数为0,只需要考虑异侧的情况。而异侧的逆序数对数如何统计呢?我们可以简单地在merge时统计——所有在右侧的元素\(a_i\),当其被插入到pos1位置时,它所遇到的所有数都是大于\(a_i\)的,因为这个数列merge后是有序的。故根据逆序数的定义,在这个子区间中#逆序数(\(a_i\))=pos2-pos1。

实现代码

int a[MAXN];
int tmp[MAXN];

int mergesort(int l, int r) {
    if (r < l) return 0;
    if (r == l) return 0;
    int mid = l + ((r-l)>>1);

    int n_l = mergesort(l, mid);
    int n_r = mergesort(mid+1, r);

    int pl = l, pr = mid+1;
    int count = 0;
    for (int i = l; i <= r; i++) {
        // 每当右边元素插入到tmp数组时,就要计算逆序数
        if (pl > mid) tmp[i] = a[pr++];
        else if (pr > r) tmp[i] = a[pl++];
        else if (a[pl] <= a[pr]) tmp[i] = a[pl++];
        else {
            count += pr - i;
            tmp[i] = a[pr++];
        }
    }
    // 将排序结果放到a里
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    return count + n_l + n_r;
}

归并排序(求逆序数)和CDQ分治

CDQ分治的基本思想十分简单:普通分治在合并两个子问题的过程中,[L,M]内的问题不会对[M+1,R]内的问题产生影响,比如线段树的求和、求极值。而CDQ分治合并两个子问题,同时考虑到[L,M]内的修改对[M+1,R]内的查询产生的影响。归并排序则是CDQ分治的基础。

mergesort4

如果我们考虑将数列二分,那么就需要考虑如上右图的两种情况——同侧和异侧:

  • 当两个数在同侧时,在若干次分治之前,它们一定属于异侧
  • 两个元素同侧时逆序对数已经在它们还是异侧时被计算过了,故不需要考虑同侧的元素之间的逆序对数,只需要处理两个数在异侧的情况
  • 只需要处理异侧的情况,那么情况就变得简单:
    在合并左右两侧时,每次插入右侧的元素时,不妨计算左侧还未插入的元素的个数,它们都大于ai,其数量就是ai的逆序数。所以有 逆序数 = #左侧元素 – 插入后的pos(从0开始)

所以有结论:每次插入时,逆序数 = num – pos,num为左侧元素个数, pos为插入后的位置,从0开始数。

我们可以发现归并排序求逆序数的过程可以认为是符合CDQ分治思想的,我们在合并过程中计算左边区间对右边区间造成的影响——这就是CDQ分治,通过归并排序维护有序性,再通过左区间对右区间求解。

至于更多、更复杂的CDQ分治的问题与应用,读者可以自行阅读相关资料。

实现代码

void merger(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    merger(l, mid);
    merger(mid + 1, r);
    int pl = l, pr = mid + 1;
    for(int i=l; i<=r; i++) {
        if( (pl <= mid && a[pl] <= a[pr]) || pr > r ){
            b[i] = a[pl++];
        } else {
            b[i] = a[pr ++];
            ans += (mid - pl + 1);
        }
    }
    for(int i=l; i<=r; i++) a[i] = b[i];

归并树

回到这个熟悉的图:
mergesort5

从上图可以发现,归并排序的过程构成了一颗类似线段树的树。那么它支不支持区间查询呢?

区间查询>x的数

假如我们查询的是区间[a, b]中值 > x的个数?

显然我们对相关的不重叠区间分别进行一次二分查找就可以。一次二分查找需要时间\(O(logN)\),而区间[a, b]至多被分为\(logN\)个不重叠的小区间,这样在\(O(log^2N)\)我们就得到了答案。

1. 建树

void init(int k, int l, int r) {    我们通过vector<int> dat[4*MAXN]的形式来储存数列。相当于线段树的每个节点不再储存一个值,而是一个数列。
    if (r-l == 1) dat[k].push_back(A[l]);
    else {  而merge函数是std提供的、将两个有序数列合并的库函数。
        init(ls, l, mid);
        init(rs, mid, r);
        dat[k].resize(r-l);
        merge(dat[ls].begin(), dat[ls].end(),
                     dat[rs].begin(), dat[rs].end(), dat[k].begin());
    }
}

2. 查询

int query(int a, int b, int x, int k, int l, int r) {//查询区间 [a,b)
    if (r <= a || b <= l) return 0;//区间不相交
    if (a <= l && r <= b) return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
    else {
        int v1 = query(a, b, x, ls, l, mid);
        int v2 = query(a, b, x, rs, mid, r);
        return v1+v2;
    }
}
int qt(int a, int b, int x) {//封装query()函数
    return query(a, b, x, 0, 0, N);
}

区间查询第k大

换一个不那么显然的问题,查询区间第k大,题目表述如下:
mergesort6

Note:这是一个经典的题目,有很多解法可以使用。而且这个题目是求静态的数列,升级版还有动态的数列。其中最常见的解法是可持久化线段树(主席)和平方分割。(看不懂就划掉

看起来对于归并树来说,第k大数的查询涉及区间的合并问题,很难做。我们含泪在外层嵌套一个二分,先将问题转化为判定\(a_i\)是否是第k大。这里二分的意思就是说:首先计算中位数(即排序好后的数列b的中间那个数b[n/2])在区间[i, j]是第几大,如果大于k,则取[mid+1, n]的中位数继续二分。(如果还没有看懂的话,那应该是没有二分的基础,建议先去搜索并阅读“二分答案”相关blog。)

而现在的问题不就是变成计算小于中位数的元素个数了吗?!正好是上一个问题。所以要解决区间第K大的问题,只需要在上一个问题的基础上加一个二分就好了。限于篇幅,这里就不给出代码了。

时间复杂度

整体时间复杂度为\(O(nlogn+mlog^3n)\)。
建树的时间复杂度为\(O(nlogn)\),然后m个查询,二分\(O(logn)\)加上查找区间的\(O(logn)\),再加上在区间内部的二分\(O(logn)\),这样在\(O(mlog^3n)\)我们就得到了答案。

归并树的应用

  • 查询区间第K大
  • 区域树(常见的方法是通过线段树套线段树完成区间查询)
    可以把之前“查询[a, b]中<v的点的个数”看成“查询a≤x≤b, y≤v的点的个数”

相关例题

  • POJ 1804
    归并排序模板题
  • POJ 2104
    区间第k大

参考文献

I. 白话经典算法系列之五 归并排序的实现
II. 归并排序求逆序对
III. 《挑战程序设计竞赛 第二版》
IV. 浅谈二分答案

发表评论

电子邮件地址不会被公开。 必填项已用*标注