【分治法】逆序对数目（Java）

问题介绍

?A[0…n-1]是一个有n个元素的数组。如果i < j， 但是A[i]>A[j]， 则这对元素 (A[i],A[j]) 被称为一个倒置 (inversion)。 设计一个 O(nlogn) 算法来计算数组中的倒置数量。

问题分析

分治法的主要思想是将问题分解成子问题，然后递归求解，并将子问题的解组合成原问题的解，优点在于它可以将大问题划分为更小的、更容易解决的子问题，从而简化了问题的求解过程。

?在问题中，可以采取取数组中间位置，将其前后分开为两部分，分别求解。分别求解的部分仍然继续使用该部分从中间分开的思想。和折半查找法所用的思想相同，不过，将折半查找法中的排序变成了倒置的代码。将左右部分分开后分别进行逆序对的求解，然后合并，不仅仅要统计倒置数量，还要保证左半右半有序。

代码

?如果left >= right，即数组范围内只有一个元素或者没有元素，直接返回。否则，找到数组的中间位置mid，然后递归地计算左半部分和右半部分的倒置数量，并且通过调用merge方法合并两个已经排好序的数组,计算跨越左右两部分的倒置数量。最后返回左半部分倒置数量、右半部分倒置数量和跨越两部分的倒置数量之和作为结果。

public class InversionCount {
    public static void main(String[] args) {
        int[] array = {5, 4, 3, 2, 1};
        InversionCount inversionCounter = new InversionCount();
        int inversionCount = inversionCounter.nInversion(array, 0, array.length - 1);
        System.out.println("Number of inversions: " + inversionCount);
    }
    public int nInversion(int[] v, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        int nLeft = nInversion(v, left, mid); // 从left..mid已经有序
        int nRight = nInversion(v, mid + 1, right); // 从mid+1..right已经有序
        int nCross = merge(v, left, mid, right);
        return nLeft + nRight + nCross;
    }

    public int merge(int[] v, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        int cnt = 0;
        int[] u = new int[right - left + 1];
        while (i <= mid && j <= right) {
            if (v[i] > v[j]) {
                u[k] = v[j];
                cnt = cnt + (mid - i + 1);
                j = j + 1;
                k = k + 1;
            } else {
                u[k] = v[i];
                i = i + 1;
                k = k + 1;
            }
        }
        while (i <= mid) {
            u[k] = v[i];
            i = i + 1;
            k = k + 1;
        }
        while (j <= right) {
            u[k] = v[j];
            j = j + 1;
            k = k + 1;
        }
        for (int index = 0; index < u.length; index++) {
            v[left + index] = u[index];
        }
        return cnt;
    }
}