归并算法经典应用——求解逆序数

本文始发于个人公众号：TechFlow，原创不易，求个关注

在之前介绍线性代数行列式计算公式的时候，我们曾经介绍过逆序数：我们在列举出行列式的每一项之后，需要通过逆序数来确定这一项符号的正负性。如果有忘记的同学可以回到之前的文章当中复习一下：

线性代数行列式

如果忘记呢，问题也不大，这个概念比较简单，我想大家很快就能都搞清楚。

今天的这一篇文章，我想和大家聊聊逆序数的算法，也是一道非常经典的算法题，经常在各大公司的面试题当中出现。

我们先来回顾一下逆序数的定义，所谓逆序数指的是数组当中究竟存在多少组数对，使得排在前面的数大于排在后面的数。我们举个例子，假设当下有一个数组是: [1, 3, 2]。

对于数对(3, 2)来说，由于3排在2前面，并且3 > 2，那么就说明(3, 2)是一对逆序数对。整个数组当中所有逆序数对的个数就是逆序数。

我们从逆序数的定义当中不难发现，逆序数其实是用来衡量一个数组有序程度的一个指标。逆序数越大，说明这个数组递增性越差。如果逆序数为0，说明这个序列是严格递增的。如果一个长度为n的数组的逆序数是$C_n^2$，那么说明这个数组是严格递减的，此时逆序数最大。

那么，我们怎么快速地求解逆序数呢？

暴力解法

显然，这个问题可以暴力求解，我们只需要遍历所有的数对，然后判断是否构成逆序即可，最后累加一下所有逆序数对的个数就是最终的答案。

这个代码非常简单，只需要几行：

inverse = 0
for i in range(1, 10):