当前位置：首页 > JavaScript

js实现查找逆序数

2026-01-31 06:12:53JavaScript

查找逆序数的实现方法

逆序数（Inversion Count）用于衡量一个数组或序列的排序程度。逆序数定义为数组中满足 i < j 且 arr[i] > arr[j] 的元素对数。以下是几种常见的实现方法：

暴力法

直接遍历所有可能的元素对，统计逆序数。时间复杂度为 O(n²)，适用于小规模数据。

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

归并排序法

利用归并排序的分治思想，在合并过程中统计逆序数。时间复杂度为 O(n log n)，适合大规模数据。

function countInversionsMergeSort(arr) {
  function mergeAndCount(arr, left, mid, right) {
    const temp = [];
    let i = left, j = mid + 1, count = 0;

    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp.push(arr[i++]);
      } else {
        temp.push(arr[j++]);
        count += mid - i + 1;
      }
    }

    while (i <= mid) temp.push(arr[i++]);
    while (j <= right) temp.push(arr[j++]);
    for (let k = left; k <= right; k++) arr[k] = temp[k - left];

    return count;
  }

  function mergeSortAndCount(arr, left, right) {
    let count = 0;
    if (left < right) {
      const mid = Math.floor((left + right) / 2);
      count += mergeSortAndCount(arr, left, mid);
      count += mergeSortAndCount(arr, mid + 1, right);
      count += mergeAndCount(arr, left, mid, right);
    }
    return count;
  }

  return mergeSortAndCount(arr, 0, arr.length - 1);
}

使用二叉索引树（Fenwick Tree）

通过动态维护前缀和的方式统计逆序数。时间复杂度为 O(n log n)，但需要离散化数据。

js实现查找逆序数

function countInversionsFenwickTree(arr) {
  const unique = [...new Set(arr)].sort((a, b) => a - b);
  const rank = (x) => unique.indexOf(x) + 1;

  const fenwick = new Array(unique.length + 1).fill(0);
  function update(index, delta) {
    while (index < fenwick.length) {
      fenwick[index] += delta;
      index += index & -index;
    }
  }

  function query(index) {
    let sum = 0;
    while (index > 0) {
      sum += fenwick[index];
      index -= index & -index;
    }
    return sum;
  }

  let count = 0;
  for (let i = arr.length - 1; i >= 0; i--) {
    const r = rank(arr[i]);
    count += query(r - 1);
    update(r, 1);
  }
  return count;
}