C++ 求逆序对数量 |21xrx.com

C++ 求逆序对数量

2023-07-01 16:15:53 深夜i -- --

C++ 逆序对数量算法排序

C++求逆序对数量

在计算机科学中，逆序对是指在一个数组或者序列中，如果某个元素A[i]大于A[j]，并且i

C++实现逆序对数量的算法有很多，其中比较常用的是归并排序算法。在这个算法中，逆序对数量就是合并两个排好序的子数组时，两个子数组之间的逆序对数量，这些逆序对数量可以在合并的同时被计算出来。归并排序算法的时间复杂度是O(nlogn)，其中n是数组的大小。

以下是C++实现逆序对数量的代码：


#include <iostream>
using namespace std;
long long merge(int arr[], int l, int mid, int r) {
  long long inv = 0;
  int i = l, j = mid + 1, k = 0;
  int temp[r - l + 1];
  while (i <= mid && j <= r) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      inv += mid - i + 1;
    }
  }
  while (i <= mid) {
    temp[k++] = arr[i++];
  }
  while (j <= r) {
    temp[k++] = arr[j++];
  }
  for (i = l, k = 0; i <= r; ++i, ++k) {
    arr[i] = temp[k];
  }
  return inv;
}
long long mergeSort(int arr[], int l, int r) {
  long long inv = 0;
  if (l < r) {
    int mid = (l + r) / 2;
    inv += mergeSort(arr, l, mid);
    inv += mergeSort(arr, mid + 1, r);
    inv += merge(arr, l, mid, r);
  }
  return inv;
}
int main() {
  int arr[] = 5;
  int n = 10;
  cout << "逆序对数量为：" << mergeSort(arr, 0, n - 1) << endl;
  return 0;
}

在主函数中，我们先定义一个整型数组和数组的大小n（这里是10），然后调用mergeSort进行归并排序并返回逆序对数量。最后，在屏幕上输出逆序对数量的大小。

在这个代码中，函数merge用于合并两个排好序的子序列，并返回子序列之间的逆序对数量。而函数mergeSort用于把原数组递归地分成小块，然后分别对每个小块进行排序和合并，最终返回整个数组中逆序对数量的值。

需要注意的是，在函数merge中，变量inv用于计算逆序对数量。当左子序列的元素大于右子序列的元素时，左子序列中的元素也一定大于右子序列中剩下的所有元素，因此inv的增量就是mid - i + 1，其中，mid是左子序列的最后一个元素的下标。

结论

C++求逆序对数量的算法是一个非常实用的算法，用于统计一个数组或序列中的逆序对数量。在本文中，我们使用了归并排序的思想，并通过函数合并两个排好序的子序列计算逆序对的数量。在程序中，我们定义了两个函数merge和mergeSort，这两个函数分别用于合并两个排好序的子序列和把原数组递归地分成小块，然后分别对每个小块进行排序和合并，最终返回整个数组中逆序对数量的值。

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

下一篇: Node.js 实现生成数字序号功能

评论区

()

相似文章