逆序數的計算三種方法？

1. 逆序數

所謂逆序數，就是指一個序列S[i]，統計處于序列的每個數的比這個數大并且排在它前面的數的數目，然后對于所有數，把這個數目加起來求和就是了。

比如4 3 1 2

4第一個，所以數目為0

3的前面是4，大于3的數目為1

1的前面是4 3 ，大于1的數目為2

2的前面是4 3 1，大于2的數目為2

所以逆序數為1+2+2 = 5

求逆序數的兩種方法

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

分別是歸并排序和樹狀數組法

2. 歸并排序

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

如何修改歸并排序求逆序數?

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

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

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

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