编辑代码

class Main {
	public static void main(String[] args) {
        //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。
		int[] arry = {2,4,3,1,5,6};
        System.out.println("该数组逆序对个数为："+countInversions(arry));
		for(int i = 0; i < arry.length; i++){
            System.out.print(arry[i]+" ");
        }
	}
    public static int countInversions(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0; // 数组为空或只有一个元素，无逆序对
        }
        int[] temp = new int[arr.length];
        return mergeSortAndCountInversions(arr, 0, arr.length - 1, temp);
    }

    private static int mergeSortAndCountInversions(int[] arr, int left, int right, int[] temp) {
        int inversionCount = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            inversionCount += mergeSortAndCountInversions(arr, left, mid, temp);
            inversionCount += mergeSortAndCountInversions(arr, mid + 1, right, temp);
            inversionCount += mergeAndCountInversions(arr, left, mid, right, temp);
        }
        return inversionCount;
    }

    private static int mergeAndCountInversions(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        int inversionCount = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversionCount += (mid - i + 1); // 统计逆序对数
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }

        return inversionCount;
    }
}