逆序对（逆序对问题） 分而治之方法（分治法）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;
}

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

欢迎讨论！