逆序數(shù)怎么算？

一個排列中所有逆序總數(shù)叫做這個排列的逆序數(shù)。

在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。逆序數(shù)為偶數(shù)的排列稱為偶排列；逆序數(shù)為奇數(shù)的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數(shù)是4，為偶排列。

如數(shù)列 3 5 4 8 2 6 9

(5,4)是一個逆序?qū)Γ瑯舆€有(3,2),(5,2),(4,2)等等。

什么是逆序數(shù)：

跟標(biāo)準(zhǔn)列相反序數(shù)的總和

比如說

標(biāo)準(zhǔn)列是1 2 3 4 5

那么 5 4 3 2 1 的逆序數(shù)算法：

5之前沒有數(shù)，記為0.

看第二個，4之前有一個5，在標(biāo)準(zhǔn)列中5在4的后面，所以記1個

類似的，第三個 3 之前有 4 5 都是在標(biāo)準(zhǔn)列中3的后面，所以記2個

同樣的，2 之前有3個，1之前有4個

將這些數(shù)加起來就是逆序數(shù)=1+2+3+4=10

再舉一個 2 4 3 1 5

4 之前有0個

3 之前有1個

1 之前有3個

5 之前有0個

所以逆序數(shù)就是1+3=4

逆序數(shù)的求法：

1.一個一個的數(shù)

最簡單也是最容易想到的方法就是，對于數(shù)列中的每一個數(shù)a[i]，遍歷數(shù)列中的數(shù)a[j](其中j<i),若a[i]<a[j],則逆序數(shù)加1，這樣就能統(tǒng)計出該數(shù)列的逆序數(shù)總和

該方法的時間復(fù)雜度為O(n^2)