定义：对于一个给定的数列,如果有i<j,且Ai>Aj,则称(i,j)为一逆序对. 要解决的问题是,给出一个数列,求出这个数列包含多少个逆序对。 例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,《3,2》，<4,2><5,2>，共4个。
首先给定了这是一个有序表，所谓有序表，是指这样的线性表，其中所有元素以递增或递减方式有序排列。 所以我们不用再进行排序了。 一般思路，就是就是遍历整个序列，判断实数与它后面的每个实数是否构成逆序对，这种算法的时间复杂度为Ο(n2)。 另一种就是采用分治算法，分为小规模的算法，进行分析。 下面上代码，直接进行边看边讲解：‘
package hello; import org.omg.CORBA.PUBLIC_MEMBER; public class M2 { public static int n=0; public static void merge(int a[],int first,int mid,int last) { int temp[] = new int[last-first+1];//临时数组，用于临时存放比较后的数字 int i=first,j=mid+1,k=0; while(i<=mid&&j<=last)//遍历比较左右两个部分 { if(a[i]<=a[j]) temp[k++] = a[i++]; //左半部分元素小于右半部分的元素，将左边该元素存入临时数组 else { temp[k++] = a[j++]; n=n+(mid-i+1);//统计左半边能和右半边该元素构成的逆序对数 } } while(i<=mid) temp[k++]=a[i++]; while(j<=last) temp[k++]=a[j++]; for(i=0; i < k;i++) a[first + i] = temp[i];//从临时数组取出放回原数组 } public static void mergesort(int a[],int first,int last) { if(first < last) { int mid = (first+last)/2; mergesort(a,first,mid);//递归排序左半部分 mergesort(a,mid+1,last);//递归排序右半部分 merge(a,first,mid,last);//将处理后的两个部分合并 } } public static void main(String[] args) { // TODO Auto-generated method stub int a[] = {4,3,2,1},i; System.out.println("序列:"); for(i=0;i<4;i++) System.out.println(a[i]); mergesort(a,0,3); System.out.println("逆序对数："); System.out.println(n-1); } }