数据结构与算法Java版-逆序对问题

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个构成一个逆序对，请打印所有的逆序对数量

• 思路：
  逆序对数量的问题可以使用归并排序的思路，只不过需要按照从大到小的顺序排列，在归并的时候计算逆序对数，java实现如下：

package problem;

public class ReverseOrderPair {
// 在一个数组中，左边的数如果比右边的数大，则这两个构成一个逆序对，请打印所有的逆序对数量
public static int merge(int[] arr,int left,int mid,int right)
{
int num=0;
int p1=left;
int p2=mid+1;
int[] arr_new=new int[right-left+1];
int i=0;
while(p1<=mid && p2<=right)
{
num+=arr[p1]>arr[p2]?(right-p2+1):0;
arr_new[i++]=arr[p1]>arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid)
{
arr_new[i++]=arr[p1++];
}
while(p2<=right)
{
arr_new[i++]=arr[p2++];
}
for(int j=0;j<arr_new.length;j++)
{
arr[left+j]=arr_new[j];
}
return num;
}
public static int getReverseOrderPairNum(int[] arr,int left,int right)
{
if(arr==null || arr.length<2 || left==right)
{
return 0;
}
int mid=left+((right-left)>>1);
return getReverseOrderPairNum(arr,left,mid)+getReverseOrderPairNum(arr,mid+1,right)+merge(arr,left,mid,right);

}
public static void printArray(int[] arr)
{
for(int elem:arr)
{
System.out.print(elem+"\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr={6,1,3,4,2,5,0};
int sum=getReverseOrderPairNum(arr,0,arr.length-1);
System.out.println(sum);
printArray(arr);
}
}

执行结果如下：

13
6 5 4 3 2 1 0