問題描述

笨方法:O(n2)

分治O(nlogn)

1)將數(shù)組分成兩半,分別求出左半邊的逆序數(shù)和右半邊的序數(shù)
2)再算有多少逆序是由左半邊去一個(gè)數(shù)和右半邊取一個(gè)數(shù)構(gòu)成(要求O(n)實(shí)現(xiàn))
解決關(guān)鍵:左半邊和右半邊都是排好序的.比如,都是從大到小排序的,這樣,左右半邊只需要從頭到尾各掃一遍,就可以找出由量變各取一個(gè)數(shù)構(gòu)成的逆序個(gè)數(shù)
下圖是上面2)的圖示

首先在排好序后,我們可以得到在本組內(nèi),逆序數(shù)的個(gè)數(shù),然后左右各掃一遍,如上圖,如果i<j,那么i后面的書也小于j,肯定不能構(gòu)成逆序數(shù),j++,當(dāng)j=5時(shí),i>j,i往后走i++,一直到3,此時(shí)不構(gòu)成,j++,i=3,j=2,構(gòu)成逆序數(shù),所以得出上述2)中的情況

總結(jié)

由歸并排序改進(jìn)得到,加上計(jì)算逆序的步驟
MergeSortAndCount:歸并排序并計(jì)算逆序數(shù)