跳转至

歸併排序

定義

歸併排序（merge sort）是高效的基於比較的穩定排序算法。

性質

歸併排序基於分治思想將數組分段排序後合併，時間複雜度在最優、最壞與平均情況下均為 \(\Theta (n \log n)\)，空間複雜度為 \(\Theta (n)\)。

歸併排序可以只使用 \(\Theta (1)\) 的輔助空間，但為便捷通常使用與原數組等長的輔助數組。

過程

合併

歸併排序最核心的部分是合併（merge）過程：將兩個有序的數組 a[i] 和 b[j] 合併為一個有序數組 c[k]。

從左往右枚舉 a[i] 和 b[j]，找出最小的值並放入數組 c[k]；重複上述過程直到 a[i] 和 b[j] 有一個為空時，將另一個數組剩下的元素放入 c[k]。

為保證排序的穩定性，前段首元素小於或等於後段首元素時（a[i] <= b[j]）而非小於時（a[i] < b[j]）就要作為最小值放入 c[k]。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) {
  size_t i = 0, j = 0, k = 0;
  while (i < aLen && j < bLen) {
    if (b[j] < a[i]) {  // <!> 先判斷 b[j] < a[i]，保證穩定性
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // 此時一個數組已空，另一個數組非空，將非空的數組併入 c 中
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void merge(const int *aBegin, const int *aEnd, const int *bBegin,
           const int *bEnd, int *c) {
  while (aBegin != aEnd && bBegin != bEnd) {
    if (*bBegin < *aBegin) {
      *c = *bBegin;
      ++bBegin;
    } else {
      *c = *aBegin;
      ++aBegin;
    }
    ++c;
  }
  for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin;
  for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin;
}

也可使用 <algorithm> 庫的 merge 函數，用法與上述指針式寫法的相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def merge(a, b):
    i, j = 0, 0
    c = []
    while(i < len(a) and j < len(b)):
        # <!> 先判斷 b[j] < a[i]，保證穩定性
        if(b[j] < a[i]):
            c.append(b[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
    # 此時一個數組已空，另一個數組非空，將非空的數組併入 c 中
    c.extend(a[i:])
    c.extend(b[j:])
    return c

分治法實現歸併排序

  1. 當數組長度為 \(1\) 時，該數組就已經是有序的，不用再分解。

  2. 當數組長度大於 \(1\) 時，該數組很可能不是有序的。此時將該數組分為兩段，再分別檢查兩個數組是否有序（用第 1 條）。如果有序，則將它們合併為一個有序數組；否則對不有序的數組重複第 2 條，再合併。

用數學歸納法可以證明該流程可以將一個數組轉變為有序數組。

為保證排序的複雜度，通常將數組分為儘量等長的兩段（\(mid = \left\lfloor \dfrac{l + r}{2} \right\rfloor\)）。

實現

注意下面的代碼所表示的區間分別是 \([l, r)\)，\([l, mid)\)，\([mid, r)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void merge_sort(int *a, int l, int r) {
  if (r - l <= 1) return;
  // 分解
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // 合併
  int tmp[1024] = {};  // 請結合實際情況設置 tmp 數組的長度（與 a 相同），或使用
                       // vector；先將合併的結果放在 tmp 裏，再返回到數組 a
  merge(a + l, a + mid, a + mid, a + r, tmp + l);  // pointer-style merge
  for (int i = l; i < r; ++i) a[i] = tmp[i];
}

1
2
3
4
5
6
7
8
9
def merge_sort(a, ll, rr):
    if rr - ll <= 1:
        return
    # 分解
    mid = (rr + ll) // 2
    merge_sort(a, ll, mid)
    merge_sort(a, mid, rr)
    # 合併
    a[ll:rr] = merge(a[ll:mid], a[mid:rr])

倍增法實現歸併排序

已知當數組長度為 \(1\) 時，該數組就已經是有序的。

將數組全部切成長度為 \(1\) 的段。

從左往右依次合併兩個長度為 \(1\) 的有序段，得到一系列長度 \(\le 2\) 的有序段；

從左往右依次合併兩個長度 \(\le 2\) 的有序段，得到一系列長度 \(\le 4\) 的有序段；

從左往右依次合併兩個長度 \(\le 4\) 的有序段，得到一系列長度 \(\le 8\) 的有序段；

……

重複上述過程直至數組只剩一個有序段，該段就是排好序的原數組。

為什麼是 \(\le n\) 而不是 \(= n\)

數組的長度很可能不是 \(2^x\)，此時在最後就可能出現長度不完整的段，可能出現最後一個段是獨立的情況。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void merge_sort(int *a, size_t n) {
  int tmp[1024] = {};  // 請結合實際情況設置 tmp 數組的長度（與 a 相同），或使用
                       // vector；先將合併的結果放在 tmp 裏，再返回到數組 a
  for (size_t seg = 1; seg < n; seg <<= 1) {
    for (size_t left1 = 0; left1 < n - seg;
         left1 += seg + seg) {  // n - seg: 如果最後只有一個段就不用合併
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> 注意最後一個段的邊界
      merge(a + left1, a + right1, a + left2, a + right2,
            tmp + left1);  // pointer-style merge
      for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
    }
  }
}

1
2
3
4
5
6
7
8
9
def merge_sort(a):
    seg = 1
    while seg < len(a):
        for l1 in range(0, len(a) - seg, seg + seg):
            r1 = l1 + seg
            l2 = r1
            r2 = l2 + seg
            a[l1:r2] = merge(a[l1:r1], a[l2:r2])
    seg <<= 1

逆序對

逆序對是 \(i < j\) 且 \(a_i > a_j\) 的有序數對 \((i, j)\)。

排序後的數組無逆序對，歸併排序的合併操作中，每次後段首元素被作為當前最小值取出時，前段剩餘元素個數之和即是合併操作減少的逆序對數量；故歸併排序計算逆序對數量的額外時間複雜度為 \(\Theta (n \log n)\)，對於 C/C++ 代碼將 merge 過程的 if(b[j] < a[i]) 部分加上 cnt += aLen - i 或 cnt += aEnd - aBegin 即可，對於 Python 代碼將 merge 過程的 if(b[j] < a[i]): 部分加上 cnt += len(a) - i 即可。

此外，逆序對計數即是將元素依次加入數組時統計當前大於其的元素數量，將數組離散化後即是區間求和問題，使用樹狀數組或線段樹解決的時間複雜度為 \(O(n \log n)\) 且空間複雜度為 \(\Theta (n)\)。

外部鏈接

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用