编辑代码

class Main {
	 public static void main(String[] args) {
        int[] a={2,14,21,23,45,2,1,13};
        int[] b={7,43,2,4,53,4,6,44,3,43};
        int[] c={0};
        int[] d={1,2,3,4,5};
        int[] e={5,4,3,2,1};
        System.out.println(reverOrder(a,0,a.length,0));
        System.out.println(reverOrder(b,0,b.length,0));
        System.out.println(reverOrder(c,0,c.length,0));
        System.out.println(reverOrder(d,0,d.length,0));
        System.out.println(reverOrder(e,0,e.length,0));
    }
    public static void display(int[] arr){
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    //分
    public  static int reverOrder(int[] arr,int arrStart,int arrEnd,int sum){
        int mid=(arrStart+arrEnd)/2;
        if((arrEnd-arrStart)<=2){
            sum+=hebing(arr,arrStart,mid,arrEnd);
//            System.out.println("上");
        }else {
            sum+=reverOrder(arr,arrStart,mid,0);
            sum+=reverOrder(arr,mid,arrEnd,0);
            sum+=hebing(arr,arrStart,mid,arrEnd);
//            System.out.println("下");
        }
//        System.out.println(sum);
        return sum;
    }

    //求逆序
    public static int hebing(int[] arr,int start,int mid,int end){
        int sum=0;
        int index1=start;
        int index2=mid;
        int min=(start+end)/2;
        int[] tempArr=new int[end-start];
        int tempIndex=0;
        while (tempIndex<tempArr.length){
            if(index1>=mid){
                for (int i=index2;i<end;i++){
                    tempArr[tempIndex]=arr[i];
                    tempIndex++;
                }
            }
            else if(index2>=end){
                for (int i=index1;i<min;i++){
                    tempArr[tempIndex]=arr[i];
                    tempIndex++;
                }
            }
            else {
                if(arr[index1]<=arr[index2]){
                    tempArr[tempIndex]=arr[index1];
                    index1++;}
                else if(arr[index1]>arr[index2]){
                    sum+=mid-index1;
                    tempArr[tempIndex]=arr[index2];
                    index2++;}
            }
            tempIndex++;
        }
        for (int i=start;i<end;i++){
            arr[i]=tempArr[i-start];
        }
//        System.out.println(start+","+mid+","+end+",");
//        display(arr);
        return sum;

    }

}