三位逆序數(shù)的計算方法？

比如4 3 1 2

4第一個，所以數(shù)目為0

3的前面是4，大于3的數(shù)目為1

1的前面是4 3 ，大于1的數(shù)目為2

2的前面是4 3 1，大于2的數(shù)目為2

所以逆序數(shù)為1+2+2 = 5

求逆序數(shù)的兩種方法

常規(guī)方法是按照逆序數(shù)的規(guī)則做，結(jié)果復雜度是O(n*n)，一般來說，有兩種快速的求逆序數(shù)的方法

分別是歸并排序和樹狀數(shù)組法

2. 歸并排序

歸并排序是源于分而治之思想，詳細的過程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個有序序列合并起來。

如何修改歸并排序求逆序數(shù)?

首先我們假設兩個有序序列a[i]和b[i]，當合并時：

由于a[i]已是有序，所以對于a[i]的各個元素來說，排在它前面且比它大的數(shù)目都是0

當b[i]中含有比a[i]小的元素時，我們必然將b[i]元素插到前面，那么就是說，在b[i]原先位置到該插的位置中，所有數(shù)都比b[i]大且排在它前面

所以這是b[i]的數(shù)目為新插入位置newPos - 原來位置oldPos