nlogn求逆序对

问题描述：若一个数组为[A1, A2, ..., An]，若有i<j且Aj>Ai，那么Ai和Aj就构成一个逆序对。该问题是求出数组中所有逆序对的数目。

 

算法思想：使用分治法可以在O(nlogn)的时间复杂度下，求出逆序对。其思想为，把一个数组拆分为两个子数组，不妨称为L和R，那么原数组的逆序对数就等于L的逆序对数加上R的逆序对数，再加上一个元素在L中另一个元素在R中构成的逆序对数。可以在分解时独立求出L和R中逆序对数，然后合并时再加上L和R共同构成的逆序对数。

public class reverseOrder {
	
	private static int number = 0;

	public static void mergeSort(int[] a, int[] b, int begin, int end) {
		if (begin < end) {
			int mid = (begin + end) / 2;
			mergeSort(a, b, begin, mid);
			mergeSort(a, b, mid+1, end);
			merge(a, b, begin, mid, end);
			copy(a, b, begin, end);
		}
	}
	
	public static void merge(int[] a, int[] b, int begin, int mid, int end) {
		int i = begin;
		int k = begin;
		int j = mid+1;
		while (i <= mid && j <= end) {
			if (a[i] <= a[j]) {
				b[k++] = a[i++];
			}
			else {
				b[k++] = a[j++];
				number += mid - i + 1;
			}
		}

		while (i <= mid)
			b[k++] = a[i++];
		while (j <= end)
			b[k++] = a[j++];
	}
	
	public static void copy(int[] a, int[] b, int begin, int end) {
		for(int i = begin; i <= end; i++)
			a[i] = b[i];
	}
	
	public static void main(String[] args) {
		int[] a = {5, 1, 2, 3, 4};
		int[] b = new int[5];
		split(a, b, 0, 4);
		System.out.println("The number of reverse pair is: " + number);
	}

}