目录
1 问题描述
给定一个随机数数组，求取这个数组中的逆序对总个数。要求时间效率尽可能高。
那么，何为逆序对？
引用自百度百科：
设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。
例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。
2 解决方案
2.1 蛮力法
初步一看，使用蛮力是最直接也最简单的方法，但是时间效率为O(n^2)。
即从第1个元素，开始依次和后面每一个元素进行大小比较，若大于，则逆序对个数加1。
具体代码如下：
package com.liuzhen.systemExe; public class Main{ //蛮力法求取数组A中逆序对数 public int bruteReverseCount(int[] A) { int result = 0; for(int i = 0;i < A.length;i++) { for(int j = i;j < A.length;j++) { if(A[i] > A[j]) result++; } } return result; } //获取一个随机数数组 public int[] getRandomArray(int n) { int[] result = new int[n]; for(int i = 0;i < n;i++) { result[i] = (int)( Math.random() * 50); //生成0~50之间的随机数 } return result; } public static void main(String[] args){ long t1 = System.currentTimeMillis(); Main test = new Main(); int[] A = test.getRandomArray(50000); int result = test.bruteReverseCount(A); long t2 = System.currentTimeMillis(); System.out.println("使用蛮力法得到结果："+result+"， 耗时："+(t2 - t1)+"毫秒"); } }
运行结果(运行3次)：
使用蛮力法得到结果：612226389， 耗时：8094毫秒 使用蛮力法得到结果：610311942， 耗时：8015毫秒 使用蛮力法得到结果：610657465， 耗时：8079毫秒
2.2 分治法（归并排序）
除了蛮力法，此处可以借用归并排序的思想来解决此题，此时时间复杂度为O（n*logn）。归并排序，具体是先进行对半划分，直到最后左半边数组只有一个元素，右半边数组中也只有一个元素时，此时开始进行回溯合并。那么，计算逆序对个数的关键，就在于此处的回溯合并过程，当左半边元素（PS：回溯过程中，左半边和右半边元素均已是升序排序）中出现大于右半边元素时，那么左半边这个元素及其后面的所有元素均大于这个右半边元素，记这些元素个数为len，那么逆序对个数要自增len。
具体代码如下：
package com.liuzhen.systemExe; public class Main{ public long count = 0; //全局变量，使用合并排序，计算逆序对数 //使用归并排序方法计算数组A中的逆序对数 public void getReverseCount(int[] A) { if(A.length > 1) { int[] leftA = getHalfArray(A, 0); //数组A的左半边元素 int[] rightA = getHalfArray(A, 1); //数组A的右半边元素 getReverseCount(leftA); getReverseCount(rightA); mergeArray(A, leftA, rightA); } } //根据judge值判断，获取数组A的左半边元素或者右半边元素 public int[] getHalfArray(int[] A, int judge) { int[] result; if(judge == 0) { //返回数组A的左半边 result = new int[A.length / 2]; for(int i = 0;i < A.length / 2;i++) result[i] = A[i]; } else { //返回数组的右半边 result= new int[A.length - A.length / 2]; for(int i = 0;i < A.length - A.length / 2;i++) result[i] = A[A.length / 2 + i]; } return result; } //合并数组A的左半边和右半边元素，并按照非降序序列排列 public void mergeArray(int[] A, int[] leftA, int[] rightA) { int len = 0; int i = 0; int j = 0; int lenL = leftA.length; int lenR = rightA.length; while(i < lenL && j < lenR) { if(leftA[i] > rightA[j]) { A[len++] = rightA[j++]; //将rightA[j]放在leftA[i]元素之前，那么leftA[i]之后lenL - i个元素均大于rightA[j] count += (lenL - i); //合并之前，leftA中元素是非降序排列，rightA中元素也是非降序排列。所以，此时就新增lenL - i个逆序对 } else { A[len++] = leftA[i++]; } } while(i < lenL) A[len++] = leftA[i++]; while(j < lenR) A[len++] = rightA[j++]; } //获取一个随机数数组 public int[] getRandomArray(int n) { int[] result = new int[n]; for(int i = 0;i < n;i++) { result[i] = (int)( Math.random() * 50); //生成0~50之间的随机数 } return result; } public static void main(String[] args){ long t1 = System.currentTimeMillis(); Main test = new Main(); int[] A = test.getRandomArray(50000); test.getReverseCount(A); long t2 = System.currentTimeMillis(); System.out.println("分治法得到结果："+test.count+"， 耗时："+(t2 - t1)+"毫秒"); } }
运行结果（运行3次）：
分治法得到结果：612226489， 耗时：36毫秒 分治法得到结果：610481152， 耗时：35毫秒 分治法得到结果：612161208， 耗时：32毫秒
参考资料：
1. 归并排序求逆序对
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
