DSA Interview Prep · 课时

使用修改后的归并排序统计逆序对

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

Q: 「使用修改后的归并排序统计逆序对」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

通过在合并阶段统计跨分割点的逆序对，计算数组中的逆序对数量——即满足 a[i] > a[j] 且 i < j 的数对。

使用修改后的归并排序统计逆序对 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

什么是逆序对

数组中的逆序对是指一对索引 (i, j)，满足 i < j 但 a[i] > a[j]——较大的元素出现在较小元素之前。例如，在 [3, 1, 2] 中，逆序对为 (3,1) 和 (3,2)，因此共有 2 个逆序对。已排序数组有 0 个逆序对。包含 n 个元素的逆序排列数组有 n(n-1)/2 个逆序对。统计逆序对可以衡量数组距离有序状态有多远。

arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions))  # 2

# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}')  # 10 for [5,4,3,2,1]

朴素的 O(n²) 方法

暴力方法会检查所有满足 i < j 的索引对 (i, j)，并统计其中 a[i] > a[j] 的数量。这需要 O(n²) 时间和 O(1) 空间。当 n = 10⁵ 时，这意味着 5 × 10⁹ 次比较，速度太慢。使用修改版归并排序的分治法可以在O(n log n) 时间内解决问题。关键洞察是：在归并排序的 merge 步骤中，我们可以高效地统计跨分割逆序对。

def count_inversions_brute(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions_brute([3, 1, 2]))   # 2
print(count_inversions_brute([5, 4, 3, 2, 1]))  # 10
print(count_inversions_brute([1, 2, 3, 4, 5]))  # 0
print(count_inversions_brute([2, 4, 1, 3, 5]))  # 3

归并排序的洞察

在合并两个有序部分 L 和 R 时，如果我们选择 R[j] 而不是 L[i]（因为 R[j] < L[i]），那么 the L 中从索引 i 开始的所有剩余元素也都大于 R[j]。这是因为 L 已排序。因此，每次从右半部分取出元素时，我们都可以统计 len(L) - i 个跨半部分逆序对。这种统计不需要额外工作——它在正常的 merge 过程中完成。

# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')

修改版归并排序的实现

修改归并排序，使其同时返回有序数组和逆序对计数。总逆序对数 = 左半部分逆序对数 + 右半部分逆序对数 + merge 过程中发现的跨半部分逆序对。基本情况返回（单个元素，0 个逆序对）。合并函数在合并时统计逆序对。总时间复杂度：O(n log n)。

def count_inversions(arr):
    def merge_sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left,  left_count  = merge_sort_count(arr[:mid])
        right, right_count = merge_sort_count(arr[mid:])
        merged, cross_count = merge_count(left, right)
        return merged, left_count + right_count + cross_count
    
    def merge_count(left, right):
        result, count = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1
                count += len(left) - i  # all remaining in left are inversions
        result += left[i:] + right[j:]
        return result, count
    
    _, total = merge_sort_count(arr)
    return total

print(count_inversions([3, 1, 2]))        # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3

跟踪算法

跟踪 [2, 4, 1, 3]：分解为 [2, 4] 和 [1, 3]。左侧子排序：[2, 4] → 已排序的 [2,4]，0 个逆序对。右侧子排序：[1, 3] → 已排序的 [1,3]，0 个逆序对。合并 [2,4] 和 [1,3]：取出 1（计数增加 2，因为 2>1 且 4>1），取出 2（计数不变），取出 3（计数增加 1，因为 4>3），取出 4。跨部分逆序对 = 3。总数 = 0+0+3 = 3。验证：逆序对 (2,1)、(4,1)、(4,3) = 3 个逆序对。✓

def count_with_trace(arr):
    def ms(arr, depth=0):
        indent = '  ' * depth
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = ms(arr[:mid], depth+1)
        R, rc = ms(arr[mid:], depth+1)
        merged, cc = merge_c(L, R)
        print(f'{indent}merge({L},{R}) → cross={cc}')
        return merged, lc + rc + cc
    
    def merge_c(L, R):
        res, c, i, j = [], 0, 0, 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]: res.append(L[i]); i += 1
            else: res.append(R[j]); j += 1; c += len(L) - i
        return res + L[i:] + R[j:], c
    
    _, total = ms(arr)
    return total

print('Total inversions:', count_with_trace([2, 4, 1, 3]))

为何能够正确捕获跨部分逆序对

正确性：任何满足 i < j 的逆序对 (a[i], a[j]) 都恰好属于以下三类中的一类：(1) 两个元素都在左半部分——由递归的左侧调用统计。(2) 两个元素都在右半部分——由递归的右侧调用统计。(3) 左半部分元素 > 右半部分元素——在 merge 过程中作为跨部分逆序对统计。这些类别互斥且完备，因此不会重复统计或遗漏任何逆序对。这种划分论证是标准的分治法正确性证明。

# Verification: compare with brute force on random arrays
import random

def count_brute(arr):
    n = len(arr)
    return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a, 0
        m=len(a)//2
        L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr)[1]

for _ in range(100):
    arr = random.choices(range(20), k=random.randint(1,10))
    assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')

逆序对计数的应用

逆序对可以衡量有序程度。应用包括：(1) 排名相关性：两个排名列表之间的肯德尔 tau 距离就是逆序对的数量。(2) 插入排序效率：插入排序执行的交换次数恰好等于逆序对的数量。(3) 冒泡排序分析：冒泡排序的每一趟都会减少逆序对；所需趟数等于逆序对的数量。(4) 谜题可解性：当且仅当逆序对数量具有特定奇偶性时，八数码或十五数码问题才有解。

# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems

def kendall_tau(rank1, rank2):
    '''Count inversions where rank1 and rank2 disagree on relative order.'''
    # Map rank2 positions to create a comparison sequence
    pos = {v: i for i, v in enumerate(rank2)}
    # Convert rank1 to position-in-rank2 ordering
    arr = [pos[v] for v in rank1]
    return count_inversions(arr)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

print(kendall_tau([1,2,3],[3,1,2]))  # measures disagreement

翻转对

翻转对（LeetCode 493）统计满足 i < j 且 nums[i] > 2 × nums[j] 的索引对 (i, j)。标准逆序对计数使用 nums[i] > nums[j]。这里，阈值变为 2 × nums[j]。修改归并排序：在合并之前统计跨分割的翻转对（使用双指针进行统计，同时确保左半部分仍有满足条件的元素），然后按正常方式合并。总时间复杂度为 O(n log n)。

def reverse_pairs(nums):
    def merge_sort_count(arr):
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = merge_sort_count(arr[:mid])
        R, rc = merge_sort_count(arr[mid:])
        # Count cross pairs: L[i] > 2*R[j]
        j = 0
        cross = 0
        for l_val in L:
            while j < len(R) and l_val > 2 * R[j]:
                j += 1
            cross += j
        # Normal merge (separate from count)
        merged = []
        i = jj = 0
        while i < len(L) and jj < len(R):
            if L[i] <= R[jj]: merged.append(L[i]); i += 1
            else: merged.append(R[jj]); jj += 1
        merged += L[i:] + R[jj:]
        return merged, lc + rc + cross
    
    return merge_sort_count(nums)[1]

print(reverse_pairs([1, 3, 2, 3, 1]))  # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3

全局逆序对数与局部逆序对数

全局逆序对与局部逆序对（LeetCode 775）：给定一个由 0..n-1 组成的排列，判断全局逆序对的数量（所有满足 i<j 且 a[i]>a[j] 的数对）是否等于局部逆序对的数量（相邻数对）。关键洞见：每个局部逆序对也都是全局逆序对，因此全局逆序对数量 ≥ 局部逆序对数量。当且仅当不存在非相邻逆序对时，两者才相等——也就是说，没有任何元素与其排序后的位置相差超过 1。这样就可以简化为检查所有 i 是否满足 abs(a[i] - i) ≤ 1。

def is_ideal_permutation(A):
    '''Global inversions == local inversions
    iff no element is more than 1 position from its sorted index.'''
    return all(abs(a - i) <= 1 for i, a in enumerate(A))

print(is_ideal_permutation([1, 0, 2]))  # True
print(is_ideal_permutation([1, 2, 0]))  # False (A[0]=1 is far from 2, A[2]=0 is far)

# Verification with inversion counts
print(count_inversions([1, 0, 2]))  # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1)  # 1 (equal)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

逆序对计数复杂度总结

总结：暴力法的逆序对计数为 O(n²)。修改后的归并排序通过在合并步骤中统计跨分割逆序对，实现 O(n log n)。额外成本是每次比较 O(1)（加上 len(left) - i），因此每个合并层级的总额外开销为 O(n)，与标准归并排序相同。辅助数组需要 O(n) 的空间。这是使用分治法在对数线性时间内统计顺序统计量的经典示例。

import time, random

def time_method(func, arr):
    start = time.time()
    result = func(arr[:])
    return result, time.time() - start

def count_brute(arr):
    return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C:   {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')

快速检查

请检查您对本课数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：逆序对可以衡量数组的无序程度，暴力法的复杂度为 O(n²)，而分治法的复杂度为 O(n log n)；修改后的归并排序每次从右半部分取出元素并将其排在左半部分元素之前时，都会加上 len(left)-i，从而统计跨两半的逆序对；以及正确性依赖于这样的划分：左半部分内部、右半部分内部和跨两半的逆序对彼此互斥，并且共同覆盖所有逆序对。接下来，我们将学习用于寻找多数元素的 Boyer-Moore 投票算法。

常见问题解答