逆序数怎么算

逆序数的计算方法是，在一个数列中，若两个数前后位置颠倒，则称它们构成了一个逆序对。
而逆序数就是该数列中逆序对数量的总和。
1. 因为，如果一个数列中有多个逆序对，说明该数列的顺序性较差，这种情况通常被认为是无序的表现，因此逆序数越多，表明该数列的有序性越差。
2. 计算逆序数的方法比较直观简单，可以通过归并排序的方法，先将数组不断拆分成单个元素，再不断合并，进行排序的过程当中，统计已分组的数字间的逆序对个数，在合并时将数值较小的元素先加入新合并的数组中，以便计算逆序数的变化。

一个排列中所有逆序总数叫做这个排列的逆序数。

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

如数列 3 5 4 8 2 6 9

(5,4)是一个逆序对，同样还有(3,2),(5,2),(4,2)等等。

什么是逆序数：

跟标准列相反序数的总和

比如说

标准列是1 2 3 4 5

那么 5 4 3 2 1 的逆序数算法：

5之前没有数，记为0.

看第二个，4之前有一个5，在标准列中5在4的后面，所以记1个

类似的，第三个 3 之前有 4 5 都是在标准列中3的后面，所以记2个

同样的，2 之前有3个，1之前有4个

将这些数加起来就是逆序数=1+2+3+4=10

再举一个 2 4 3 1 5

4 之前有0个

3 之前有1个

1 之前有3个

5 之前有0个

所以逆序数就是1+3=4

逆序数的求法：

1.一个一个的数

最简单也是最容易想到的方法就是，对于数列中的每一个数a[i]，遍历数列中的数a[j](其中j<i),若a[i]<a[j],则逆序数加1，这样就能统计出该数列的逆序数总和

该方法的时间复杂度为O(n^2)

1. 逆序数

所谓逆序数，就是指一个序列S[i]，统计处于序列的每个数的比这个数大并且排在它前面的数的数目，然后对于所有数，把这个数目加起来求和就是了。

比如4 3 1 2

4第一个，所以数目为0

3的前面是4，大于3的数目为1

1的前面是4 3 ，大于1的数目为2

2的前面是4 3 1，大于2的数目为2

所以逆序数为1+2+2 = 5

求逆序数的两种方法

常规方法是按照逆序数的规则做，结果复杂度是O(n*n)，一般来说，有两种快速的求逆序数的方法

分别是归并排序和树状数组法

2. 归并排序

归并排序是源于分而治之思想，详细的过程可以查阅其他资料，总体思想是划分一半，各自排好序后将两个有序序列合并起来。

如何修改归并排序求逆序数?

首先我们假设两个有序序列a[i]和b[i]，当合并时：

由于a[i]已是有序，所以对于a[i]的各个元素来说，排在它前面且比它大的数目都是0

当b[i]中含有比a[i]小的元素时，我们必然将b[i]元素插到前面，那么就是说，在b[i]原先位置到该插的位置中，所有数都比b[i]大且排在它前面

所以这是b[i]的数目为新插入位置newPos - 原来位置oldPos