通过归并排序求逆序对数量

为什么是归并排序, 而不是其他的排序算法呢?
因为归并排序涉及到了两个有序序列的合并, 非常方便求逆序对数量.

具我所知, 还有一种算法: 树状数组(BIT)
前几天刚刚写过, 就不重复了, 可以看我写的Leetcode题解:
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/pythonshu-zhuang-shu-zu-jie-fa-zhu-shi-x-f449/

时间复杂度

归并排序, 顺便求逆序数
归并排序的时间复杂度是O(nlogn)
因此, 本代码的时间复杂度就是O(nlogn)

Python 代码

def mergesort(A):
    n = len(A)
    if n <= 1:
        return 0, A
    mid = n // 2
    cnt1, left = mergesort(A[:mid])
    cnt2, right = mergesort(A[mid:])
    i, j = 0, 0
    cnt = cnt1 + cnt2
    ans = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            ans.append(left[i])
            i += 1
        else:
            ans.append(right[j])
            j += 1
            cnt += len(left) - i
    if i < len(left):
        ans.extend(left[i:])
    else:
        ans.extend(right[j:])
    return cnt, ans



while True:
    n = int(input())
    if not n:
        break
    A = []
    for _ in range(n):
        A.append(int(input()))
    cnt, B = mergesort(A)
    print(cnt)