788. 逆序对的数量 Java题解 （归并排序）

输入样例：

6
2 3 4 5 6 1

输出样例：

5

通过分治思想，当归并排序到某一层时，假定左边序列[4, 6, 7]，右边序列为[1, 5, 9].  归并的步骤是：当左序列第一个值大于右边第一个值时，将右边第一个值加到辅助数组，此时左边序列的值均小于右边第一个数，所以将左边序列此时的个数作累加。左序列第一个值小于等于右边第一个值时，无需处理，因为此时为正序，非逆序。

import java.io.*;

public class Main {
	static int[]arr;
	static int[]temp;
	static int ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new int[n + 1];
		temp = new int[n + 1];
		String[] split = br.readLine().split(" ");
		for(int i = 1; i <= n; i++) 
			arr[i] = Integer.parseInt(split[i - 1]);
		mergeSort(1, n);
		System.out.println(ans);
	}
	
	public static void mergeSort(int l, int r) {
		if(l >= r) return;//最深层只有一个元素
		int mid = l + r >> 1;
		mergeSort(l, mid);
		mergeSort(mid + 1, r);
		
		int i = l, j = mid + 1, k = 0;//i为左边序列端点，j为右边序列端点
		while(i <= mid && j <= r) {
			if(arr[i] > arr[j]) {//当左序列的某个值大于右序列的第一个值时，
							  //表明左序列之后的值均大于这个值（左序列递增），
				ans += mid - i + 1;	//所以只要将包括左序列在内之后的左序列的个数累加即可
				temp[k++] = arr[j++];
			}else temp[k++] = arr[i++];//右边大时不需要考虑，因为是“逆序”
		} 
		while(i <= mid) temp[k++] = arr[i++];
		while(j <= r) temp[k++] = arr[j++];
		for(i = l, k = 0; i <= r; i++, k++) arr[i] = temp[k];
	}
}