数组中的逆序对

1. 题目描述

输入一个数组,求出这个数组中的逆序对的总数。

例如在数组{7，5，6，4}中，一共存在 5 个逆序对，分别是(7,6), (7, 5), (7,4), (6,4), (5,4)。

2. 思路分析

暴力法的时间复杂度是 O(N^2)。利用归并排序的思路，可以将时间复杂度降低到 O(NlogN)。

比如对于 7、5、6、4 来说，会被分成 5、7 和 4、6 两组。

准备两个指针指向两组最后元素，当左边数组指针的对应元素小于右边指针对应元素，结果可以加上从左指针到右指针之间的元素个数（都是逆序的）。

依次移动指针，直到达到边界。

3. 代码实现

代码最后输出了数组，经过归并，数组已经是有序的了。

/**
 *
 * @param {Array} arr
 * @param {Number} start
 * @param {Number} end
 * @return {Number}
 */
function findInversePairNum(arr, start, end) {
    if (start === end) {
        return 0
    }

    const copy = new Array(end - start + 1)
    const length = (end - start) >> 1
    const leftNum = findInversePairNum(arr, start, start + length)
    const rightNum = findInversePairNum(arr, start + length + 1, end)

    let i = start + length, // 左子数组的最后一个下标
        j = end, // 右子数组的最后一个下标
        count = leftNum + rightNum,
        copyIndex = end - start // copy数组中的最后一个下标

    // 可以参考数据集合：[2, 3, 1, 4]
    for (; i >= start && j >= start + length + 1; ) {
        if (arr[i] > arr[j]) {
            copy[copyIndex--] = arr[i--]
            count += j - start - length
        } else {
            copy[copyIndex--] = arr[j--]
        }
    }

    for (; i >= start; --i) {
        copy[copyIndex--] = arr[i]
    }

    for (; j >= start + length + 1; --j) {
        copy[copyIndex--] = arr[j]
    }

    // 将排序号的数据放到原数组中
    for (i = 0; i < end - start + 1; ++i) {
        arr[i + start] = copy[i]
    }

    // clear
    copy.length = 0

    return count
}

/**
 * 测试代码
 */

const arr = [7, 5, 6, 4]
console.log(findInversePairNum(arr, 0, arr.length - 1)) // output: 5
console.log(arr) // output: [4, 5, 6, 7]