逆序对个数求解python加注释

以下是逆序对个数求解 Python 代码，附有详细注释：

def merge_sort(arr):
    if len(arr) == 1: # 当长度为1时，停止拆分
        return arr

    mid = len(arr) // 2 # 找到中间点
    left = arr[:mid] # 分割出左边部分
    right = arr[mid:] # 分割出右边部分

    left = merge_sort(left) # 递归对左边部分进行排序
    right = merge_sort(right) # 递归对右边部分进行排序

    return merge(left, right) # 将左右两个有序部分合并

def merge(left, right):
    result = [] # 新建空数组存放合并后的有序数列

    i = 0
    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

    result += left[i:] # 将剩余的左边的数都放入有序数列中
    result += right[j:] # 将剩余的右边的数都放入有序数列中

    return result

def count_inversions(arr):
    _, count = merge_sort_helper(arr)
    return count

def merge_sort_helper(arr):
    if len(arr) == 1: # 停止拆分
        return arr, 0

    mid = len(arr) // 2 # 找到中间点
    left = arr[:mid] # 分割出左边部分
    right = arr[mid:] # 分割出右边部分

    # 分别递归进行归并和计算逆序对个数
    left, left_count = merge_sort_helper(left)
    right, right_count = merge_sort_helper(right)

    # 合并两个有序部分，并计算逆序对个数
    merged_arr, merged_count = merge_count_split(left, right)

    # 返回合并后的有序数组和逆序对个数之和
    return merged_arr, left_count + right_count + merged_count

def merge_count_split(left, right):
    result = [] # 存放有序数列
    count = 0 # 逆序对个数

    i = 0
    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

    result += left[i:] # 将剩余的左边的数放入有序数组中
    result += right[j:] # 将剩余的右边的数放入有序数组中

    return result, count

# 测试
arr = [7, 3, 6, 1, 8, 2, 9, 4, 5]
print(count_inversions(arr)) # 输出逆序对个数为 20

注意，这段代码利用了归并排序的思想来解决逆序对的问题。由于归并排序的时间复杂度为 O(nlogn)，因此该算法的时间复杂度也为 O(nlogn)。