后知后觉

用户名：uq_93478337688

访问量：121

签　名：

等　　级
排　　名	39389
经　　验	338
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

分治归并求逆序对个数（java)
浏览：68

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

分治归并求逆序对个数（java)

　　作者: 后知后觉　　　　发表时间：2023-03-11 19:53:43 浏览：68　|　评论：0　

原题链接：求逆序对个数

## 思路
分治的思想。
总的逆序数=左子数组的逆序数+右子数组的逆序数+横跨两个有序子数组的数产生的逆序的个数。
### 对于子数组的逆序数：
我们可以递归不断地将数组拆成两半，直到子数组长度为1，长度为1的子数组逆序数就是0；所以我们只需要累加上横跨两个有序子数组的数产生的逆序的个数就行了。
### 对于横跨两个有序子数组的数产生的逆序的个数。
在归并排序的过程中使子数组有序。
在合并两个有序子数组之前，统计横跨两个有序子数组的数产生的逆序的个数。
因为两个子数组都是升序的。逆序对一个出自左子数组，一个出自右子数组。
①如果左子数组中某个元素left[l]>右子数组的某个元素right[r].那么有所以左子数组中l以后的元素都将与right[r]构成逆序对。总的逆序数直接加left.length-l;
②然后r++,直到出现大于left[l]的，在左移l,找到left[l]>right[r],总的逆序数再加left.length-l；
③重复①②步直到l==left.length或r==right.length.因为若是前者，因为right升序，不可能在r+=k后找到left[k]>right[r+k];所以不会有逆序对。而若是后者，说明所有可能逆序对已经判断完了
最终得到的cnt就是总的逆序数。

```java
package algorithm.dongxin;
import java.util.Scanner;
public class ReverseOrderNumber {
    static int[] numArr;
    static int cnt=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        numArr=new int[n];
        for (int i=0; i<n;i++)
            numArr[i]=sc.nextInt();
        func(0,n-1);
        System.out.println(cnt);
    }
    static int[] mergeAndCnt(int[] arrl,int[] arrr,int len){//在做归并排序合并两个有序子数组之前记录逆序数。
        int l=0,r=0;
        while(l<arrl.length&&r<arrr.length){
            if(arrl[l]>arrr[r]){
                cnt+=arrl.length-l;
                r++;
            }
            else
                l++;
        }
        l=0;r=0;
        int[] allArr=new int[len];
        int i=0,tag=0;
        while(r<arrr.length){
            if(tag==1)
                break;
            if(arrl[l]<arrr[r]){
                allArr[i++]=arrl[l];
                l++;
            }
            else{
                allArr[i++]=arrr[r];
                r++;
            }
            if(r>=arrr.length){
                for(int j=l;j<arrl.length;j++){
                    allArr[i++]=arrl[j];
                }
                tag=1;
            }
            if(l>=arrl.length){
                for(int j=r;j<arrr.length;j++){
                    allArr[i++]=arrr[j];
                }
                tag=1;
            }
        }
        return allArr;
    }

static int[]  func(int start, int end) {//归并排序的过程
        if(end==start){
            int[] Arr=new int[]{numArr[start]};
            return Arr;
        }
        else{
            int mid=(end+start)/2;
            int[] midArrl=func(start,mid),midArrr=func(mid+1,end);
            return mergeAndCnt(midArrl,midArrr,end-start+1);
        }
    }
}

```

0.0分

3 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

后知后觉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

A+B for Input-Output Practice (I) （C++代码）

回文数字（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

分治归并求逆序对个数（java)

评论区

精彩推荐

震宇大神的杀毒软件（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1009题解

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数（C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

后知后觉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

A+B for Input-Output Practice (I) （C++代码）

回文数字 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

分治归并求逆序对个数（java)

评论区

精彩推荐

震宇大神的杀毒软件 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1009题解

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

字符串输入输出函数 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

回文数字（C++代码）

　　评论区

震宇大神的杀毒软件（C语言代码）

字符串输入输出函数（C语言代码）