Count Inversions逆序對

01為什麼需要它

看到這些關鍵字就想到它：逆序對、i < j 但 a[i] > a[j]、兩份排名有多不一致、Kendall tau、最少相鄰交換次數、右邊有幾個比我小、排列的奇偶、在合併排序時順便數。

02核心概念

逆序對是一對位置 i < j 而 a[i] > a[j]，也就是「前面的比後面的大」。n 個元素最多有 n(n−1)/2 對（完全反序），最少 0 對（已排序），數字大小就代表序列離有序有多遠：它等於泡沫排序的交換次數、插入排序的挪動次數，也是把序列排好所需的最少相鄰交換次數。兩層迴圈兩兩比對是 O(n²)，n = 10⁵ 時要 50 億次。

分治的觀察：把陣列切成左右兩半，每一對逆序對只有三種：兩個都在左半、兩個都在右半、一個在左一個在右（跨半）。前兩種遞迴去數。跨半的那種只看「左半的某個值大於右半的某個值」，和兩半內部怎麼排列無關，所以可以先把兩半各自排好再數，這正是合併排序的合併步驟。合併時左指標 i、右指標 j：若 a[i] ≤ a[j] 取左邊；否則取右邊的 a[j]，此時左半還沒取走的 a[i..mid−1] 全都 ≥ a[i] > a[j]，而且原本都排在 a[j] 前面，一次加上 mid − i 對。每一個跨半逆序對 (左 x, 右 y) 恰好在 y 被取出的那一刻算一次：比 y 大的左半元素那時都還沒被取走，不比 y 大的都已經取走了。

複雜度就是合併排序的 T(n) = 2T(n/2) + O(n)，O(n log n) 時間、O(n) 暫存空間，另加 O(log n) 的遞迴深度。答案本身可能到 n(n−1)/2：n 超過 65,536 就會超出 32 位元整數，C++ 一定要用 long long。另一種同樣 O(n log n) 的寫法是用 Fenwick Tree：值先壓縮成名次，由左往右掃，每個元素查「前面已經出現、而且比我大」的個數再把自己加進去；它不必重排陣列，適合一邊讀資料一邊數。

常見的坑：相等的值不算逆序，合併時必須寫 a[i] ≤ a[j] 先取左邊，寫成 < 會把相等的也算進去；計數的位置要和取出的方向一致，「取右邊時加 mid − i」和「取左邊時加 j − mid」是兩種等價寫法，混用就會重複或漏算；直接在輸入陣列上排序會把呼叫端的資料打亂。變形題要注意條件是否和合併的順序一致：Reverse Pairs 的條件是 a[i] > 2·a[j]，和「誰先出來」的順序不同，要在合併之前另外用雙指標數；Count of Smaller Numbers After Self 要的是每個元素各自的數量，就得排序索引而不是值。這一課和 Merge Sort 是同一段程式碼，差別只是多了一行計數；Insertion Sort 那篇示範的挪動次數 13，數的也是逆序對。

03演算法步驟

1. 1定義 sort(lo, hi)：把 [lo, hi) 排好，並回傳這個區間內的逆序對數。長度 ≤ 1 時回傳 0。
2. 2切半遞迴：cnt = sort(lo, mid) + sort(mid, hi)，這是兩半內部的逆序對。
3. 3合併：比較 a[i] 和 a[j]。a[i] ≤ a[j] 就取左邊；否則取右邊，並 cnt += mid − i。
4. 4把合併結果寫回 [lo, hi)，回傳 cnt。最外層的回傳值就是答案，記得用 64 位元整數。
5. 5要每個元素各自的數量，或條件不是單純的大於（例如 a[i] > 2·a[j]），就改成排序索引、或在合併前另外用雙指標數。

04互動示範

評審 B 給八部作品的名次 [3, 1, 4, 7, 2, 8, 5, 6]，已經依評審 A 的名次排好，所以逆序對就是兩位評審意見相反的作品對數。上方是整個陣列，黃色是正在合併的區段；下方列出左半、右半與合併結果，藍色是下一次要比較的兩個元素，灰色是已經取走的。每當右邊的元素先出來（合併結果裡的綠色），左邊還沒取走的元素會全部變成黃色，一次算進逆序對。最後共 8 對，和暴力兩兩比對一樣，佔全部 28 對的 29%。

05程式碼

Python 放合併排序版、對照用的暴力版，以及把兩份排名轉成逆序對來算 Kendall tau 距離的應用。C++ 放合併排序版與 Fenwick Tree 版，並用完全反序的 10 萬個數示範答案為什麼一定要 long long。

# 合併排序順便數逆序對：右邊的元素先出來時，左邊還沒出來的都比它大
def count_inversions(a):
    a = a[:]                                 # 在副本上排序，不改動輸入
    buf = [0] * len(a)

    def sort(lo, hi):                        # 排好 a[lo:hi]，回傳其中的逆序對數
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = sort(lo, mid) + sort(mid, hi)  # 左半內部 + 右半內部
        i, j = lo, mid
        for k in range(lo, hi):
            if j == hi or (i < mid and a[i] <= a[j]):
                buf[k] = a[i]                # 相等不算逆序，先取左邊
                i += 1
            else:
                buf[k] = a[j]
                j += 1
                cnt += mid - i               # 跨兩半：左邊還剩 mid - i 個都比 a[j] 大
        a[lo:hi] = buf[lo:hi]
        return cnt

    return sort(0, len(a))


def count_inversions_brute(a):               # 對照用的 O(n²)
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])


# 兩份排名的 Kendall tau 距離：有幾對項目，兩份排名的先後相反
def kendall_tau_distance(rank_a, rank_b):
    pos = {item: i for i, item in enumerate(rank_b)}
    return count_inversions([pos[item] for item in rank_a])   # 依 A 的順序寫下 B 的名次


if __name__ == "__main__":
    judge_b = [3, 1, 4, 7, 2, 8, 5, 6]                       # 和互動示範同一組
    print(count_inversions(judge_b), count_inversions_brute(judge_b))   # 8 8
    print(kendall_tau_distance(["A", "B", "C", "D"], ["B", "A", "D", "C"]))   # 2
    print(count_inversions(list(range(5000, 0, -1))))       # 12497500 = 5000 × 4999 / 2

06練習題

• LeetCode 775Global and Local Inversions（全部逆序對都必須是相鄰的）Medium
• LeetCode 1850Minimum Adjacent Swaps to Reach the Kth Smallest Number（相鄰交換次數就是逆序對數）Medium
• LeetCode 315Count of Smaller Numbers After Self（每個元素各自數，排序索引）Hard
• LeetCode 493Reverse Pairs（條件是 a[i] > 2·a[j]，合併前先用雙指標數）Hard
• LeetCode 327Count of Range Sum（對前綴和做同樣的合併計數）Hard