逆序对（逆序对问题） 分而治之方法（分治法）java代码实现完整版（递归实现）

什么是逆序对：

对于一个包含n个整数的数组arr[1…n]，如果有i < j，且arr[ i ]>arr[ j ]，则称(A[ i] ,A[ j] )为数组arr中的一个逆序对。

一般思维：

蛮力枚举：
即两层for循环遍历每个元素，这样的算法时间复杂度为O(n²).
那么我们能否利用分治法去寻找一个更有效的方法去解决问题呢。

分治法解决逆序对：

我们可以参考归并排序的过程，结合归并排序每次比较排序之后的有序性，在合并的过程中进行统计逆序对的个数，（不太了解分治法和归并排序的读者，可以点击查看我的另一篇博文：归并排序（分而治之法））。
合并之后，合并在一起的两个部分之间都已经统计出了这两个部分的逆序对，之后就不需要再对合并后的自身进行统计啦，而且自身已经是有序的了（从小到大），只需要在对自身与要与自己合并的部分进行统计。
代码部分只需对归并排序的合并过程统计逆序对数，其他步骤和归并排序都一样。

java完整代码（递归实现）：

public int countInversion(int []arr,int left,int right) {
	if(left >= right) {
		return 0;					//递归出口
	}
	int mid = (int)((left+right)/2);
	int countLeft = countInversion(arr,left,mid);     //先左边递归
	int countRight = countInversion(arr,mid+1,right);     //再右边递归
	int countMerge = mergeInversion(arr,left,mid,right);	 	//调用排序函数
	return countLeft+countRight+countMerge;
}
public int mergeInversion(int []arr,int left,int mid, int right) {
	int i = left ,j = mid+1 ,tempIndex = left;				//i指向左半边，j指向右半边
	int count = 0;
	int []tempArr = arr.clone();
	while(i <= mid && j <= right) {
		if(tempArr[i]>tempArr[j]) {
			arr[tempIndex] = tempArr[j];
			count = count+right-j+1;    //统计逆序对个数
			j++;
			tempIndex++;
		}
		else {
			arr[tempIndex] = tempArr[i];
			i++;
			tempIndex++;
		}
	}
	if(i<=mid)
		count--;				//因为当右半边完时，左半边判断的指针未后移，在下面第一个while处会多自增一次，所以在这里先自减
	while(i<=mid) {				//左边还没有完，右边已完
		arr[tempIndex] = tempArr[i];
		count++;
		i++;
		tempIndex++;
	}
	while(j<=right){
		arr[tempIndex] = tempArr[j];  //右边还没有完，左边已完
		j++;
		tempIndex++;
	}
	return count;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

调用上述函数，结果运行：

欢迎讨论！

文章来源: blog.csdn.net，作者：Mr.Yushiwen，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/MrYushiwen/article/details/107230513