后知后觉

用户名：uq_93478337688

访问量：59

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

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

　　作者: 后知后觉　　　　发表时间：2023-03-11 19:53:43 浏览：30　|　评论：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分

1 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

后知后觉

TA的其他文章

你可能喜欢

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

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

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

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

程序员的表白（C语言代码）

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

评论区

精彩推荐

P1002 （C语言代码）

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

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

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

本人酷爱递归实现很多问题，这里也是

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

哥德巴赫曾猜测（C语言代码）

完数（C语言代码）

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

矩阵加法（C语言代码）

后知后觉

TA的其他文章

你可能喜欢

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

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

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

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

程序员的表白 （C语言代码）

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

评论区

精彩推荐

P1002 （C语言代码）

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

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

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

本人酷爱递归实现很多问题，这里也是

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

哥德巴赫曾猜测 （C语言代码）

完数 （C语言代码）

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

矩阵加法 （C语言代码）

程序员的表白（C语言代码）

　　评论区

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

哥德巴赫曾猜测（C语言代码）

完数（C语言代码）

矩阵加法（C语言代码）