归并排序思想应用之----求数组中的逆序对

数据结构与算法

求数组中的逆序对的问题我在大一的时候就遇到过，没想到三年了。还是不会。。。。问题摆在那里，你不主动去解决，那个问题永远在那，今天不会，你不去看，明天还是不会，后天还是不会，，，，。

public class Solution{
    public static int counter=0;
    public static void group(int []nums,int left,int right){
        if(left>right){
            return ;
        }
        int mid=(left+right)/2;
        group(nums,left,mid);
        group(nums,mid+1,right);
        merge(nums,left,mid,right);
    }
    public static void merge(int []nums,int left,int mid,int right){
        int []a=new int[nums.length];
        int i=left;
        int j=mid+1;
        for(int k=left;k<=right;k++){
            a[k]=nums[k];
        }
        for(int k=left;k<=right;k++){
            if(i>mid){
                a[k]=nums[j++];
            }else if(j>right){
                a[k]=nums[i++];
            }else if(a[i]>a[j]){
                a[k]=nums[j++];
                   // 因为如果a[i]此时比右数组的当前元素a[j]大，    
               // 那么左数组中a[i]后面的元素就都比a[j]大    
               // 【因为数组此时是有序数组】    用实际数字来看好像确实是这样的
                counter+=mid-i+1;
            }else {
                a[k]=nums[i++];
            }
        }
    }
}