逆序數
排列中逆序的總數
也就是說，對於n個不同的元素，先規定各元素之間有一個標準次序（例如n個 不同的自然數，可規定從小到大為標準次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標準次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。
在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。
逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。
nixushu
逆序數
計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。例如在序列 中，逆序依次為 (2,1), (4,3), (4,1), (3,1)，因此該序列的逆序數為 4。下面這個 Visual Basic 6.0 編寫的示例使用的就是直接計數的方法，函數 NiXushu 返回一個字元串的逆序數。
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=1Toi-1
If n(i)
c=c+1
End If
Next j
Next i
NiXuShu = c
End Function
直接計數法雖然簡單直觀，但是其時間複雜度是。一個更快（但稍複雜）的計算方法是在歸併排序的同時計算逆序數。
下面這個編寫的例子演示了計算方法。函數 mergeSort() 返回序列的逆序數。
int is1[n],is2[n];// is1為原數組，為臨時數組，n為個人定義的長度
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)
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;
基本信息
目錄