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

C++代码：求逆序数

2023-07-09 13:53:05 深夜i -- --

C++ 算法排序逆序数

逆序数是一个经常在计算机科学中用到的数学概念，指的是一个序列中逆序对的数量。在排序算法、图论算法等领域都有着广泛的应用。

如果要计算一个数列的逆序数，可以使用归并排序。在归并排序时，每次合并两个有序的子序列时，对于子序列中的每一个数，我们都可以统计一下它右侧有多少个数小于它，然后把这个数加到逆序数的计数器中即可。

下面是一份用 C++ 实现的计算逆序数的代码：


#include <iostream>
using namespace std;
long long mergeSort(int* a, int l, int r) {
  if(l >= r) return 0;
  int mid = (l + r) / 2;
  long long res = mergeSort(a, l, mid) + mergeSort(a, mid + 1, r);
  int* tmp = new int[r - l + 1];
  int i = l, j = mid + 1, k = 0;
  while(i <= mid && j <= r) {
    if(a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      res += (mid - i + 1);
      tmp[k++] = a[j++];
    }
  }
  while(i <= mid) tmp[k++] = a[i++];
  while(j <= r) tmp[k++] = a[j++];
  for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
  delete[] tmp;
  return res;
}
int main() {
  int a[] = 1;
  int n = sizeof(a) / sizeof(int);
  long long res = mergeSort(a, 0, n - 1);
  cout << res << endl;
  return 0;
}

代码中的 `mergeSort` 函数就是归并排序，其中统计逆序数的方法就是在将两个有序子序列合并成一个新的有序序列时，对于右侧的数，它的逆序对数量等于左侧子序列中比它大的元素数量，这部分就可以用一个计数器记录下来，并加到最终的逆序数统计结果中。

这份代码的时间复杂度是 O(nlogn)，但需要注意到可能会出现计算结果超出 int 范围的情况，因此我们需要使用 long long 类型来存储最终结果。

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

下一篇: C++中的内部类实现

评论区

()

相似文章