js实现查找逆序数

逆序数简介

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

暴力法实现

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

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;
}

// 示例
console.log(countInversions([2, 4, 1, 3, 5])); // 输出 3

归并排序优化法

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

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

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;
}

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

  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      count += (mid - i + 1); // 统计逆序数
    }
  }

  while (i <= mid) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (let p = 0; p < k; p++) arr[left + p] = temp[p];

  return count;
}

// 示例
console.log(countInversions([2, 4, 1, 3, 5])); // 输出 3

注意事项

• 暴力法简单直观，但性能较差。
• 归并排序法效率更高，但实现稍复杂。
• 若需处理浮点数或自定义比较逻辑，需调整比较条件（如将 arr[i] <= arr[j] 改为自定义函数）。