编辑代码

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

  // 分割数组为两半
  const middle = Math.floor(arr.length / 2);
  const leftHalf = arr.slice(0, middle);
  const rightHalf = arr.slice(middle);

  // 递归计算左右两半的逆序对数
  const leftResult = countInversions(leftHalf);
  const rightResult = countInversions(rightHalf);

  // 合并左右两半并计算跨越左右两半的逆序对数
  const mergedResult = mergeAndCount(leftResult.sortedArray, rightResult.sortedArray);

  // 返回总的逆序对数
  return {
    sortedArray: mergedResult.sortedArray,
    count: leftResult.count + rightResult.count + mergedResult.count,
  };
}

function mergeAndCount(left, right) {
  let merged = [];
  let leftIndex = 0;
  let rightIndex = 0;
  let inversionCount = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      merged.push(left[leftIndex]);
      leftIndex++;
    } else {
      // 如果左半边的元素大于右半边的元素，就构成逆序对
      merged.push(right[rightIndex]);
      rightIndex++;
      inversionCount += left.length - leftIndex;
    }
  }

  // 将左右两半剩余的元素合并
  merged = merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));

  return {
    sortedArray: merged,
    count: inversionCount,
  };
}