歸並排序計算逆序對數量：算法原理與 C 語言實現詳解

問題定義

給定長度 N 的數組，求逆序對數量：i < j 且 a[i] > a[j] 的對數。暴力 O(N²) 超時，需 O(N log N) 算法。

歸並排序思想

歸並過程中，將數組分為左右兩有序子數組。合併時，若左邊當前元素 L[i] > 右邊當前元素 R[j]，則 L[i] 及其后所有元素均大於 R[j]（因左子數組有序），形成 mid - i + 1 個逆序對。累加即得總數。

算法步驟

1. 遞歸分解至單元素。
2. 合併兩有序子數組至臨時數組，同時計算逆序對。
3. 拷貝回原數組，保證上層合併有序性。
4. 全局變量 count 累加（遞歸各層共享）。

完整 C 代碼

#include <stdio.h>

#define MAXN 20000
int a[MAXN], tmp[MAXN];
long long cnt = 0; // 逆序對數可能超過 int

void merge(int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            cnt += mid - i + 1; // 關鍵：左邊剩餘元素全大於 a[j]
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (i = lo; i <= hi; i++) a[i] = tmp[i];
}

void mergeSort(int lo, int hi) {
    if (lo < hi) {
        int mid = (lo + hi) >> 1;
        mergeSort(lo, mid);
        mergeSort(mid + 1, hi);
        merge(lo, mid, hi);
    }
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    mergeSort(0, n - 1);
    printf("%lld\n", cnt);
    return 0;
}

關鍵點解析

• 全局 cnt：避免遞歸返回值層層傳遞，簡化代碼。
• 臨時數組 tmp：歸並需額外空間，全局分配避免重複 malloc。
• 條件 a[i] <= a[j]：等號保證穩定性，不影響逆序對計數（嚴格大於才計數）。
• 長整型 long long：N=20000 時最大逆序對 ~2億，超 int 範圍。

複雜度

• 時間：O(N log N)
• 空間：O(N)（臨時數組）

測試示例

輸入:
7
3 1 4 2 5 6 0
輸出:
9
// 逆序對: (3,1)(3,2)(3,0)(1,0)(4,2)(4,0)(2,0)(5,0)(6,0)

總結

歸並排序天然適合計算逆序對，核心在於合併階段利用有序性批量計數。掌握「左邊剩餘元素個數」這一洞察，即可靈活應用於各類「有序區間配對計數」問題。