获取数组中逆序对的对数

package class04;
import java.util.Arrays;
/**
* 获取数组中逆序对的对数
*

* 在一个数组中，
* 任何一个前面的数a，和任何一个后面的数b，
* 如果(a,b)是降序的，就称为逆序对。
* 返回数组中所有的逆序对的对数。
*/
public class Code03_reversePairNumber {
public static int reversePairNumber(int[] arr) {
if (arr == null || arr.length <2) {
return 0;
}
return process(arr, 0, arr.length - 1);
}
private static int process(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int M = L + ((R - L) >> 1);
return process(arr, L, M) + process(arr, M + 1, R) + merge(arr, L, M, R);
}
private static int merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int ans = 0;//用于记录逆序对的对数
int p1 = M;//定义p1先在左组的最右位置
int p2 = R;//定义p2先在右组的最右位置
int i = help.length - 1;//辅助数组help，从后往前逆序填值。
while (p1 >= L && p2 >= M + 1) {
//如果arr[p1]大于arr[p2]，那么右组中p2(不含)左侧的所有数，都是大于arr[p1]的，给ans累加上这个个数。
ans += arr[p1] > arr[p2] ? p2 - (M + 1) + 1 : 0;
//如果左组中的arr[p1]，大于右组中的arr[p2]，就给help[i]赋值arr[p1]，p1--，i--。
//如果左组中的arr[p1]，小于等于右组中的arr[p2]，就给help[i]赋值arr[p2]，p2--，i--。
//注意，如果是等于，一定是给help[i]赋值右组的arr[p2]，而不是左组的arr[p1]。否则，对于左组的arr[p1]，我们不知道右组中一共有几个数是小于arr[p1]的。
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= L) {//只要p1大于等于左组的0位置
help[i--] = arr[p1--];//就将arr[p1]赋值给help[i]，p1--，i--。
}
while (p2 >= M + 1) {//只要p2大于等于右组的0位置
help[i--] = arr[p2--];//就将arr[p2]赋值给help[i]，p2--，i--。
}
for (i = 0; i //将辅助数组help中的值，全部倒给原数组arr。仅仅是当前一个小组。
arr[L + i] = help[i];
}
return ans;
}
//获取逆序对的对数，用于测试。
public static int reversePairNumberForTest(int[] arr) {
int ans = 0;
for (int i = 0; i ) {
for (int j = 0; j ) {
if (arr[j] > arr[i]) {//数组中，当任意一个数大于它左侧的任意一个数时，ans就累加一。
ans++;
}
}
}
return ans;
}
public static int[] generatorRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) (Math.random() * maxSize) + 2];
for (int i = 0; i ) {
arr[i] = (int) (Math.random() * maxValue);
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i ) {
res[i] = arr[i];
}
return res;
}
public static void main(String[] args) {
int maxSize = 100;
int maxValue = 100;
int testTimes = 100000;
System.out.println("test start!");
for (int i = 0; i ) {
int[] arr0 = generatorRandomArray(maxSize, maxValue);
int[] arr1 = copyArray(arr0);
int[] arr2 = copyArray(arr0);
int num1 = reversePairNumber(arr1);
int num2 = reversePairNumberForTest(arr2);
if (num1 != num2) {
System.out.println("oops!");
System.out.println("arr0 = " + Arrays.toString(arr0));
System.out.println("num1 = " + num1);
System.out.println("num2 = " + num2);
break;
}
}
System.out.println("test end!");
}
}