逆序數怎么算?
一個排列中所有逆序總數叫做這個排列的逆序數。
在一個排列中,如果一對數的前后位置與大小順序相反,即前面的數大于后面的數,那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列;逆序數為奇數的排列稱為奇排列。如2431中,21,43,41,31是逆序,逆序數是4,為偶排列。
如數列 3 5 4 8 2 6 9
(5,4)是一個逆序對,同樣還有(3,2),(5,2),(4,2)等等。
什么是逆序數:
跟標準列相反序數的總和
比如說
標準列是1 2 3 4 5
那么 5 4 3 2 1 的逆序數算法:
5之前沒有數,記為0.
看第二個,4之前有一個5,在標準列中5在4的后面,所以記1個
類似的,第三個 3 之前有 4 5 都是在標準列中3的后面,所以記2個
同樣的,2 之前有3個,1之前有4個
將這些數加起來就是逆序數=1+2+3+4=10
再舉一個 2 4 3 1 5
4 之前有0個
3 之前有1個
1 之前有3個
5 之前有0個
所以逆序數就是1+3=4
逆序數的求法:
1.一個一個的數
最簡單也是最容易想到的方法就是,對于數列中的每一個數a[i],遍歷數列中的數a[j](其中j<i),若a[i]<a[j],則逆序數加1,這樣就能統計出該數列的逆序數總和
該方法的時間復雜度為O(n^2)