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

思路：将数组二分划分为多两个子区间，然后对两个子区间进行递归划分。直到只剩2个元素时，此时可以判断两者是否为逆序。

接着返回上层继续对比，没出现一个逆序count++。具体思路都在注释里面了。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param data int整型一维数组
 * @param dataLen int data数组长度
 * @return int整型
 */
static int count=0;//设置逆序序列为全局变量，初始值为0

//归并函数
void merge(int* array, int left, int mid, int right)
{
    //每次归并时，设置一个辅助数组，用于存放统计逆序后的有序序列
    //由于逆序已经统计，所以更改为有序序列，之后归并时再出现逆序只需要递增逆序数就行了
    int *tmpArr=(int*)malloc(sizeof(int)*(right-left+1));
    //辅助数组的当前结点下边设置为k
    int k=0;
    //start记录当前归并段的起始位置
    int start=left;
    //l_s表示左区间起始位置，r_s表示右区间起始位置
    int l_s=left,r_s=mid+1;

    //以下为归并函数的核心部分
    while(l_s<=mid&&r_s<=right)
    {   //当顺序时
        if(array[l_s]<array[r_s])
        {
            tmpArr[k++]=array[l_s++];
        }
        else//逆序时
        {
            tmpArr[k++]=array[r_s++];
            //说明：因为发生逆序时，前面l_s走过的部分都是顺序的，所以当r_s指向的元素更小时
            //此时要统计已经走过的顺序元素，与r_s构成元素形成逆序
            //因此逆序增加（mid-l_s+1）
            count=count+(mid-l_s+1);
            count%=1000000007;
        }
    }
    //当左区间未遍历完时，将左区间加入
    while(l_s<=mid)
    {
        tmpArr[k++]=array[l_s++];
    }
    //当右区间未遍历完时，将右区间加入
    while(r_s<=right)
    {
        tmpArr[k++]=array[r_s++];
    }
    //更新归并后有序数组
    for(int i=0;i<right-left+1;i++)
    {   
        //这里要从开始记录的start起始位置开始更新
        array[start++]=tmpArr[i];
    }
}
//归并的递归函数
void mergeSort(int *array,int left,int right)
{
    int mid=(left+right)/2;
    if(left<right)
    {   //对左区间递归
        mergeSort(array,left,mid);
        //对右区间递归
        mergeSort(array,mid+1,right);
        //合并区间
        merge(array,left,mid,right);
    }
}

//主函数
int InversePairs(int* data, int dataLen ) {
    //当数组只有一个或没有元素时，逆序为0，直接返回
    if(dataLen<2)
    {
        return 0;
    }
    //对数组进行归并排序，并通过全局变量count统计逆序数
    mergeSort(data,0,dataLen-1);
    //返回逆序数
    return count;
}