编辑代码

function countInversions(arr) {
    if (arr.length <= 1) {
        return { sortedArray: arr, count: 0 };
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    const merge = (leftArr, rightArr) => {
        const sorted = [];
        let count = 0;
        let leftIndex = 0;
        let rightIndex = 0;

        while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
            if (leftArr[leftIndex] <= rightArr[rightIndex]) {
                sorted.push(leftArr[leftIndex]);
                leftIndex++;
            } else {
                sorted.push(rightArr[rightIndex]);
                rightIndex++;
                count += leftArr.length - leftIndex;
            }
        }

        return {
            sorted: sorted.concat(leftArr.slice(leftIndex), rightArr.slice(rightIndex)),
            count: count,
        };
    };

    const { sortedArray: leftSorted, count: leftCount } = countInversions(left);
    const { sortedArray: rightSorted, count: rightCount } = countInversions(right);
    const { sorted, count: mergeCount } = merge(leftSorted, rightSorted);

    return {
        sortedArray: sorted,
        count: leftCount + rightCount + mergeCount,
    };
}
const array = [2, 4, 3, 1, 5, 6];
const { count } = countInversions(array);
console.log(`逆序对数量: ${count}`);