使用归并排序计算数组中逆序对的 C/C++ 程序？

对给定数组进行排序时发生的逆序对的数量称为逆序对数。逆序对问题是一个经典问题，可以使用归并排序算法解决。在这个问题中，我们将计算数组中每个元素左侧比它大的元素的数量，并将计数添加到输出中。此逻辑在归并排序的合并函数中完成。

为了更好地理解主题，让我们举个例子。让我们考虑两个参与合并过程的子数组 -

 

 

Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5

解释

数组的逆序对数

给定一个数组，找出它的逆序对数。如果 (i < j) 且 (A[i] > A[j])，则对 (i, j) 称为数组 A 的逆序对。我们需要计算数组 arr 中所有这样的对。

例如，

数组中有 5 个逆序对

(9,6), (9,4), (9,5), (6,4), (6,5)

1. 比较元素的值。

2. 如果较低索引处的数值较高，则递增计数器。

3. 显示结果。

示例

#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
   int k = low, i = low, j = mid + 1;
   int inversionCount = 0;
   while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) {
         aux[k++] = arr[i++];
      } else {
         aux[k++] = arr[j++];
         inversionCount += (mid - i + 1); // NOTE
      }
   }
   while (i <= mid)
   aux[k++] = arr[i++];
   for (int i = low; i <= high; i++)
      arr[i] = aux[i];
   return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
   if (high == low) // if run size == 1
      return 0;
   int mid = (low + ((high - low) >> 1));
   int inversionCount = 0;
   inversionCount += MergeSort(arr, aux, low, mid);
   inversionCount += MergeSort(arr, aux, mid + 1, high);
   inversionCount += Merge(arr, aux, low, mid, high);
   return inversionCount;
}
int main() {
   int arr[] = { 1, 9, 6, 4, 5 };
   int N = 5;
   int aux[N];
   for (int i = 0; i < N; i++)
      aux[i] = arr[i];
   printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
   return 0;
}

更新于: 2019年8月19日

234 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告