js实现查找逆序数

逆序数概念

逆序数指在一个序列中，前面的元素大于后面的元素的对数。例如序列 [2, 4, 1, 3, 5] 中，逆序对有 (2,1)、(4,1)、(4,3)，逆序数为 3。

暴力法实现

直接遍历所有可能的元素对，统计满足逆序条件的对数：

function countInversions(arr) {
  let count = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) count++;
    }
  }
  return count;
}

时间复杂度为 O(n²)，适合小规模数据。

归并排序优化法

利用归并排序过程统计逆序数，时间复杂度优化至 O(n log n)：

function countInversions(arr) {
  let temp = new Array(arr.length);
  return mergeSort(arr, temp, 0, arr.length - 1);
}

function mergeSort(arr, temp, left, right) {
  let mid, invCount = 0;
  if (right > left) {
    mid = Math.floor((right + left) / 2);
    invCount += mergeSort(arr, temp, left, mid);
    invCount += mergeSort(arr, temp, mid + 1, right);
    invCount += merge(arr, temp, left, mid + 1, right);
  }
  return invCount;
}

function merge(arr, temp, left, mid, right) {
  let i = left, j = mid, k = left, invCount = 0;
  while (i <= mid - 1 && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      invCount += (mid - i);
    }
  }
  while (i <= mid - 1) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (i = left; i <= right; i++) arr[i] = temp[i];
  return invCount;
}

使用示例

const arr = [2, 4, 1, 3, 5];
console.log(countInversions(arr)); // 输出 3

注意事项

• 暴力法简单但效率低，适用于教学演示或极小数据集。
• 归并排序法虽然代码复杂，但在处理大规模数据时优势明显。
• 若需要处理浮点数或特殊比较逻辑，需修改比较条件部分。