编辑代码

public class CountInversions {
    public static long 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 long mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        long count = 0;
        if (left < right) {
            int mid = (left + right) / 2;

            // 递归地计算左侧和右侧子数组中的逆序对数量
            count += mergeSortAndCount(arr, temp, left, mid);
            count += mergeSortAndCount(arr, temp, mid + 1, right);

            // 合并两个子数组并在合并过程中计算逆序对数量
            count += mergeAndCountInversions(arr, temp, left, mid, right);
        }
        return count;
    }

    private static long mergeAndCountInversions(int[] arr, int[] temp, int left, int mid, int right) {
        long count = 0;

        int i = left; // 左侧子数组的索引
        int j = mid + 1; // 右侧子数组的索引
        int k = left; // 合并后子数组的索引

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

        // 复制左侧和右侧子数组中剩余的元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将合并后的子数组复制回原始数组
        System.arraycopy(temp, left, arr, left, k - left);

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 1, 5,6};
        long inversions = countInversions(arr);
        System.out.println("逆序对数量：" + inversions);
    }
}