怎么求排列逆序数

排列逆序数是指在一个排列中，若有两个数在数组中的顺序与它们在完全有序的数组中的顺序相反，则这两个数就构成了一个逆序对，排列逆序数就是逆序对的个数。求排列逆序数可以使用归并排序的思想，具体步骤如下：

1. 将原始数组分成左右两个子数组，对左右两个子数组进行递归排序，得到左右两个有序数组。

2. 对左右两个有序数组进行归并操作，得到一个完全有序的数组，并统计逆序对的数量。

3. 将逆序对数量返回。

具体代码实现如下：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, count1 = merge_sort(arr[:mid])
    right, count2 = merge_sort(arr[mid:])
    merged, count3 = merge(left, right)

    return merged, count1 + count2 + count3

def merge(left, right):
    i, j = 0, 0
    count = 0
    merged = []

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            count += len(left) - i

    merged += left[i:]
    merged += right[j:]

    return merged, count

其中，merge_sort函数接收一个数组，返回排好序的数组和逆序对数量。merge函数接收左右两个有序数组，返回归并后的完全有序数组和逆序对数量。在归并的过程中，若左边的元素大于右边的元素，则左边剩余的元素都与右边的元素构成逆序对，因此将逆序对数量加上len(left) - i。最终，将左右两个有序数组归并成一个完全有序的数组，并返回逆序对数量