C++ 求逆序数的代码 |21xrx.com

C++ 求逆序数的代码

2023-07-05 05:24:38 深夜i 35 0

C++ 求逆序数代码

逆序数，是指一个数列中逆序对的数量。而借助计算机编程，我们可以快速地计算出一个数列的逆序数。在 C++ 编程中，有一种常见的算法就是使用归并排序。下面是这种算法的具体实现方法：

#include <iostream>
using namespace std;
const int MAXN = 500010;
int n, a[MAXN], t[MAXN];
long long merge_sort(int l, int r) {
  if (l == r) return 0;
  int mid = (l + r) / 2;
  long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
  int i = l, j = mid + 1, pos = l;
  while (i <= mid && j <= r) {
    if (a[i] <= a[j]) {
      t[pos++] = a[i++];
    } else {
      res += mid - i + 1;
      t[pos++] = a[j++];
    }
  }
  while (i <= mid) t[pos++] = a[i++];
  while (j <= r) t[pos++] = a[j++];
  for (int i = l; i <= r; i++) a[i] = t[i];
  return res;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  long long ans = merge_sort(1, n);
  cout << ans << endl;
  return 0;
}

上述代码的核心功能是 `merge_sort()` 函数，该函数实现归并排序算法，并返回数列中逆序对的数量。在 `merge_sort()` 函数中，使用了双指针的思想，将排序后的两个子数组进行归并，同时统计出逆序对的数量。最终，将已排序的数组复制回原来的数组中，完成排序操作。

在 `main()` 函数中，读入数列，调用 `merge_sort()` 函数，输出结果。需要注意的是，由于数据范围较大，需要使用 long long 类型来存储逆序对的数量。

上一篇: idea打包java可执行jar包

下一篇: "C++中如何将二维数组作为参数传递"

评论区

相似文章