逆序对的个数

public class InversePairNum {

private int count = 0;
private int[] temp;//保存排好序的中间结果，再将结果拷贝到原数组

public int resolve(int[] num,int length){
    temp = new int[length];
    divideSort(num,0,length-1);
    return count;
}

private void divideSort(int[] num, int left, int right) {
    if(left < right){
        int mid = (left + right)/2;

        //分成一个一个元素
        divideSort(num,left,mid);
        divideSort(num,mid+1,right);

        mergeSort(num,left,mid,right);
    }
}

private void mergeSort(int[] num, int left, int mid, int right) {

    int leftEnd = mid;
    int rightEnd = right;

    int tempIndex = right;

    //指针从后往前移
    while (leftEnd >= left && rightEnd >= mid + 1) {
        if (num[leftEnd] > num[rightEnd]) {
            temp[tempIndex--] = num[leftEnd--];

            //不是 right - mid 右边的指针是往前挪的
            count += rightEnd - mid;
        } else {
            temp[tempIndex--] = num[rightEnd--];
        }
    }

    //剩余元素
    while (leftEnd >= left) {
        temp[tempIndex--] = num[leftEnd--];
    }

    while (rightEnd >= mid + 1) {
        temp[tempIndex--] = num[rightEnd--];
    }

    //利用临时数组temp来使得num数组左右两边都是有序的(递增的)
    for (int i = left; i <= right; i++) {
        num[i] = temp[i];
    }
}

public static void main(String[] args){
    InversePairNum test = new InversePairNum();
    int[] num = {4,6,3,1,5,7,2};
    System.out.println(test.resolve(num,num.length));
}

}