题解 | #数组中的逆序对#

用归并算法，先分后治

    int count;
    public int InversePairs(int [] array) {
        if(array!=null){
            divide(array,0,array.length-1);
        }
        return count;
    }
    public void divide(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        int mid=(start+end)/2;
        divide(array,start,mid);
        divide(array,mid+1,end);
        //治
        mergeSort(array,start,mid,end);
    }
    public void mergeSort(int[] array,int start,int mid,int end){
        int[] newArray=new int[end-start+1];
        int i=start,j=mid+1,k=0;
        while(i<=mid&&j<=end){
            if(array[i]<=array[j]){
                newArray[k++]=array[i++];
            }else{
                //若a[i]>a[j],则a[i]后面到a[mid]的数都大于a[j]
                count=(count+mid-i+1)%1000000007;
                newArray[k++]=array[j++];
            }
        }
        //没比完的部分
        while(i<=mid) newArray[k++]=array[i++];
        while(j<=end) newArray[k++]=array[j++];
        
        //覆盖原数组
        for(k=0;k<newArray.length;k++){
            array[start+k]=newArray[k];
        }
    }
}