求逆序对 (Java 代码)

import java.util.Scanner;

public class Main {

	static int[]a;
	static int[]temp;
		public static void main(String[] args) {
			Scanner sc=new Scanner(System.in);
				int  n=sc.nextInt();
				a=new int[n];
				temp=new int[n+1];
				for (int i = 0; i < n; i++)
		               a[i]=sc.nextInt();
			  long ans = mergeSort(a, 0, n-1);
		       System.out.println(ans);
		}
		 static long  mergeSort(int []a, int left, int right) {

		    //定义终止条件
		    if (left >= right)
		        return 0;
		    //求中间值
		    int mid = (left + right) >> 1;
		    //不断进行递归，使得数组呈现有序递增
		    long count = mergeSort(a, left, mid) + mergeSort(a, mid + 1, right);
		    //i为左数组下标，j为右数组下标，pos为临时数组下标
		    int i = left, j = mid + 1;
		    int pos = 1;
		    while (i <= mid && j <= right) {
		        //如果a[i]<a[j],那么A[j]时右数组中第一个大于a[i]的元素，a在左右两数组是升序的，
		        //那么从mid+1到j-1的元素都小于a[i],则a[i]逆序数为j-mid-i
		        if (a[i] <= a[j]) {
		            temp[pos] = a[i];
		            ++i;
		            count += (j - mid) - 1;
		        }
		        else {
		            temp[pos] = a[j];
		            ++j;
		        }

		        pos++;
		    }
		    //左数组是否全部遍历
		    for (int k = i; k <= mid; k++) {
		        temp[pos++] = a[k];
		        count += (j - mid) - 1;
		    }
		    //右数组是否全部遍历
		    for (int k = j; k <= right; k++)
		        temp[pos++] = a[k];
		    pos = 1;
		    //复制数组
		    for (int k = left; k <= right; k++,pos++) {
		        a[k] = temp[pos];
		    }
		    return count;
		}
	}