# 算法：计算数组中的反转(逆序)S1（使用合并排序）

2021年3月30日12:45:49 发表评论 729 次浏览

## 本文概述

``````Input: arr[] = {8, 4, 2, 1}
Output: 6

Explanation: Given array has six inversions:
(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).

Input: arr[] = {3, 1, 2}
Output: 2

Explanation: Given array has two inversions:
(3, 1), (3, 2)``````

• 方法：遍历数组, 并为每个索引找到数组右侧较小元素的数量。这可以使用嵌套循环来完成。对数组中所有索引的计数求和, 然后打印总和。
• 算法：
1. 从头到尾遍历数组
2. 对于每个元素, 使用另一个循环查找小于当前数量的元素数, 直到该索引为止。
3. 总结每个索引的反转计数。
4. 打印反转计数。
• 实现

## C ++

``````// C++ program to Count Inversions
// in an array
#include <bits/stdc++.h>
using namespace std;

int getInvCount( int arr[], int n)
{
int inv_count = 0;
for ( int i = 0; i < n - 1; i++)
for ( int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;

return inv_count;
}

// Driver Code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << " Number of inversions are "
<< getInvCount(arr, n);
return 0;
}

// This code is contributed
// by Akanksha Rai``````

## C

``````// C program to Count
// Inversions in an array
#include <stdio.h>
#include <stdlib.h>
int getInvCount( int arr[], int n)
{
int inv_count = 0;
for ( int i = 0; i < n - 1; i++)
for ( int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;

return inv_count;
}

/* Driver program to test above functions */
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( " Number of inversions are %d \n" , getInvCount(arr, n));
return 0;
}``````

## Java

``````// Java program to count
// inversions in an array
class Test {
static int arr[] = new int [] { 1 , 20 , 6 , 4 , 5 };

static int getInvCount( int n)
{
int inv_count = 0 ;
for ( int i = 0 ; i < n - 1 ; i++)
for ( int j = i + 1 ; j < n; j++)
if (arr[i] > arr[j])
inv_count++;

return inv_count;
}

// Driver method to test the above function
public static void main(String[] args)
{
System.out.println( "Number of inversions are "
+ getInvCount(arr.length));
}
}``````

## Python3

``````# Python3 program to count
# inversions in an array

def getInvCount(arr, n):

inv_count = 0
for i in range (n):
for j in range (i + 1 , n):
if (arr[i] > arr[j]):
inv_count + = 1

return inv_count

# Driver Code
arr = [ 1 , 20 , 6 , 4 , 5 ]
n = len (arr)
print ( "Number of inversions are" , getInvCount(arr, n))

# This code is contributed by Smitha Dinesh Semwal``````

## C#

``````// C# program to count inversions
// in an array
using System;
using System.Collections.Generic;

class GFG {

static int [] arr = new int [] { 1, 20, 6, 4, 5 };

static int getInvCount( int n)
{
int inv_count = 0;

for ( int i = 0; i < n - 1; i++)
for ( int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;

return inv_count;
}

// Driver code
public static void Main()
{
Console.WriteLine( "Number of "
+ "inversions are "
+ getInvCount(arr.Length));
}
}

// This code is contributed by Sam007``````

## 的PHP

``````<?php
// PHP program to Count Inversions
// in an array

function getInvCount(& \$arr , \$n )
{
\$inv_count = 0;
for ( \$i = 0; \$i < \$n - 1; \$i ++)
for ( \$j = \$i + 1; \$j < \$n ; \$j ++)
if ( \$arr [ \$i ] > \$arr [ \$j ])
\$inv_count ++;

return \$inv_count ;
}

// Driver Code
\$arr = array (1, 20, 6, 4, 5 );
\$n = sizeof( \$arr );
echo "Number of inversions are " , getInvCount( \$arr , \$n );

// This code is contributed by ita_c
?>``````
• 输出如下：
``Number of inversions are 5``
• 复杂度分析：
• 时间复杂度：O(n ^ 2), 需要两个嵌套循环才能从头到尾遍历数组, 因此时间复杂度为O(n ^ 2)
• 空间复杂:O(1), 不需要额外的空间。

• 方法：
假设数组左半边和右半边的反转次数(分别为inv1和inv2), 在Inv1 + Inv2中没有考虑哪些反转？答案是–在合并步骤中需要计算的反转数。因此, 要获得许多反转, 需要在左子数组, 右子数组和merge()中添加许多反转。

• 怎么获得的merge()中的反转次数？
在合并过程中, 让我用于索引左子数组, 让j用于右子数组。在merge()的任何步骤中, 如果a [i]大于a [j], 则存在(mid – i)个反转。因为左子数组和右子数组已排序, 所以左子数组中的所有其余元素(a [i + 1], a [i + 2]…a [mid])将大于a [j]
• 完整图片：
• 算法：
1. 这个想法类似于合并排序, 将数组分成两个相等或几乎相等的两半, 直到达到基本情况为止。
2. 创建一个函数合并, 计算合并数组的两半时的反转次数, 创建两个索引i和j, i是上半部分的索引, j是下半部分的索引。如果a [i]大于a [j], 则存在(mid – i)个反演。因为左子数组和右子数组已排序, 所以左子数组中的所有其余元素(a [i + 1], a [i + 2]…a [mid])将大于a [j]。
3. 创建一个递归函数, 将数组分成两半, 然后求和前一半的求反数​​, 再求后一半的求反数​​, 然后将二者合并, 求出答案。
4. 递归的基本情况是在给定的一半中只有一个元素。
5. 打印答案
• 实现

## C ++

``````// C++ program to Count
// Inversions in an array
// using Merge Sort
#include <bits/stdc++.h>
using namespace std;

int _mergeSort( int arr[], int temp[], int left, int right);
int merge( int arr[], int temp[], int left, int mid, int right);

/* This function sorts the
input array and returns the
number of inversions in the array */
int mergeSort( int arr[], int array_size)
{
int temp[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function
that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort( int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
/* Divide the array into two parts and
call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left) / 2;

/* Inversion count will be sum of
inversions in left-part, right-part
and number of inversions in merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);

/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}

/* This funt merges two sorted arrays
and returns inversion count in the arrays.*/
int merge( int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];

/* this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

// Driver code
int main()
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
int ans = mergeSort(arr, n);
cout << " Number of inversions are " << ans;
return 0;
}

// This is code is contributed by rathbhupendra``````

## C

``````// C program to Count
// Inversions in an array
// using Merge Sort
#include <stdio.h>
#include <stdlib.h>

int _mergeSort( int arr[], int temp[], int left, int right);
int merge( int arr[], int temp[], int left, int mid, int right);

/* This function sorts the input array and returns the
number of inversions in the array */
int mergeSort( int arr[], int array_size)
{
int * temp = ( int *) malloc ( sizeof ( int ) * array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive function that sorts the input
array and returns the number of inversions in the array.
*/
int _mergeSort( int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of the parts */
mid = (right + left) / 2;

/* Inversion count will be the sum of inversions in
left-part, right-part and number of inversions in
merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);

/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}

/* This funt merges two sorted arrays and returns inversion
count in the arrays.*/
int merge( int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];

/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

/* Driver program to test above functions */
int main( int argv, char ** args)
{
int arr[] = { 1, 20, 6, 4, 5 };
printf ( " Number of inversions are %d \n" , mergeSort(arr, 5));
getchar ();
return 0;
}``````

## Java

``````// Java implementation of the approach
import java.util.Arrays;

public class GFG {

// Function to count the number of inversions
// during the merge process
private static int mergeAndCount( int [] arr, int l, int m, int r)
{

// Left subarray
int [] left = Arrays.copyOfRange(arr, l, m + 1 );

// Right subarray
int [] right = Arrays.copyOfRange(arr, m + 1 , r + 1 );

int i = 0 , j = 0 , k = l, swaps = 0 ;

while (i < left.length && j < right.length)
{
if (left[i] <= right[j])
arr[k++] = left[i++];
else {
arr[k++] = right[j++];
swaps += (m + 1 ) - (l + i);
}
}
return swaps;
}

// Merge sort function
private static int mergeSortAndCount( int [] arr, int l, int r)
{

// Keeps track of the inversion count at a
// particular node of the recursion tree
int count = 0 ;

if (l < r) {
int m = (l + r) / 2 ;

// Total inversion count = left subarray count
// + right subarray count + merge count

// Left subarray count
count += mergeSortAndCount(arr, l, m);

// Right subarray count
count += mergeSortAndCount(arr, m + 1 , r);

// Merge count
count += mergeAndCount(arr, l, m, r);
}

return count;
}

// Driver code
public static void main(String[] args)
{
int [] arr = { 1 , 20 , 6 , 4 , 5 };

System.out.println(mergeSortAndCount(arr, 0 , arr.length - 1 ));
}
}

// This code is contributed by Pradip Basak``````

## Python3

``````# Python 3 program to count inversions in an array

# Function to Use Inversion Count
def mergeSort(arr, n):
# A temp_arr is created to store
# sorted array in merge function
temp_arr = [ 0 ] * n
return _mergeSort(arr, temp_arr, 0 , n - 1 )

# This Function will use MergeSort to count inversions

def _mergeSort(arr, temp_arr, left, right):

# A variable inv_count is used to store
# inversion counts in each recursive call

inv_count = 0

# We will make a recursive call if and only if
# we have more than one elements

if left < right:

# mid is calculated to divide the array into two subarrays
# Floor division is must in case of python

mid = (left + right) / / 2

# It will calculate inversion
# counts in the left subarray

inv_count + = _mergeSort(arr, temp_arr, left, mid)

# It will calculate inversion
# counts in right subarray

inv_count + = _mergeSort(arr, temp_arr, mid + 1 , right)

# It will merge two subarrays in
# a sorted subarray

inv_count + = merge(arr, temp_arr, left, mid, right)
return inv_count

# This function will merge two subarrays
# in a single sorted subarray
def merge(arr, temp_arr, left, mid, right):
i = left     # Starting index of left subarray
j = mid + 1 # Starting index of right subarray
k = left     # Starting index of to be sorted subarray
inv_count = 0

# Conditions are checked to make sure that
# i and j don't exceed their
# subarray limits.

while i < = mid and j < = right:

# There will be no inversion if arr[i] <= arr[j]

if arr[i] < = arr[j]:
temp_arr[k] = arr[i]
k + = 1
i + = 1
else :
# Inversion will occur.
temp_arr[k] = arr[j]
inv_count + = (mid - i + 1 )
k + = 1
j + = 1

# Copy the remaining elements of left
# subarray into temporary array
while i < = mid:
temp_arr[k] = arr[i]
k + = 1
i + = 1

# Copy the remaining elements of right
# subarray into temporary array
while j < = right:
temp_arr[k] = arr[j]
k + = 1
j + = 1

# Copy the sorted subarray into Original array
for loop_var in range (left, right + 1 ):
arr[loop_var] = temp_arr[loop_var]

return inv_count

# Driver Code
# Given array is
arr = [ 1 , 20 , 6 , 4 , 5 ]
n = len (arr)
result = mergeSort(arr, n)
print ( "Number of inversions are" , result)

# This code is contributed by ankush_953``````

## C#

``````// C# implementation of counting the
// inversion using merge sort

using System;
public class Test {

/* This method sorts the input array and returns the
number of inversions in the array */
static int mergeSort( int [] arr, int array_size)
{
int [] temp = new int [array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}

/* An auxiliary recursive method that sorts the input
array and returns the number of inversions in the
array. */
static int _mergeSort( int [] arr, int [] temp, int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
/* Divide the array into two parts and call
_mergeSortAndCountInv() for each of the parts */
mid = (right + left) / 2;

/* Inversion count will be the sum of inversions
in left-part, right-part
and number of inversions in merging */
inv_count += _mergeSort(arr, temp, left, mid);
inv_count
+= _mergeSort(arr, temp, mid + 1, right);

/*Merge the two parts*/
inv_count
+= merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}

/* This method merges two sorted arrays and returns
inversion count in the arrays.*/
static int merge( int [] arr, int [] temp, int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged
subarray*/
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];

/*this is tricky -- see above
* explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

// Driver method to test the above function
public static void Main()
{
int [] arr = new int [] { 1, 20, 6, 4, 5 };
Console.Write( "Number of inversions are "
+ mergeSort(arr, 5));
}
}
// This code is contributed by Rajput-Ji``````
• 输出如下：
``Number of inversions are 5``
• 复杂度分析：
• 时间复杂度：O(n log n), 使用的算法是分治法, 因此在每个级别中需要一个完整的数组遍历, 并且存在log n个级别, 因此时间复杂度为O(n log n)。
• 空间复杂:O(n), 临时数组。

http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf

http://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

• A+