对给定数组进行排序时发生的反转计数称为反转计数。逆问题是一个经典问题,可以使用归并排序算法来解决。在此问题 v 中,我们将计算其左侧大于它的所有元素,并将计数添加到输出。这个逻辑是在合并排序的合并函数中完成的。
为了更好地理解这个主题,让我们举一个例子。让我们考虑合并过程中涉及的两个子数组 -




Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5
说明
数组的反转次数
给定一个数组,找出它的反转次数。如果 (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 > 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 </stdio.h>
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











