数组中的倒数计数

My answer in Python:

首先对数组进行排序并复制它。在我的程序中，B 表示已排序的数组。 2-迭代原始数组(未排序) ，并在排序列表中查找该元素的索引。还要记下元素的索引。 3-确保元素没有任何重复项，如果有，那么你需要将索引的值改为 -1。我程序中的 while 条件正是这样做的。 继续计算你的索引值的倒数，一旦你计算了元素的倒数，就移除它。

def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False


while first <= last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1


def solution(A):


B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1


inversion_count += j
B.pop(j)


if inversion_count > 1000000000:
return -1
else:
return inversion_count


print solution([4, 10, 11, 1, 3, 9, 10])

Well I have a different solution but I am afraid that would work only for distinct array elements.

//Code
#include <bits/stdc++.h>
using namespace std;


int main()
{
int i,n;
cin >> n;
int arr[n],inv[n];
for(i=0;i<n;i++){
cin >> arr[i];
}
vector<int> v;
v.push_back(arr[n-1]);
inv[n-1]=0;
for(i=n-2;i>=0;i--){
auto it = lower_bound(v.begin(),v.end(),arr[i]);
//calculating least element in vector v which is greater than arr[i]
inv[i]=it-v.begin();
//calculating distance from starting of vector
v.insert(it,arr[i]);
//inserting that element into vector v
}
for(i=0;i<n;i++){
cout << inv[i] << " ";
}
cout << endl;
return 0;
}

为了解释我的代码，我们继续从 Array 的末尾添加元素。对于任何传入数组元素，我们找到 矢量 v 中第一个元素的索引，它大于我们的传入元素并将该值赋给传入元素索引的倒数计数。然后，我们将元素插入到向量 v 中，在它的正确位置，这样向量 v 保持排序顺序。

//INPUT
4
2 1 4 3


//OUTPUT
1 0 1 0


//To calculate total inversion count just add up all the elements in output array

最好的优化方法是通过合并排序来解决这个问题，在合并排序中我们可以通过比较左右数组来检查需要多少次反转。当左数组中的元素大于右数组中的元素时，就是倒排。

合并排序方法:-

这是密码。代码是完全相同的合并排序，除了代码片段下的 mergeToParent方法，其中我是计算在别的条件下的 (left[leftunPicked] < right[rightunPicked])倒置

public class TestInversionThruMergeSort {
    

static int count =0;


public static void main(String[] args) {
int[] arr = {6, 9, 1, 14, 8, 12, 3, 2};
        



partition(arr);


for (int i = 0; i < arr.length; i++) {


System.out.println(arr[i]);
}
        

System.out.println("inversions are "+count);


}


public static void partition(int[] arr) {


if (arr.length > 1) {


int mid = (arr.length) / 2;
int[] left = null;


if (mid > 0) {
left = new int[mid];


for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
}


int[] right = new int[arr.length - left.length];


if ((arr.length - left.length) > 0) {
int j = 0;
for (int i = mid; i < arr.length; i++) {
right[j] = arr[i];
++j;
}
}


partition(left);
partition(right);
mergeToParent(left, right, arr);
}


}


public static void mergeToParent(int[] left, int[] right, int[] parent) {


int leftunPicked = 0;
int rightunPicked = 0;
int parentIndex = -1;


while (rightunPicked < right.length && leftunPicked < left.length) {


if (left[leftunPicked] < right[rightunPicked]) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;


} else {
count = count + left.length-leftunPicked;
if ((rightunPicked < right.length)) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}
}


}


while (leftunPicked < left.length) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;
}


while (rightunPicked < right.length) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}


}


}

我们可以比较输入数组和排序数组的另一种方法:- 这个暗黑破坏神的实现答案。虽然这不应该是首选的方法，因为从数组或列表中删除 n 个元素是 log (n ^ 2)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;




public class TestInversion {


public static void main(String[] args) {
        

Integer [] arr1 = {6, 9, 1, 14, 8, 12, 3, 2};
        

List<Integer> arr = new ArrayList(Arrays.asList(arr1));
List<Integer> sortArr = new ArrayList<Integer>();
        

for(int i=0;i<arr.size();i++){
sortArr.add(arr.get(i));
         

}
        

            

Collections.sort(sortArr);
        

int inversion = 0;
        

Iterator<Integer> iter = arr.iterator();
        

while(iter.hasNext()){
            

Integer el = (Integer)iter.next();
int index = sortArr.indexOf(el);
            

if(index+1 > 1){
inversion = inversion + ((index+1)-1);
}
            

//iter.remove();
sortArr.remove(el);
            

}
        

System.out.println("Inversions are "+inversion);
        

        

        



}




}

另一个 Python 解决方案

def inv_cnt(a):
n = len(a)
if n==1:
return a,0
left = a[0:n//2] # should be smaller
left,cnt1 = inv_cnt(left)
right = a[n//2:] # should be larger
right, cnt2 = inv_cnt(right)


cnt = 0
i_left = i_right = i_a = 0
while i_a < n:
if (i_right>=len(right)) or (i_left < len(left) and left[i_left] <= right[i_right]):
a[i_a] = left[i_left]
i_left += 1
else:
a[i_a] = right[i_right]
i_right += 1
if i_left < len(left):
cnt += len(left) - i_left
i_a += 1


return (a, (cnt1 + cnt2 + cnt))

Maximum number of inversions possible for a list of size n could be generalized by an expression:

maxPossibleInversions = (n * (n-1) ) / 2

因此，对于大小为 6的数组，最大可能的倒数将等于 15。

为了达到 n logn的复杂度，我们可以借助合并排序的反演算法。

以下是一般步骤:

• 将数组分成两部分
• 调用合并排序例程。如果左侧子数组中的元素大于右侧子数组中的元素，则生成 inversionCount += leftSubArray.length

就是这样！

这是一个简单的例子，我用 Javascript 做的:

var arr = [6,5,4,3,2,1]; // Sample input array


var inversionCount = 0;


function mergeSort(arr) {
if(arr.length == 1)
return arr;


if(arr.length > 1) {
let breakpoint = Math.ceil((arr.length/2));
// Left list starts with 0, breakpoint-1
let leftList = arr.slice(0,breakpoint);
// Right list starts with breakpoint, length-1
let rightList = arr.slice(breakpoint,arr.length);


// Make a recursive call
leftList = mergeSort(leftList);
rightList = mergeSort(rightList);


var a = merge(leftList,rightList);
return a;
}
}


function merge(leftList,rightList) {
let result = [];
while(leftList.length && rightList.length) {
/**
* The shift() method removes the first element from an array
* and returns that element. This method changes the length
* of the array.
*/
if(leftList[0] <= rightList[0]) {
result.push(leftList.shift());
}else{
inversionCount += leftList.length;
result.push(rightList.shift());
}
}


while(leftList.length)
result.push(leftList.shift());


while(rightList.length)
result.push(rightList.shift());


console.log(result);
return result;
}


mergeSort(arr);
console.log('Number of inversions: ' + inversionCount);

在 Swift 中使用合并排序计算数组中的倒数的实现:

注意，交换的数量增加了

nSwaps += mid + 1 - iL

(它是数组左侧的相对长度减去左侧当前元素的索引)

... 因为这是数组右边的元素必须跳过的元素数(反转的数目 #) ，以便进行排序。

func merge(arr: inout [Int], arr2: inout [Int], low: Int, mid: Int, high: Int) -> Int {
var nSwaps = 0;


var i = low;
var iL = low;
var iR = mid + 1;


while iL <= mid && iR <= high {
if arr2[iL] <= arr2[iR] {
arr[i] = arr2[iL]
iL += 1
i += 1
} else {
arr[i] = arr2[iR]
nSwaps += mid + 1 - iL
iR += 1
i += 1
}
}


while iL <= mid {
arr[i] = arr2[iL]
iL += 1
i += 1
}


while iR <= high {
arr[i] = arr2[iR]
iR += 1
i += 1
}


return nSwaps
}


func mergeSort(arr: inout [Int]) -> Int {
var arr2 = arr
let nSwaps = mergeSort(arr: &arr, arr2: &arr2, low: 0, high: arr.count-1)
return nSwaps
}


func mergeSort(arr: inout [Int], arr2: inout [Int], low: Int, high: Int) -> Int {


if low >= high {
return 0
}


let mid = low + ((high - low) / 2)


var nSwaps = 0;
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: low, high: mid)
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: mid+1, high: high)
nSwaps += merge(arr: &arr, arr2: &arr2, low: low, mid: mid, high: high)


return nSwaps
}


var arrayToSort: [Int] = [2, 1, 3, 1, 2]
let nSwaps = mergeSort(arr: &arrayToSort)


print(arrayToSort) // [1, 1, 2, 2, 3]
print(nSwaps) // 4

这个答案的主要目的是比较这里找到的各种 Python 版本的速度，但是我也有自己的一些贡献。(FWIW，我是在执行重复搜索时发现这个问题的)。

在 CPython 中实现的算法的相对执行速度可能不同于对算法的简单分析和对其他语言的经验所期望的速度。这是因为 Python 提供了许多用 C 语言实现的强大函数和方法，这些函数和方法对列表和其他集合的操作速度接近完全编译语言的速度，所以这些操作比用 Python 代码“手动”实现的等效算法运行速度快得多。

利用这些工具的代码往往比理论上更优秀的算法性能更好，后者试图在集合的各个项上使用 Python 操作来完成所有事情。当然，正在处理的数据的实际数量也会对此产生影响。但是对于中等数量的数据，使用以 C 语言速度运行的 O (n2)算法的代码可以轻松击败使用单个 Python 操作完成大部分工作的 O (n log n)算法。

Many of the posted answers to this inversion counting question use an algorithm based on mergesort. Theoretically, this is a good approach, unless the array size is very small. But Python's built-in TimSort (a hybrid stable sorting algorithm, derived from merge sort and insertion sort) runs at C speed, and a mergesort coded by hand in Python cannot hope to compete with it for speed.

其中一个更有趣的解决方案，在 尼克拉斯 B 发布的答案中，使用内置排序来确定数组项的排序，使用 二叉索引树(又名 Fenwick 树)来存储计算反转计数所需的累积总和。在试图理解这个数据结构和尼克拉斯的算法的过程中，我写了一些我自己的变体(张贴在下面)。但是我也发现，对于中等大小的列表，使用 Python 内置的 sum函数实际上是 再快点，而不是可爱的 Fenwick 树。

def count_inversions(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total

最终，当列表大小达到500左右时，在 for循环中调用 sum的 O (n2)方面出现了问题，性能开始急剧下降。

合并排序不是唯一的 O (nlogn)排序，还可以利用其他几种排序来执行反转计数。普拉萨德克的回答使用二叉树排序，但他的代码似乎是在 C + + 或其派生物之一。所以我添加了一个 Python 版本。我最初使用一个类来实现树节点，但是发现 dict 明显更快。我最终使用了 list，它甚至更快，尽管它确实使代码的可读性降低了一些。

Treesort 的一个好处是它比合并排序更容易迭代实现。Python 不会优化递归，而且它有递归深度限制(尽管如果 真的需要的话可以增加)。当然，Python 函数调用相对较慢，因此当您试图优化速度时，最好避免函数调用。

Another O(nlogn) sort is the venerable radix sort. It's big advantage is that it doesn't compare keys to each other. It's disadvantage is that it works best on contiguous sequences of integers, ideally a permutation of integers in range(b**m) where b is usually 2. I added a few versions based on radix sort after attempting to read 反演计数、离线正交范围计数及相关问题 which is linked in 计算排列中的“倒置”次数.

为了有效地使用基数排序来计算长度为 n 的一般序列 seq中的倒数，我们可以创建一个 range(n)的排列，它具有与 seq相同的倒数次数。我们可以通过 TimSort 在(最坏的情况下) O (nlogn)时间内做到这一点。诀窍是通过对 seq排序来置换 seq的索引。用一个小例子更容易解释这一点。

seq = [15, 14, 11, 12, 10, 13]
b = [t[::-1] for t in enumerate(seq)]
print(b)
b.sort()
print(b)

输出

[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)]
[(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]

By sorting the (value, index) pairs of seq we have permuted the indices of seq with the same number of swaps that are required to put seq into its original order from its sorted order. We can create that permutation by sorting range(n) with a suitable key function:

print(sorted(range(len(seq)), key=lambda k: seq[k]))

输出

[4, 2, 3, 5, 1, 0]

我们可以通过使用 seq的 .__getitem__方法来避免 lambda:

sorted(range(len(seq)), key=seq.__getitem__)

This is only slightly faster, but we're looking for all the speed enhancements we can get. ;)

下面的代码对这个页面上所有现有的 Python 算法进行 timeit测试，加上我自己的一些测试: 几个蛮力 O (n2)版本，Niklas B 算法的一些变体，当然还有一个基于合并排序(我写的时候没有参考现有的答案)。它还有基于列表的 treesort 代码，这些代码大致来源于 prasadvk 的代码，以及各种基于基数排序的函数，有些使用与合并排序方法类似的策略，有些使用 sum或 Fenwick 树。

该程序测量一系列随机整数列表上每个函数的执行时间; 它还可以验证每个函数给出的结果与其他函数相同，并且它不修改输入列表。

每个 timeit调用给出一个包含3个结果的向量，我对它们进行排序。这里要看的主要值是最小值，其他值只是表明最小值的可靠程度，正如 timeit模块文件中的注释所讨论的。

不幸的是，这个程序的输出太大，不能包括在这个答案中，所以我把它发布在 它自己的(社区维基)答案。

输出来自在我那台古老的32位单核2GHz 机器上运行的3次，这台机器在一个老的 Debian 衍生发行版上运行 Python 3.6.0。YMMV.在测试期间，我关闭了我的 Web 浏览器，断开了与路由器的连接，以尽量减少其他任务对 CPU 的影响。

第一次运行测试列表大小从5到320的所有函数，循环大小从4096到64(当列表大小加倍时，循环大小减半)。用于构造每个列表的随机池的大小是列表本身的一半，因此我们很可能得到重复的 很多。有些倒数计数算法对重复数据更为敏感。

第二次运行使用更大的列表: 640到10240，并且固定的循环大小为8。为了节省时间，它从测试中消除了几个最慢的函数。我的强制 O (n2)函数在这些大小下只是 方式太慢了，正如前面提到的，我使用 sum的代码在小到中等的列表上表现得非常好，只是无法跟上大列表的速度。

最后一次运行涵盖了从20480到655360的列表大小，以及具有8个最快函数的4个固定循环大小。对于40,000左右的列表大小，Tim Babych 的代码是明显的赢家。干得好，蒂姆！尼克拉斯 B 的代码也是一个很好的全方位执行器，尽管它在较小的列表中被击败。基于二分法的“ python”代码也做得相当不错，尽管它看起来有点慢，因为有大量重复的列表，这可能是因为它使用线性 while循环来跨越欺骗。

然而，对于非常大的列表大小，基于二分法的算法不能与真正的 O (nlogn)算法竞争。

#!/usr/bin/env python3


''' Test speeds of various ways of counting inversions in a list


The inversion count is a measure of how sorted an array is.
A pair of items in a are inverted if i < j but a[j] > a[i]


See https://stackoverflow.com/questions/337664/counting-inversions-in-an-array


This program contains code by the following authors:
mkso
Niklas B
B. M.
Tim Babych
python
Zhe Hu
prasadvk
noman pouigt
PM 2Ring


Timing and verification code by PM 2Ring
Collated 2017.12.16
Updated 2017.12.21
'''


from timeit import Timer
from random import seed, randrange
from bisect import bisect, insort_left


seed('A random seed string')


# Merge sort version by mkso
def count_inversion_mkso(lst):
return merge_count_inversion(lst)[1]


def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = len(lst) // 2
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)


def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Using a Binary Indexed Tree, aka a Fenwick tree, by Niklas B.
def count_inversions_NiklasB(a):
res = 0
counts = [0] * (len(a) + 1)
rank = {v: i for i, v in enumerate(sorted(a), 1)}
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by B.M
# Modified by PM 2Ring to deal with the global counter
bm_count = 0


def merge_count_BM(seq):
global bm_count
bm_count = 0
sort_bm(seq)
return bm_count


def merge_bm(l1,l2):
global bm_count
l = []
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
bm_count += len(l2)
l.reverse()
return l1 + l2 + l


def sort_bm(l):
t = len(l) // 2
return merge_bm(sort_bm(l[:t]), sort_bm(l[t:])) if t > 0 else l


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by Tim Babych
def solution_TimBabych(A):
sorted_left = []
res = 0
for i in range(1, len(A)):
insort_left(sorted_left, A[i-1])
# i is also the length of sorted_left
res += (i - bisect(sorted_left, A[i]))
return res


# Slightly faster, except for very small lists
def solutionE_TimBabych(A):
res = 0
sorted_left = []
for i, u in enumerate(A):
# i is also the length of sorted_left
res += (i - bisect(sorted_left, u))
insort_left(sorted_left, u)
return res


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by "python"
def solution_python(A):
B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch_python(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1
inversion_count += j
B.pop(j)
return inversion_count


def binarySearch_python(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by Zhe Hu
def inv_cnt_ZheHu(a):
_, count = inv_cnt(a.copy())
return count


def inv_cnt(a):
n = len(a)
if n==1:
return a, 0
left = a[0:n//2] # should be smaller
left, cnt1 = inv_cnt(left)
right = a[n//2:] # should be larger
right, cnt2 = inv_cnt(right)


cnt = 0
i_left = i_right = i_a = 0
while i_a < n:
if (i_right>=len(right)) or (i_left < len(left)
and left[i_left] <= right[i_right]):
a[i_a] = left[i_left]
i_left += 1
else:
a[i_a] = right[i_right]
i_right += 1
if i_left < len(left):
cnt += len(left) - i_left
i_a += 1
return (a, cnt1 + cnt2 + cnt)


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by noman pouigt
# From https://stackoverflow.com/q/47830098
def reversePairs_nomanpouigt(nums):
def merge(left, right):
if not left or not right:
return (0, left + right)
#if everything in left is less than right
if left[len(left)-1] < right[0]:
return (0, left + right)
else:
left_idx, right_idx, count = 0, 0, 0
merged_output = []


# check for condition before we merge it
while left_idx < len(left) and right_idx < len(right):
#if left[left_idx] > 2 * right[right_idx]:
if left[left_idx] > right[right_idx]:
count += len(left) - left_idx
right_idx += 1
else:
left_idx += 1


#merging the sorted list
left_idx, right_idx = 0, 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] > right[right_idx]:
merged_output += [right[right_idx]]
right_idx += 1
else:
merged_output += [left[left_idx]]
left_idx += 1
if left_idx == len(left):
merged_output += right[right_idx:]
else:
merged_output += left[left_idx:]
return (count, merged_output)


def partition(nums):
count = 0
if len(nums) == 1 or not nums:
return (0, nums)
pivot = len(nums)//2
left_count, l = partition(nums[:pivot])
right_count, r = partition(nums[pivot:])
temp_count, temp_list = merge(l, r)
return (temp_count + left_count + right_count, temp_list)
return partition(nums)[0]


# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# PM 2Ring
def merge_PM2R(seq):
seq, count = merge_sort_count_PM2R(seq)
return count


def merge_sort_count_PM2R(seq):
mid = len(seq) // 2
if mid == 0:
return seq, 0
left, left_total = merge_sort_count_PM2R(seq[:mid])
right, right_total = merge_sort_count_PM2R(seq[mid:])
total = left_total + right_total
result = []
i = j = 0
left_len, right_len = len(left), len(right)
while i < left_len and j < right_len:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
total += left_len - i
result.extend(left[i:])
result.extend(right[j:])
return result, total


def rank_sum_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total


# Fenwick tree functions adapted from C code on Wikipedia
def fen_sum(tree, i):
''' Return the sum of the first i elements, 0 through i-1 '''
total = 0
while i:
total += tree[i-1]
i -= i & -i
return total


def fen_add(tree, delta, i):
''' Add delta to element i and thus
to fen_sum(tree, j) for all j > i
'''
size = len(tree)
while i < size:
tree[i] += delta
i += (i+1) & -(i+1)


def fenwick_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += fen_sum(counts, i)
fen_add(counts, 1, i)
return total


def fenwick_inline_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total


def bruteforce_loops_PM2R(a):
total = 0
for i in range(1, len(a)):
u = a[i]
for j in range(i):
if a[j] > u:
total += 1
return total


def bruteforce_sum_PM2R(a):
return sum(1 for i in range(1, len(a)) for j in range(i) if a[j] > a[i])


# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackoverflow.com/a/16056139
def ltree_count_PM2R(a):
total, root = 0, None
for u in a:
# Store data in a list-based tree structure
# [data, count, left_child, right_child]
p = [u, 0, None, None]
if root is None:
root = p
continue
q = root
while True:
if p[0] < q[0]:
total += 1 + q[1]
child = 2
else:
q[1] += 1
child = 3
if q[child]:
q = q[child]
else:
q[child] = p
break
return total


# Counting based on radix sort, recursive version
def radix_partition_rec(a, L):
if len(a) < 2:
return 0
if len(a) == 2:
return a[1] < a[0]
left, right = [], []
count = 0
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
L >>= 1
if L:
count += radix_partition_rec(left, L) + radix_partition_rec(right, L)
return count


# The following functions determine swaps using a permutation of
# range(len(a)) that has the same inversion count as `a`. We can create
# this permutation with `sorted(range(len(a)), key=lambda k: a[k])`
# but `sorted(range(len(a)), key=a.__getitem__)` is a little faster.


# Counting based on radix sort, iterative version
def radix_partition_iter(seq, L):
count = 0
parts = [seq]
while L and parts:
newparts = []
for a in parts:
if len(a) < 2:
continue
if len(a) == 2:
count += a[1] < a[0]
continue
left, right = [], []
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
if left:
newparts.append(left)
if right:
newparts.append(right)
parts = newparts
L >>= 1
return count


def perm_radixR_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_rec(b, 1 << n)


def perm_radixI_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_iter(b, 1 << n)


# Plain sum of the counts of the permutation
def perm_sum_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
total += sum(counts[:i])
counts[i] = 1
return total


# Fenwick sum of the counts of the permutation
def perm_fenwick_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total


# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# All the inversion-counting functions
funcs = (
solution_TimBabych,
solutionE_TimBabych,
solution_python,
count_inversion_mkso,
count_inversions_NiklasB,
merge_count_BM,
inv_cnt_ZheHu,
reversePairs_nomanpouigt,
fenwick_PM2R,
fenwick_inline_PM2R,
merge_PM2R,
rank_sum_PM2R,
bruteforce_loops_PM2R,
bruteforce_sum_PM2R,
ltree_count_PM2R,
perm_radixR_PM2R,
perm_radixI_PM2R,
perm_sum_PM2R,
perm_fenwick_PM2R,
)


def time_test(seq, loops, verify=False):
orig = seq
timings = []
for func in funcs:
seq = orig.copy()
value = func(seq) if verify else None
t = Timer(lambda: func(seq))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__, value))
assert seq==orig, 'Sequence altered by {}!'.format(func.__name__)
first = timings[0][-1]
timings.sort()
for result, name, value in timings:
result = ', '.join([format(u, '.5f') for u in result])
print('{:24} : {}'.format(name, result))


if verify:
# Check that all results are identical
bad = ['%s: %d' % (name, value)
for _, name, value in timings if value != first]
if bad:
print('ERROR. Value: {}, bad: {}'.format(first, ', '.join(bad)))
else:
print('Value: {}'.format(first))
print()


#Run the tests
size, loops = 5, 1 << 12
verify = True
for _ in range(7):
hi = size // 2
print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
seq = [randrange(hi) for _ in range(size)]
time_test(seq, loops, verify)
loops >>= 1
size <<= 1


#size, loops = 640, 8
#verify = False
#for _ in range(5):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1


#size, loops = 163840, 4
#verify = False
#for _ in range(3):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1

有关输出，请参阅此处

这个答案包含由我的 主要答案中的代码生成的 timeit测试的结果。详情请参阅答案！

count_inversions speed test results


Size = 5, hi = 2, 4096 loops
ltree_count_PM2R         : 0.04871, 0.04872, 0.04876
bruteforce_loops_PM2R    : 0.05696, 0.05700, 0.05776
solution_TimBabych       : 0.05760, 0.05822, 0.05943
solutionE_TimBabych      : 0.06642, 0.06704, 0.06760
bruteforce_sum_PM2R      : 0.07523, 0.07545, 0.07563
perm_sum_PM2R            : 0.09873, 0.09875, 0.09935
rank_sum_PM2R            : 0.10449, 0.10463, 0.10468
solution_python          : 0.13034, 0.13061, 0.13221
fenwick_inline_PM2R      : 0.14323, 0.14610, 0.18802
perm_radixR_PM2R         : 0.15146, 0.15203, 0.15235
merge_count_BM           : 0.16179, 0.16267, 0.16467
perm_radixI_PM2R         : 0.16200, 0.16202, 0.16768
perm_fenwick_PM2R        : 0.16887, 0.16920, 0.17075
merge_PM2R               : 0.18262, 0.18271, 0.18418
count_inversions_NiklasB : 0.19183, 0.19279, 0.20388
count_inversion_mkso     : 0.20060, 0.20141, 0.20398
inv_cnt_ZheHu            : 0.20815, 0.20841, 0.20906
fenwick_PM2R             : 0.22109, 0.22137, 0.22379
reversePairs_nomanpouigt : 0.29620, 0.29689, 0.30293
Value: 5


Size = 10, hi = 5, 2048 loops
solution_TimBabych       : 0.05954, 0.05989, 0.05991
solutionE_TimBabych      : 0.05970, 0.05972, 0.05998
perm_sum_PM2R            : 0.07517, 0.07519, 0.07520
ltree_count_PM2R         : 0.07672, 0.07677, 0.07684
bruteforce_loops_PM2R    : 0.07719, 0.07724, 0.07817
rank_sum_PM2R            : 0.08587, 0.08823, 0.08864
bruteforce_sum_PM2R      : 0.09470, 0.09472, 0.09484
solution_python          : 0.13126, 0.13154, 0.13185
perm_radixR_PM2R         : 0.14239, 0.14320, 0.14474
perm_radixI_PM2R         : 0.14632, 0.14669, 0.14679
fenwick_inline_PM2R      : 0.16796, 0.16831, 0.17030
perm_fenwick_PM2R        : 0.18189, 0.18212, 0.18638
merge_count_BM           : 0.19816, 0.19870, 0.19948
count_inversions_NiklasB : 0.21807, 0.22031, 0.22215
merge_PM2R               : 0.22037, 0.22048, 0.26106
fenwick_PM2R             : 0.24290, 0.24314, 0.24744
count_inversion_mkso     : 0.24895, 0.24899, 0.25205
inv_cnt_ZheHu            : 0.26253, 0.26259, 0.26590
reversePairs_nomanpouigt : 0.35711, 0.35762, 0.35973
Value: 20


Size = 20, hi = 10, 1024 loops
solutionE_TimBabych      : 0.05687, 0.05696, 0.05720
solution_TimBabych       : 0.06126, 0.06151, 0.06168
perm_sum_PM2R            : 0.06875, 0.06906, 0.07054
rank_sum_PM2R            : 0.07988, 0.07995, 0.08002
ltree_count_PM2R         : 0.11232, 0.11239, 0.11257
bruteforce_loops_PM2R    : 0.12553, 0.12584, 0.12592
solution_python          : 0.13472, 0.13540, 0.13694
bruteforce_sum_PM2R      : 0.15820, 0.15849, 0.16021
perm_radixI_PM2R         : 0.17101, 0.17148, 0.17229
perm_radixR_PM2R         : 0.17891, 0.18087, 0.18366
perm_fenwick_PM2R        : 0.20554, 0.20708, 0.21412
fenwick_inline_PM2R      : 0.21161, 0.21163, 0.22047
merge_count_BM           : 0.24125, 0.24261, 0.24565
count_inversions_NiklasB : 0.25712, 0.25754, 0.25778
merge_PM2R               : 0.26477, 0.26566, 0.31297
fenwick_PM2R             : 0.28178, 0.28216, 0.29069
count_inversion_mkso     : 0.30286, 0.30290, 0.30652
inv_cnt_ZheHu            : 0.32024, 0.32041, 0.32447
reversePairs_nomanpouigt : 0.45812, 0.45822, 0.46172
Value: 98


Size = 40, hi = 20, 512 loops
solutionE_TimBabych      : 0.05784, 0.05787, 0.05958
solution_TimBabych       : 0.06452, 0.06475, 0.06479
perm_sum_PM2R            : 0.07254, 0.07261, 0.07263
rank_sum_PM2R            : 0.08537, 0.08540, 0.08572
ltree_count_PM2R         : 0.11744, 0.11749, 0.11792
solution_python          : 0.14262, 0.14285, 0.14465
perm_radixI_PM2R         : 0.18774, 0.18776, 0.18922
perm_radixR_PM2R         : 0.19425, 0.19435, 0.19609
bruteforce_loops_PM2R    : 0.21500, 0.21511, 0.21686
perm_fenwick_PM2R        : 0.23338, 0.23375, 0.23674
fenwick_inline_PM2R      : 0.24947, 0.24958, 0.25189
bruteforce_sum_PM2R      : 0.27627, 0.27646, 0.28041
merge_count_BM           : 0.28059, 0.28128, 0.28294
count_inversions_NiklasB : 0.28557, 0.28759, 0.29022
merge_PM2R               : 0.29886, 0.29928, 0.30317
fenwick_PM2R             : 0.30241, 0.30259, 0.35237
count_inversion_mkso     : 0.34252, 0.34356, 0.34441
inv_cnt_ZheHu            : 0.37468, 0.37569, 0.37847
reversePairs_nomanpouigt : 0.50725, 0.50770, 0.50943
Value: 369


Size = 80, hi = 40, 256 loops
solutionE_TimBabych      : 0.06339, 0.06373, 0.06513
solution_TimBabych       : 0.06984, 0.06994, 0.07009
perm_sum_PM2R            : 0.09171, 0.09172, 0.09186
rank_sum_PM2R            : 0.10468, 0.10474, 0.10500
ltree_count_PM2R         : 0.14416, 0.15187, 0.18541
solution_python          : 0.17415, 0.17423, 0.17451
perm_radixI_PM2R         : 0.20676, 0.20681, 0.20936
perm_radixR_PM2R         : 0.21671, 0.21695, 0.21736
perm_fenwick_PM2R        : 0.26197, 0.26252, 0.26264
fenwick_inline_PM2R      : 0.28111, 0.28249, 0.28382
count_inversions_NiklasB : 0.31746, 0.32448, 0.32451
merge_count_BM           : 0.31964, 0.33842, 0.35276
merge_PM2R               : 0.32890, 0.32941, 0.33322
fenwick_PM2R             : 0.34355, 0.34377, 0.34873
count_inversion_mkso     : 0.37689, 0.37698, 0.38079
inv_cnt_ZheHu            : 0.42923, 0.42941, 0.43249
bruteforce_loops_PM2R    : 0.43544, 0.43601, 0.43902
bruteforce_sum_PM2R      : 0.52106, 0.52160, 0.52531
reversePairs_nomanpouigt : 0.57805, 0.58156, 0.58252
Value: 1467


Size = 160, hi = 80, 128 loops
solutionE_TimBabych      : 0.06766, 0.06784, 0.06963
solution_TimBabych       : 0.07433, 0.07489, 0.07516
perm_sum_PM2R            : 0.13143, 0.13175, 0.13179
rank_sum_PM2R            : 0.14428, 0.14440, 0.14922
solution_python          : 0.20072, 0.20076, 0.20084
ltree_count_PM2R         : 0.20314, 0.20583, 0.24776
perm_radixI_PM2R         : 0.23061, 0.23078, 0.23525
perm_radixR_PM2R         : 0.23894, 0.23915, 0.24234
perm_fenwick_PM2R        : 0.30984, 0.31181, 0.31503
fenwick_inline_PM2R      : 0.31933, 0.32680, 0.32722
merge_count_BM           : 0.36003, 0.36387, 0.36409
count_inversions_NiklasB : 0.36796, 0.36814, 0.37106
merge_PM2R               : 0.36847, 0.36848, 0.37127
fenwick_PM2R             : 0.37833, 0.37847, 0.38095
count_inversion_mkso     : 0.42746, 0.42747, 0.43184
inv_cnt_ZheHu            : 0.48969, 0.48974, 0.49293
reversePairs_nomanpouigt : 0.67791, 0.68157, 0.72420
bruteforce_loops_PM2R    : 0.82816, 0.83175, 0.83282
bruteforce_sum_PM2R      : 1.03322, 1.03378, 1.03562
Value: 6194


Size = 320, hi = 160, 64 loops
solutionE_TimBabych      : 0.07467, 0.07470, 0.07483
solution_TimBabych       : 0.08036, 0.08066, 0.08077
perm_sum_PM2R            : 0.21142, 0.21201, 0.25766
solution_python          : 0.22410, 0.22644, 0.22897
rank_sum_PM2R            : 0.22820, 0.22851, 0.22877
ltree_count_PM2R         : 0.24424, 0.24595, 0.24645
perm_radixI_PM2R         : 0.25690, 0.25710, 0.26191
perm_radixR_PM2R         : 0.26501, 0.26504, 0.26729
perm_fenwick_PM2R        : 0.33483, 0.33507, 0.33845
fenwick_inline_PM2R      : 0.34413, 0.34484, 0.35153
merge_count_BM           : 0.39875, 0.39919, 0.40302
fenwick_PM2R             : 0.40434, 0.40439, 0.40845
merge_PM2R               : 0.40814, 0.41531, 0.51417
count_inversions_NiklasB : 0.41681, 0.42009, 0.42128
count_inversion_mkso     : 0.47132, 0.47192, 0.47385
inv_cnt_ZheHu            : 0.54468, 0.54750, 0.54893
reversePairs_nomanpouigt : 0.76164, 0.76389, 0.80357
bruteforce_loops_PM2R    : 1.59125, 1.60430, 1.64131
bruteforce_sum_PM2R      : 2.03734, 2.03834, 2.03975
Value: 24959


Run 2


Size = 640, hi = 320, 8 loops
solutionE_TimBabych      : 0.04135, 0.04374, 0.04575
ltree_count_PM2R         : 0.06738, 0.06758, 0.06874
perm_radixI_PM2R         : 0.06928, 0.06943, 0.07019
fenwick_inline_PM2R      : 0.07850, 0.07856, 0.08059
perm_fenwick_PM2R        : 0.08151, 0.08162, 0.08170
perm_sum_PM2R            : 0.09122, 0.09133, 0.09221
rank_sum_PM2R            : 0.09549, 0.09603, 0.11270
merge_count_BM           : 0.10733, 0.10807, 0.11032
count_inversions_NiklasB : 0.12460, 0.19865, 0.20205
solution_python          : 0.13514, 0.13585, 0.13814


Size = 1280, hi = 640, 8 loops
solutionE_TimBabych      : 0.04714, 0.04742, 0.04752
perm_radixI_PM2R         : 0.15325, 0.15388, 0.15525
solution_python          : 0.15709, 0.15715, 0.16076
fenwick_inline_PM2R      : 0.16048, 0.16160, 0.16403
ltree_count_PM2R         : 0.16213, 0.16238, 0.16428
perm_fenwick_PM2R        : 0.16408, 0.16416, 0.16449
count_inversions_NiklasB : 0.19755, 0.19833, 0.19897
merge_count_BM           : 0.23736, 0.23793, 0.23912
perm_sum_PM2R            : 0.32946, 0.32969, 0.33277
rank_sum_PM2R            : 0.34637, 0.34756, 0.34858


Size = 2560, hi = 1280, 8 loops
solutionE_TimBabych      : 0.10898, 0.11005, 0.11025
perm_radixI_PM2R         : 0.33345, 0.33352, 0.37656
ltree_count_PM2R         : 0.34670, 0.34786, 0.34833
perm_fenwick_PM2R        : 0.34816, 0.34879, 0.35214
fenwick_inline_PM2R      : 0.36196, 0.36455, 0.36741
solution_python          : 0.36498, 0.36637, 0.40887
count_inversions_NiklasB : 0.42274, 0.42745, 0.42995
merge_count_BM           : 0.50799, 0.50898, 0.50917
perm_sum_PM2R            : 1.27773, 1.27897, 1.27951
rank_sum_PM2R            : 1.29728, 1.30389, 1.30448


Size = 5120, hi = 2560, 8 loops
solutionE_TimBabych      : 0.26914, 0.26993, 0.27253
perm_radixI_PM2R         : 0.71416, 0.71634, 0.71753
perm_fenwick_PM2R        : 0.71976, 0.72078, 0.72078
fenwick_inline_PM2R      : 0.72776, 0.72804, 0.73143
ltree_count_PM2R         : 0.81972, 0.82043, 0.82290
solution_python          : 0.83714, 0.83756, 0.83962
count_inversions_NiklasB : 0.87282, 0.87395, 0.92087
merge_count_BM           : 1.09496, 1.09584, 1.10207
rank_sum_PM2R            : 5.02564, 5.06277, 5.06666
perm_sum_PM2R            : 5.09088, 5.12999, 5.13512


Size = 10240, hi = 5120, 8 loops
solutionE_TimBabych      : 0.71556, 0.71718, 0.72201
perm_radixI_PM2R         : 1.54785, 1.55096, 1.55515
perm_fenwick_PM2R        : 1.55103, 1.55353, 1.59298
fenwick_inline_PM2R      : 1.57118, 1.57240, 1.57271
ltree_count_PM2R         : 1.76240, 1.76247, 1.80944
count_inversions_NiklasB : 1.86543, 1.86851, 1.87208
solution_python          : 2.01490, 2.01519, 2.06423
merge_count_BM           : 2.35215, 2.35301, 2.40023
rank_sum_PM2R            : 20.07048, 20.08399, 20.13200
perm_sum_PM2R            : 20.10187, 20.12551, 20.12683


Run 3
Size = 20480, hi = 10240, 4 loops
solutionE_TimBabych      : 1.07636, 1.08243, 1.09569
perm_radixI_PM2R         : 1.59579, 1.60519, 1.61785
perm_fenwick_PM2R        : 1.66885, 1.68549, 1.71109
fenwick_inline_PM2R      : 1.72073, 1.72752, 1.77217
ltree_count_PM2R         : 1.96900, 1.97820, 2.02578
count_inversions_NiklasB : 2.03257, 2.05005, 2.18548
merge_count_BM           : 2.46768, 2.47377, 2.52133
solution_python          : 2.49833, 2.50179, 3.79819


Size = 40960, hi = 20480, 4 loops
solutionE_TimBabych      : 3.51733, 3.52008, 3.56996
perm_radixI_PM2R         : 3.51736, 3.52365, 3.56459
perm_fenwick_PM2R        : 3.76097, 3.80900, 3.87974
fenwick_inline_PM2R      : 3.95099, 3.96300, 3.99748
ltree_count_PM2R         : 4.49866, 4.54652, 5.39716
count_inversions_NiklasB : 4.61851, 4.64303, 4.73026
merge_count_BM           : 5.31945, 5.35378, 5.35951
solution_python          : 6.78756, 6.82911, 6.98217


Size = 81920, hi = 40960, 4 loops
perm_radixI_PM2R         : 7.68723, 7.71986, 7.72135
perm_fenwick_PM2R        : 8.52404, 8.53349, 8.53710
fenwick_inline_PM2R      : 8.97082, 8.97561, 8.98347
ltree_count_PM2R         : 10.01142, 10.01426, 10.03216
count_inversions_NiklasB : 10.60807, 10.62424, 10.70425
merge_count_BM           : 11.42149, 11.42342, 11.47003
solutionE_TimBabych      : 12.83390, 12.83485, 12.89747
solution_python          : 19.66092, 19.67067, 20.72204


Size = 163840, hi = 81920, 4 loops
perm_radixI_PM2R         : 17.14153, 17.16885, 17.22240
perm_fenwick_PM2R        : 19.25944, 19.27844, 20.27568
fenwick_inline_PM2R      : 19.78221, 19.80219, 19.80766
ltree_count_PM2R         : 22.42240, 22.43259, 22.48837
count_inversions_NiklasB : 22.97341, 23.01516, 23.98052
merge_count_BM           : 24.42683, 24.48559, 24.51488
solutionE_TimBabych      : 60.96006, 61.20145, 63.71835
solution_python          : 73.75132, 73.79854, 73.95874


Size = 327680, hi = 163840, 4 loops
perm_radixI_PM2R         : 36.56715, 36.60221, 37.05071
perm_fenwick_PM2R        : 42.21616, 42.21838, 42.26053
fenwick_inline_PM2R      : 43.04987, 43.09075, 43.13287
ltree_count_PM2R         : 49.87400, 50.08509, 50.69292
count_inversions_NiklasB : 50.74591, 50.75012, 50.75551
merge_count_BM           : 52.37284, 52.51491, 53.43003
solutionE_TimBabych      : 373.67198, 377.03341, 377.42360
solution_python          : 411.69178, 411.92691, 412.83856


Size = 655360, hi = 327680, 4 loops
perm_radixI_PM2R         : 78.51927, 78.66327, 79.46325
perm_fenwick_PM2R        : 90.64711, 90.80328, 91.76126
fenwick_inline_PM2R      : 93.32482, 93.39086, 94.28880
count_inversions_NiklasB : 107.74393, 107.80036, 108.71443
ltree_count_PM2R         : 109.11328, 109.23592, 110.18247
merge_count_BM           : 111.05633, 111.07840, 112.05861
solutionE_TimBabych      : 1830.46443, 1836.39960, 1849.53918
solution_python          : 1911.03692, 1912.04484, 1914.69786

大多数答案是基于 MergeSort，但它不是唯一的方法来解决这是在 O(nlogn)

I'll discuss a few approaches.

1. 使用 Balanced Binary Search Tree

   • 增强树以存储重复元素的频率。
   • 其思想是，当从树根遍历到叶子以插入时，继续计算更大的节点。

就像这样。

Node *insert(Node* root, int data, int& count){
if(!root) return new Node(data);
if(root->data == data){
root->freq++;
count += getSize(root->right);
}
else if(root->data > data){
count += getSize(root->right) + root->freq;
root->left = insert(root->left, data, count);
}
else root->right = insert(root->right, data, count);
return balance(root);
}


int getCount(int *a, int n){
int c = 0;
Node *root = NULL;
for(auto i=0; i<n; i++) root = insert(root, a[i], c);
return c;
}

2. 使用 Binary Indexed Tree
   • 创建一个求和 BIT。
   • 从末尾开始循环，并开始查找更大元素的计数。

int getInversions(int[] a) {
int n = a.length, inversions = 0;
int[] bit = new int[n+1];
compress(a);
BIT b = new BIT();
for (int i=n-1; i>=0; i--) {
inversions += b.getSum(bit, a[i] - 1);
b.update(bit, n, a[i], 1);
}
return inversions;
}

3. 使用 Segment Tree
   • 创建一个求和段 Tree。
   • 从数组末尾进行循环，并在 [0, a[i]-1]和更新 a[i] with 1之间进行查询

int getInversions(int *a, int n) {
int N = n + 1, c = 0;
compress(a, n);
int tree[N<<1] = {0};
for (int i=n-1; i>=0; i--) {
c+= query(tree, N, 0, a[i] - 1);
update(tree, N, a[i], 1);
}
return c;
}

此外，当使用 BIT或 Segment-Tree的一个好主意是做 Coordinate compression

void compress(int *a, int n) {
int temp[n];
for (int i=0; i<n; i++) temp[i] = a[i];
sort(temp, temp+n);
for (int i=0; i<n; i++) a[i] = lower_bound(temp, temp+n, a[i]) - temp + 1;
}

C + + Θ (n lg n)解法与对的打印构成倒数计数。

int merge(vector<int>&nums , int low , int mid , int high){
int size1 = mid - low +1;
int size2= high - mid;
vector<int>left;
vector<int>right;
for(int i = 0  ; i < size1 ; ++i){
left.push_back(nums[low+i]);
}
for(int i = 0 ; i <size2 ; ++i){
right.push_back(nums[mid+i+1]);
}
left.push_back(INT_MAX);
right.push_back(INT_MAX);
int i = 0 ;
int j = 0;
int start  = low;
int inversion = 0 ;
while(i < size1 && j < size2){
if(left[i]<right[j]){
nums[start] = left[i];
start++;
i++;
}else{
for(int l = i ; l < size1; ++l){
cout<<"("<<left[l]<<","<<right[j]<<")"<<endl;
}
inversion += size1 - i;
nums[start] = right[j];
start++;
j++;
}
}
if(i == size1){
for(int c = j ; c< size2 ; ++c){
nums[start] = right[c];
start++;
}
}
if(j == size2){
for(int c =  i ; c< size1 ; ++c){
nums[start] = left[c];
start++;
}
}
return inversion;
}
int inversion_count(vector<int>& nums , int low , int high){
if(high>low){
int mid = low + (high-low)/2;
int left = inversion_count(nums,low,mid);
int right = inversion_count(nums,mid+1,high);
int inversion = merge(nums,low,mid,high) + left + right;
return inversion;
}
return 0 ;
}

解决方案一: 当有大量的数字时工作得很好

def countInversions(arr):
n = len(arr)
if n == 1:
return 0
n1 = n // 2
n2 = n - n1
arr1 = arr[:n1]
arr2 = arr[n1:]
# print(n1,'||',n1,'||',arr1,'||',arr2)
ans = countInversions(arr1) + countInversions(arr2)
print(ans)
i1 = 0
i2 = 0
for i in range(n):
# print(i1,n1,i2,n2)
if i1 < n1 and (i2 >= n2 or arr1[i1] <= arr2[i2]):
arr[i] = arr1[i1]
ans += i2
i1 += 1
elif i2 < n2:
arr[i] = arr2[i2]
i2 += 1
return ans

Solution Two.Simple solution.

def countInversions(arr):
count = 0
for i in range(len(arr)):
for j in range(i, len(arr)):
# print(arr[i:len(arr)])
if arr[i] > arr[j]:
print(arr[i], arr[j])
count += 1
print(count)