编辑代码

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

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

  const leftResult = countInversions(left);
  const rightResult = countInversions(right);

  const mergeResult = mergeAndCountSplitInversions(leftResult.sortedArray, rightResult.sortedArray);

  const totalInversions = leftResult.inversions + rightResult.inversions + mergeResult.inversions;

  return { sortedArray: mergeResult.sortedArray, inversions: totalInversions };
}

function mergeAndCountSplitInversions(left, right) {
  let i = 0;
  let j = 0;
  let inversions = 0;
  const merged = [];

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i]);
      i++;
    } else {
      merged.push(right[j]);
      j++;
      // 如果左侧元素大于右侧元素，产生逆序对
      inversions += left.length - i;
    }
  }

  return {
    sortedArray: merged.concat(left.slice(i)).concat(right.slice(j)),
    inversions: inversions,
  };
}

// 测试示例
const arr1 = [6, 5, 4, 3, 2, 1];

const arr2 = [2, 4, 3, 1, 5, 6];
const result1 = countInversions(arr1);
console.log("逆序对1的个数:", result1.inversions);

const result2 = countInversions(arr2);
console.log("逆序对2的个数:", result2.inversions);