9.A[0…n−1]是一个n个不同实数构成的数组。如果i<j,但是A[i]>A[j],则这对元素( A[i],A[j])被称为一个倒置( inversion)。设计一个O( nlogn)算法来计算数组中的倒置数量。写伪代码

为了计算给定数组 `A[0...n-1]` 中的倒置数量，我们可以使用归并排序的思想，同时在合并过程中计数倒置。这是一个经典的减少问题空间复杂度的方法，将原问题分解成规模更小的问题，再合并结果。

以下是伪代码实现：

function countInversions(A[], n):
    // 如果数组长度小于等于1，不存在倒置
    if n <= 1:
        return 0
    
    // 分割数组，找到中间位置 mid
    mid = floor(n / 2)
    
    // 对左半部分和右半部分递归调用 countInversions
    leftInversions = countInversions(A[0...mid], mid)
    rightInversions = countInversions(A[mid...n], n - mid)

    // 归并过程，统计倒置
    inversionsInMerge = mergeAndCountInversions(A[0...n], leftInversions, rightInversions, mid)
    
    return leftInversions + rightInversions + inversionsInMerge

function mergeAndCountInversions(leftArray[], rightArray[], leftSize, rightSize):
    mergedArray[] = new Array(leftSize + rightSize)
    inversionCount = 0

    leftIndex = 0
    rightIndex = 0
    for i in range(0, leftSize + rightSize):
        // 当左边数组还有元素且左边元素大于右边时，有倒置
        if (leftIndex < leftSize and (rightIndex == rightSize or leftArray[leftIndex] <= rightArray[rightIndex])):
            mergedArray[i] = leftArray[leftIndex]
            leftIndex += 1
        else:
            mergedArray[i] = rightArray[rightIndex]
            rightIndex += 1
            inversionCount += leftSize - leftIndex  // 统计倒置的数量

    // 将剩余的左边元素复制到数组中，并更新倒置计数
    while leftIndex < leftSize:
        mergedArray[i] = leftArray[leftIndex]
        leftIndex += 1
        inversionCount += leftSize - leftIndex  // 左边所有剩余元素都是倒置

    return inversionCount

这个算法的时间复杂度为 O(n log n)，因为每次分割都导致问题规模减半，而在合并阶段，我们需要线性时间来计算和统计倒置。