深入了解歸并排序——從歸并排序到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)。

這裡是我的個人網站：

https://endlesslethe.com/mergesort-and-mergetree-tutorial.html

有更多總結分享，排版也可能會更好看一點=v=

加上一點分治的想法：

進而對于一個數組，我們可以如下的方式二分分治：

如上圖所示，最下面是我們需要排序的數組。我們把它分成N個長度為1的區間。那麼相鄰兩個區間進行一次合并的時間為\(O(N)\)。而得到有序的、長度為2的區間後，我們根據它們有序的特點繼續合并，那麼又在\(O(N)\)的時間内得到了有序的、長度為4的區間。

顯然當我們得到最後的排序結果時，一共用了\(O(NlogN)\)的時間，\(O(NlogN)\)的空間。

寫成僞代碼的形式：

實作代碼

下面是歸并排序程式的調用程式，但前面的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分治的基礎。

[外鍊圖檔轉存失敗(img-UKxhfRtL-1568995946119)(https://endlesslethe.com/wordpress/wp-content/uploads/2019/09/mergesort4.jpg)]

如果我們考慮将數列二分，那麼就需要考慮如上右圖的兩種情況——同側和異側：

• 當兩個數在同側時，在若幹次分治之前，它們一定屬于異側
• 兩個元素同側時逆序對數已經在它們還是異側時被計算過了，故不需要考慮同側的元素之間的逆序對數，隻需要處理兩個數在異側的情況

• 隻需要處理異側的情況，那麼情況就變得簡單：

  在合并左右兩側時，每次插入右側的元素時，不妨計算左側還未插入的元素的個數，它們都大于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];
           

歸并樹

回到這個熟悉的圖：

[外鍊圖檔轉存失敗(img-yK4rkRj4-1568995946120)(https://endlesslethe.com/wordpress/wp-content/uploads/2019/09/mergesort4.jpg)]

從上圖可以發現，歸并排序的過程構成了一顆類似線段樹的樹。那麼它支不支援區間查詢呢？

區間查詢>x的數

假如我們查詢的是區間[a, b]中值 > x的個數？

顯然我們對相關的不重疊區間分别進行一次二分查找就可以。一次二分查找需要時間\(O(logN)\)，而區間[a, b]至多被分為\(logN\)個不重疊的小區間，這樣在\(O(log^2N)\)我們就得到了答案。

１. 建樹

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());
    }
}
           

２. 查詢

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大，題目表述如下：

Note：這是一個經典的題目，有很多解法可以使用。而且這個題目是求靜态的數列，更新版還有動态的數列。其中最常見的解法是可持久化線段樹（主席）和平方分割。（看不懂就劃掉

看起來對于歸并樹來說，第k大數的查詢涉及區間的合并問題，很難做。我們含淚在外層嵌套一個二分，先将問題轉化為判定\(a_i\)是否是第k大。這裡二分的意思就是說：首先計算中位數（即排序好後的數列b的中間那個數b[n/2]）在區間[i, j]是第幾大，如果大于k，則取[mid+1, n]的中位數繼續二分。（如果還沒有看懂的話，那應該是沒有二分的基礎，建議先閱讀參考文獻IV"淺談二分答案"。）

而現在的問題不就是變成計算小于中位數的元素個數了嗎？！正好是上一個問題。是以要解決區間第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. 淺談二分答案