设计分治算法统计 给定排列中含有逆序的个数。

算法思路：

将排列分成左半部分和右半部分，分别递归求解左半部分和右半部分的逆序数，再统计跨越左右两部分的逆序数。跨越左右两部分的逆序数可以通过归并排序的思想计算得到。具体地，将左半部分和右半部分分别排好序后，将它们合并成一个排好序的序列。在合并的过程中，当右半部分的当前元素小于左半部分的当前元素时，计算逆序数并将右半部分的当前元素插入到合并后的序列中；否则，将左半部分的当前元素插入到合并后的序列中。

算法实现：

def merge_and_count(left, right):
    i, j = 0, 0
    count = 0
    result = []
    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

def count_inversions(nums):
    if len(nums) <= 1:
        return nums, 0
    mid = len(nums) // 2
    left, left_count = count_inversions(nums[:mid])
    right, right_count = count_inversions(nums[mid:])
    merged, cross_count = merge_and_count(left, right)
    return merged, left_count + right_count + cross_count

nums = [2, 4, 1, 3, 5]
_, count = count_inversions(nums)
print(count)  # 输出 3

算法分析：

设排列的长度为 n。分治算法的时间复杂度为 O(nlogn)，归并排序的时间复杂度为 O(nlogn)，因此总的时间复杂度为 O(nlogn)。

空间复杂度为 O(nlogn)，因为每一层递归都需要使用 O(n) 的空间。