逆序數計算方法

『壹』 2n（2n-2）.....2（2n-1）(2n-3)...1的逆序數怎麼求，求詳細過程

2n（2n-2）.....2（2n-1）(2n-3)...1的逆序數

=(2n-1)+(2n-2-1)+(2n-4-1)+...+(2-1)+1/2((2n-1-1)+(2n-3-1)+...+(1-1))

=(2n-1)+(2n-3)+(2n-5)+...+1+1/2((2n-2)+(2n-4)+...+0)

=(2n-1+1)*n/2+1/2*(2n-2+0)*n/2)

=n^2+n(n-1)/2

=3/2n^2-1/2n

對於n個不同的元素，先規定各元素之間有一個標准次序（例如n個 不同的自然數，可規定從小到大為標准次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就說有1個逆序。

(1)逆序數計算方法擴展閱讀：

計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 2, 4, 3, 1 } 中，逆序依次為 (2,1)，(4,3)，(4,1)，(3,1)，因此該序列的逆序數為 4。

Visual Basic6.0 編寫的示例使用的就是直接計數的方法，函數 NiXushu 返回一個字元串的逆序數。

Private Function NiXuShu(ByVal l As String) As Long '逆序數計算

Dim i As Integer, j As Integer, c As Long

Dim n() As Integer

ReDim n(Len(l))

For i = 1 To Len(l)

n(i) = Val(Mid(l, i, 1))

For j = 1 To i - 1

If n(i) < n(j) Then

c = c + 1

End If

Next j

Next i

NiXuShu = c

End Function

『貳』 逆序數 公式

n(n-1)/2是排列n(n-1)…321的公式
317428695
在3前比3的有0個
在1前比1的有1個
在7前比7的有0個
以此類推
逆序數=0+1+0+1+3+0+2+0+3=10

『叄』 怎麼算逆序數急~~~！！！

可使用直接計數法，計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。

舉個例子：

標准列是1 2 3 4 5，那麼 5 4 3 2 1 的逆序數演算法：

看第二個，4之前有一個5，在標准列中5在4的後面，所以記1個。

類似的，第三個 3 之前有 4 5 都是在標准列中3的後面，所以記2個。

同樣的，2 之前有3個，1之前有4個，將這些數加起來就是逆序數=1+2+3+4=10。

(3)逆序數計算方法擴展閱讀：

其它演算法：

1、歸並排序

歸並排序是將數列a[l,h]分成兩半a[l,mid]和a[mid+1,h]分別進行歸並排序，然後再將這兩半合並起來。在合並的過程中（設l<=i<=mid，mid+1<=j<=h），當a[i]<=a[j]時，並不產生逆序數；

當a[i]>a[j]時，在前半部分中比a[i]大的數都比a[j]大，將a[j]放在a[i]前面的話，逆序數要加上mid+1-i。因此，可以在歸並排序中的合並過程中計算逆序數。

2、樹狀數組

由於樹狀數組的特性，求和是從當前節點往前求，所以，這里要查詢插入當前數值之時，要統計有多少個小於該數值的數還沒插入，這些沒插入的數，都會在後面插入，也就形成了逆序數。

『肆』 當排列數中出現相同的數時，逆序數怎麼計算，比如145243

逆序數是指一個排列中所有逆序總數，而排列，是從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列。

145243中出現出現相同的數4， 所以145243不是排列，也就無所謂計算逆序和逆序數了。

逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[1]如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

(4)逆序數計算方法擴展閱讀

計算逆序數：

標准列是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

『伍』 逆序數怎麼求

解答如下：

當n=1時，排列為1 2，逆序數t=0。

當n=2時，排列為內1 3 2 4，逆序容數t=1。

當n=3時，排列為1 3 5 2 4 6，逆序數t=1+2=3。

當n=4時，排列為1 3 5 7 2 4 6 8，逆序數t=1+2+3=6。

當n=5時，排列為1 3 5 7 9 2 4 6 8 10，逆序數t=1+2+3+4=10。

相關內容解釋

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。

也就是說，對於n個不同的元素，先規定各元素之間有一個標准次序(例如n個 不同的自然數，可規定從小到大為標准次序)，於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。

『陸』 求排列的逆序數有簡單的方法嗎

更快的的求排列的逆序數計算方法是在歸並排序的同時計算逆序數。下面這個 C++ 編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。
int is1[n],is2[n];// is1為原數組，is2為臨時數組，n為個人定義的長度。
long mergeSort(int a,int b)// 下標，例如數組int is[5]，全部排序的調用為：mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
long count=0;
count+=mergeSort(a,mid);
count+=mergeSort(mid+1,b);
count+=merge(a,mid,b);
return count;
}
return 0;
}
long merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long count=0;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j])// 此處為穩定排序的關鍵，不能用小於
is2[k++]=is1[i++];
else
{
is2[k++]=is1[j++];
count+=j-k;// 每當後段的數組元素提前時，記錄提前的距離
}
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 寫回原數組
is1[i]=is2[i];
return count;
}

『柒』 逆序數的逆序數的計算

計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 2, 4, 3, 1 } 中，逆序依次為 (2,1), (4,3), (4,1), (3,1)，因此該序列的逆序數為 4。下面這個 Visual Basic 6.0 編寫的示例使用的就是直接計數的方法，函數 NiXushu 返回一個字元串的逆序數。
Private Function NiXuShu(ByVal l As String) As Long '逆序數計算
Dim i As Integer, j As Integer, c As Long
Dim n() As Integer
ReDim n(Len(l))
For i = 1 To Len(l)
n(i) = Val(Mid(l, i, 1))
For j = 1 To i - 1
If n(i) < n(j) Then
c = c + 1
End If
Next j
Next i
NiXuShu = c
End Function 直接計數法雖然簡單直觀，但是其時間復雜度是 O(n^2)。一個更快（但稍復雜）的計算方法是在歸並排序的同時計算逆序數。下面這個 C++ 編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。
int is1[n],is2[n];// is1為原數組，is2為臨時數組，n為個人定義的長度
long mergeSort(int a,int b)// 下標，例如數組int is[5]，全部排序的調用為mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
long count=0;
count+=mergeSort(a,mid);
count+=mergeSort(mid+1,b);
count+=merge(a,mid,b);
return count;
}
return 0;
}
long merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long count=0;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j])// 此處為穩定排序的關鍵，不能用小於
is2[k++]=is1[i++];
else
{
is2[k++]=is1[j++];
count+=j-k;// 每當後段的數組元素提前時，記錄提前的距離
}
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 寫回原數組
is1[i]=is2[i];
return count;
}

『捌』 怎樣求逆序數

這個的是0
1後面<1的數0個＋2後面<2的數0個＋3後面<3的數0個＝0
可以推廣為（a,b,c,……，z)
a後面小於a的數A個……一直加到z後面小於z的數Z個
即為它的逆序數！

『玖』 逆序數的計算

解答如下：
當n=1時，排列為1
2，逆序數t=0；
當n=2時，排列為1
3
2
4，逆序數t=1；
當n=3時，排列為1
3
5
2
4
6，逆序數t=1+2=3；
當n=4時，排列為1
3
5
7
2
4
6
8，逆序數t=1+2+3=6；
當n=5時，排列為1
3
5
7
9
2
4
6
8
10，逆序數t=1+2+3+4=10；
………
依次類推得排列1，3，…（2n-1),2,4,…(2n)的逆序數為
T=0+1+2+3+…+（n-1）=n（n-1）/2
補充：
這個題目是由一個奇數列與一個偶數列組成的
2是分界點，把2之前的看成一部分，2之後（包括2）的看成一部分
然後再看2n-1與2n就會知道其規律性了

『拾』 關於排列逆序數的計算

順次一個一個檢測各個數的【逆序數】（排列後面比它小的數的個數。（其實這不是唯一的方法，但如果連這個方法也不會也不必貪多！）），然後把各個逆序數加起來就得到整個排列的逆序數。
排列中：N[(2n)...]=2n-1
【因為後面
2n-1個數都比2n小】；
N[。。(2n-2)。。。]
=2n-3
【2n-2後面有2n-2個數，除2n-1比它大，都小】；
N'(2n-4)=2n-5
【後面有2n-3個數，2n-1、2n-3比它大】；
。。。
N'(2)=1
【只有
1
比它小】；
N'[(2n-1)]=n-1
【後面n-1個都比它小】；
N'[(2n-3)]=n-2
。。。
。。。
N『(3)=1
【1
比它小】；
N'(1)=0
【後面沒有比它小的】；
所以，排列的逆序數=N(排列）
=(2n-1)+(2n-3)+...+3+1+(n-1)+(n-2)+...+2+1+0
=[(1+2n-1)n/2]+(0+n-1)n/2
=(2n^2)/2+(n^2-n)/2
=(3n^2-n)/2
【逆序數的計算因方法的不同，數值並不唯一，但奇偶性是一定的。】