在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。也就是說，對於n個不同的元素，先規定各元素之間有一個標準次序（例如n個 不同的自然數，可規定從小到大為標準次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標準次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。
基本介紹
- 中文名：逆序數
- 外文名：inversion number
- 有關求法：歸併排序
- 有關求法：冒泡排序
定義,逆序數的計算,直接計數,歸併排序,
定義
逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。
逆序數的計算
直接計數
計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 { 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
歸併排序
下面這個 C++ 編寫的例子演示了計算方法。函式 mergeSort() 返回序列的逆序數。
int is1[n],is2[n];// is1為原數組，is2為臨時數組，n為個人定義的長度
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;
}
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;
}
