java编写程序求逆序数

可以使用归并排序的思想来求逆序数。具体步骤如下：

1. 定义一个函数 `mergeSort(int[] nums, int left, int right)`，表示对数组 nums 的下标从 left 到 right 进行归并排序，并返回该区间内的逆序数个数。

2. 在 `mergeSort` 函数中，如果 left 不等于 right，则计算出 mid = (left + right) / 2，然后递归调用 `mergeSort(nums, left, mid)` 和 `mergeSort(nums, mid+1, right)`。

3. 在 `mergeSort` 函数中，对于已经排好序的左右两个子数组，使用归并排序的思想进行合并，并计算出左右两个数组之间的逆序数个数。

4. 在 `merge` 函数中，定义一个临时数组 temp，以及三个指针 i、j 和 k。分别表示左子数组、右子数组和 temp 数组的下标。

5. 在 `merge` 函数中，将左右两个子数组中的元素按大小顺序依次放入 temp 数组中，并计算逆序数个数。具体实现方式为：如果左子数组中的元素比右子数组中的元素小，则逆序数个数加上右子数组中剩余元素的个数（因为左子数组中当前元素比右子数组中剩余元素都小），并将右子数组中当前元素放入 temp 数组；否则将左子数组中当前元素放入 temp 数组。

6. 在 `merge` 函数中，最后将 temp 数组中的元素复制回原数组 nums 中。

7. 在 `mergeSort` 函数中，返回左右两个子数组之间的逆序数个数，以及将左右两个子数组合并后的逆序数个数之和。

实现代码如下：

public class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid+1, right);
        int[] temp = new int[right - left + 1];
        int i = left, j = mid+1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                count += mid - i + 1;
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        System.arraycopy(temp, 0, nums, left, temp.length);
        return count;
    }
}