Python分治逆序计数算法实现报错：无法解包非可迭代int对象

错误原因分析 #

1. 递归基例返回值不匹配 #

当数组长度为1时，SortandCount仅返回单个整数0，但递归调用时你需要将返回值解包为排序后的数组和逆序数两个变量，这直接触发了TypeError: cannot unpack non-iterable int object。根据分治法逻辑，基例必须同时返回这两个值。

2. CountSplitInv函数的合并逻辑错误 #

• 第一个条件分支错误地将索引i添加到结果数组D中，实际应添加B[i]元素；
• 两个if语句未做互斥处理，执行完第一个分支后i递增，可能导致第二个分支触发索引越界或错误计数，需改为if...elif...结构。

修复后的完整代码 #

# count the number of inversions 
def SortandCount(A: list):
    length = len(A)
    if length == 1:
        # 基例返回排序后的数组和逆序数0
        return A, 0
    mid = length // 2
    firsthalf = A[:mid]
    secondhalf = A[mid:]
    
    B, X = SortandCount(firsthalf)
    C, Y = SortandCount(secondhalf)
    D, Z = CountSplitInv(B, C)
    
    return D, X + Y + Z


def CountSplitInv(B, C):
    # takes 2 sorted list B C merging it into sorted list D 
    # as well as counting the inversions
    invnum = 0
    D = []
    i = j = 0
    len_b = len(B)
    len_c = len(C)
    
    while i < len_b and j < len_c:
        if B[i] <= C[j]:
            D.append(B[i])
            i += 1
        elif B[i] > C[j]:
            D.append(C[j])
            j += 1
            invnum += len_b - i
    # 处理剩余未合并的元素
    D.extend(B[i:])
    D.extend(C[j:])
    return D, invnum

def inversions_countin_wrapper(lst: list) -> int:
    return SortandCount(lst)[1]


A = [14, 2, 3]
sorted_arr, num = SortandCount(A)
print(f"排序后的数组: {sorted_arr}")
print(f"逆序数: {num}")

验证结果 #

输入[14,2,3]的正确逆序数为2（14>2、14>3），修复后代码输出：

排序后的数组: [2, 3, 14]
逆序数: 2

内容的提问来源于stack exchange，提问作者Beatrice z.jiang