题解 | #数组中的逆序对#c归并排序

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param data int整型一维数组 
 * @param dataLen int data数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int InversePairs(int* data, int dataLen ) {
    if(dataLen<2)//递归终止条件 剩下一个数时停止
        return 0;
    int mid=(dataLen+1)>>1;
    // write code here
    long long res=0;
    res=InversePairs(data,mid)+InversePairs(data+mid,dataLen-mid);//分割成子问题
    int *temp=malloc(sizeof(int)*dataLen);//辅助数组
    memcpy(temp, data, dataLen*sizeof(int));//数组拷贝
    int i=0,j=mid,p=0;
    while(i<mid&&j<dataLen)//排序
    {
        if(temp[i]<=temp[j])
        {
            data[p++]=temp[i++];
        }
        else
        {
            data[p++]=temp[j++];//出现逆序对，统计该数之前的个数即为逆序对个数
            res=res+mid-i;
        }
    }
    while(i<mid)
        data[p++]=temp[i++];//排序完善
    while(j<dataLen)
        data[p++]=temp[j++];
    res=res%1000000007;
    return res;
}