编辑代码

public class InversionCount {
    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 1, 5, 6};
        int count = countInversions(arr);
        System.out.println("逆序对的个数为: " + count);
    }

    public static int countInversions(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0; // 无逆序对
        }

        int[] temp = new int[arr.length];
        return mergeSortAndCount(arr, temp, 0, arr.length - 1);
    }

    private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;
            int leftCount = mergeSortAndCount(arr, temp, left, middle);
            int rightCount = mergeSortAndCount(arr, temp, middle + 1, right);
            int mergeCount = merge(arr, temp, left, middle, right);
            return leftCount + rightCount + mergeCount;
        }
        return 0;
    }

    private static int merge(int[] arr, int[] temp, int left, int middle, int right) {
        int i = left;
        int j = middle + 1;
        int k = left;
        int count = 0; // 统计逆序对的个数

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

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

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

        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }

        return count;
    }
}