递归函数中数组赋值问题：分治法实现数组逆序计数异常

嘿，我看你在实现分治法计算数组逆序对的过程中遇到了递归里的数组处理问题，而且合并环节的代码也没写完对吧？我来帮你把这个问题理顺，并且给出完整的可运行代码。

你代码里可能踩的坑 #

• 逻辑判断用了位运算符&，而不是逻辑与and，这会导致条件判断逻辑出错
• 数组切片array[-n2:]可以简化为array[n1:]，更直观且不易出错
• 合并环节是统计跨子数组逆序对的核心，这部分你没写完，也是最容易出问题的地方
• 用math.floor(len(array)/2)不如直接用整数除法len(array)//2，Python里更简洁高效

修正后的完整代码 #

import math

def count_inv_sort(array):
    # 递归终止条件：数组长度为1，逆序对为0，返回(逆序对数, 排序后的数组)
    if len(array) == 1:
        return (0, array)
    else:
        # 拆分数组为左右两部分
        n1 = len(array) // 2  # 替代math.floor，更简洁
        array_1 = array[:n1]
        array_2 = array[n1:]  # 替代array[-n2:]，更直观
        
        # 递归处理左右子数组，得到各自的逆序对数和排序后的数组
        (inv1, sorted_array_1) = count_inv_sort(array_1)
        (inv2, sorted_array_2) = count_inv_sort(array_2)
        
        # 合并两个排序后的数组，同时统计跨子数组的逆序对
        i = 0  # sorted_array_1的指针
        j = 0  # sorted_array_2的指针
        inv_count = 0  # 跨子数组的逆序对数
        merged_array = []
        
        while i < len(sorted_array_1) and j < len(sorted_array_2):
            if sorted_array_1[i] <= sorted_array_2[j]:
                merged_array.append(sorted_array_1[i])
                i += 1
            else:
                # 当sorted_array_1[i] > sorted_array_2[j]时，sorted_array_1中i之后的所有元素都大于sorted_array_2[j]
                inv_count += len(sorted_array_1) - i
                merged_array.append(sorted_array_2[j])
                j += 1
        
        # 把剩余的元素添加到合并数组中
        merged_array.extend(sorted_array_1[i:])
        merged_array.extend(sorted_array_2[j:])
        
        # 总逆序对数 = 左子数组逆序对 + 右子数组逆序对 + 跨子数组逆序对
        total_inv = inv1 + inv2 + inv_count
        return (total_inv, merged_array)

# 测试示例
if __name__ == "__main__":
    test_array = [3, 1, 2, 4, 0]
    inv_count, sorted_arr = count_inv_sort(test_array)
    print(f"数组的逆序对数量：{inv_count}")  # 预期输出：6
    print(f"排序后的数组：{sorted_arr}")  # 预期输出：[0, 1, 2, 3, 4]

核心逻辑说明 #

1. 递归拆分：把数组不断拆分成左右两个子数组，直到每个子数组只有一个元素（此时逆序对为0）
2. 合并统计：在合并两个排序后的子数组时，如果左边当前元素大于右边当前元素，那么左边剩下的所有元素都和右边当前元素构成逆序对，直接加上len(sorted_array_1) - i即可，不用逐个统计，这也是分治法高效的原因（时间复杂度O(n log n)）
3. 总逆序对：最终的逆序对数是左子数组的逆序对、右子数组的逆序对，加上跨两个子数组的逆序对之和

内容的提问来源于stack exchange，提问作者Xiaohong