Question

求排列的逆序数

Answer 1

求排列的逆序数：

O(n2)

分治O(nlogn)： 

1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数 

2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成（要求O(n)实现）

由归并排序改进得到，加上计算逆序的步骤

MergeSortAndCount：归并排序并计算逆序数

注意：在一个排列中，如果一对数的前后位置与大小顺序相反（即前面的数大于后面的数），那么这一对数就被称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。