《剑指offer》：数组中的逆序对——算法讲解
例如在数组{7,5,6,4} 中，一共存在5个逆序对，分别是（7,6）、（7,5）、（7,4）、（6,4）和（5,4）。
方法一：顺序扫描整个数组。
每到一个数就从头到尾计算其他数到这里的逆序对数，复杂度是O(n2)，由最上的输入描述，复杂度是不可忍受的
方法二：先比较两个相邻的数字
来自《剑指offer》第二版
- 每扫描到一个数字的时候，不能拿它和后面的每一个数字进行比较
- 考虑先比较两个相邻的数字（如下图）
- (a)(b)(c)三步都很容易理解，(c)统计逆序对也很容易【记得要排序】，难点在于(d)。
- 如何对{5,7} {4,6}，计算出逆序对。 只要重复递归步骤(d)便可计算出所有的逆序对数。
针对步骤(d)：合并子数组 && 统计逆序对
如上图：
- 先用两个指针 P1、P2 指向两个子数组的末尾（P1 指向7，P2指向 6）
- 比较 P1、P2 指向的数的大小
- 如果 P1->num 大于 P2->num（如上图a情况 7>6）构成逆序对，且逆序对的数目 等于 第二个子数组中从左到指针处所有数字的个数。【图a是两对，图c是一对】
- 如果 P1->num 小于 P2->num（如上图b情况 5<6）不构成逆序对
- 注意：每次比较的时候，把较大的数字，从后往前放在另外一个数组中，以确保计算逆序对后得到一个排序好的数组
其实就是归并排序：复杂度为O(nlogn)
关于归并排序：https://blog.****.net/qq_39883358/article/details/83149825