2019-05-23逆序队

package 逆序对问题;

import java.util.Arrays;

public class Reverse {
    public static void main(String[] args) {
        int[] arr= {1,2,3,4,5,6,1};
        int res=reverseOrder(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(res);
    }
    public static int reverseOrder(int[] arr) {
        if(arr==null || arr.length<2) {
            return 0;
        }
        int res=reverseProcess(arr, 0, arr.length-1);
        return res;
        
    }
    public static int reverseProcess(int[] arr, int L, int R) {
        if(L==R) {
            return 0;
        }
        int mid=(L+R)/2;
        return reverseProcess(arr, L, mid)+
            reverseProcess(arr, mid+1, R)+
            mergerRevprint(arr, L, mid, R);
    }
    public static int mergerRevprint(int[] arr, int l, int mid, int r) {
        int p1=l;
        int i=0;
        int p2=mid+1;
        int[] help = new int[r-l+1];
        int count=0;
        while(p1<=mid && p2<=r) {
            if(arr[p1]>arr[p2]) {
                for(int k=p2;k<=r;k++) {
                    System.out.println(arr[p1]+" "+arr[k]);
                    ++count;
                }
                help[i++]=arr[p1++]; 
                // 解释一下这里为什么把p1放进去了因为通过for一次性将逆序对全部打印完了就不存在比
                //p1还要小的数了这里的变化也可以用作归并排序的从大到小的排序方式
            }else {
                help[i++]=arr[p2++];
            }
            //help[i++] = arr[p1]>arr[p2]?arr[p1++]:arr[p2++];
            // 不用上一语句的原因是if语句已经比较过了如果写上这个语句会进行重复比较没有意义
        }
        while(p1<=mid) {
            help[i++]=arr[p1++];
        }
        while(p2<=r) {
            help[i++]=arr[p2++];
        }
        for(int k=0;k<help.length;k++) {
            arr[l+k]=help[k];
        }
        return count;
    }
}