在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序(例如n个 不同的自然数，可规定从小到大为标准次序)，于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

• 中文名 逆序数
• 外文名 Inverse 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

归并排序

　　直接计数法虽然简单直观，但是其时间复杂度是 O(n^2)。一个更快(但稍复杂)的计算方法是在归并排序的同时计算逆序数。下面这个 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;

　　}