逆序数详解：线性代数-矩阵-相关的公式细解-疑难点汇总
Author：zhoulujun Date：
之前整理过：透析矩阵，由浅入深娓娓道来—高数-线性代数-矩阵
但是，关于矩阵里面的歪歪道道还是有不少不明觉厉
比如：逆序数
而这段时间，党的十九大轰轰烈烈召开（我等被代表屁民只是围观），但是，VPN莫名被强烈封杀，在 天朝找点偏学术性的文章 真不容易。
逆序数
有序集：设A为一个有n个数字的有序集（n>1），其中所有数字各不相同。
比如A={1,2,3}，那么A就是一个有续集。1,2,3从小到大排列就为 标准排列，那么B={3,2,1}就为逆序排列。B集合就是逆序集。
逆序对：逆序对：数列a[1],a[2],a[3]…中的任意两个数a[i],a[j] (i<j)，如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对。
逆序数：逆序数是逆序集的基数，它常用于量度排列或序列的已排序程度。当线性代数里面指一个数列中逆序对的总数——跟标准列相反序数的总和。
如数列 C=[ 3 5 4 8 2 6 9]，(5,4)是一个逆序对，同样还有(3,2),(5,2),(4,2)等等
那么如何求得一个数列的逆序数呢？
方法1：一个一个的数
最简单也是最容易想到的方法就是，对于数列中的每一个数a[i]，遍历数列中的数a[j](其中j<i),若a[i]<a[j],则逆序数加1，这样就能统计出该数列的逆序数总和
该方法的时间复杂度为O(n^2)，
方法2：归并的思想
有一种排序的方法是归并排序，归并排序的主要思想是将整个序列分成两部分，分别递归将这两部分排好序之后，再和并为一个有序的序列。参考：http://blog.csdn.net/dlengong/article/details/7594919
http://www.cnblogs.com/youxin/p/3352940.html
标准列是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. 计算排列的逆序数.
解：在排列中，
排在首位，故其逆序数为；
的前面比大的数只有个，故其逆序数为；
的前面没有比大的数，故其逆序数为；
的前面比大的数有个，故其逆序数为；
的前面比大的数有个，故其逆序数为.
于是排列的逆序数为
注： 一个排列的逆序数为排列中各个元素逆序数的总和，计算一排列的逆序数的常用方法是分别计算出排列中每个元素的逆序数，再求总和.
逆序数为奇数的排列称为奇排列，逆序数为偶数的排列称为偶排列.
转载本站文章《逆序数详解：线性代数-矩阵-相关的公式细解-疑难点汇总》,
请注明出处：https://www.zhoulujun.cn/html/theory/Mathematics/Algebra/8060.html