java改编归并排序实现求解逆序对的数量

逆序对问题 用改写归并排序过程解决
* 逆序问题 左边的数如果比右边的数大，则折两个数构成一个逆序对，打印逆序对的数量。
* 其实就是求解一个数右边有多少个数比它小
* 解决办法 从右向左合并 遇到相等的右移右组的指针

思想和前面求解小和问题一样 左边产生的逆序对的数量和右边产生再加上merge过程产生的逆序对的数量
代码如下

import java.util.Scanner;

public class code13_ReversePair2 {
    
    // arr[L..R]既要排好序，也要求逆序对数量返回
    // 所有merge时，产生的逆序对数量，累加，返回
    // 左 排序 merge并产生逆序对数量
    // 右 排序 merge并产生逆序对数量

    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        // l < r
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }
    //merge过程产生逆序对的数量
    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = help.length - 1;
        int p1 = m;
        int p2 = r;

        int res = 0;
        while (p1 >= L && p2 > m) {
            res += arr[p1] > arr[p2] ? (p2 - m) : 0;
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L) {
            help[i--] = arr[p1--];
        }
        while (p2 > m) {
            help[i--] = arr[p2--];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine().toString();
        String[] arr = str.split(" ");
        int[] b=new int[arr.length];
        for(int i=0;i 
测试代码如下
 
 
新创建一个公众号 Rockey小何同学 想相互交流的同学可以关注一下哈！ 感谢支持！					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5719882.html