分治算法---解决逆序数的问题

int is1[maxx],is2[maxx];// is1为原数组，is2为临时数组，n为个人定义的长度
long long Merge(int low,int mid,int high)
{
    int i=low,j=mid+1,k=low;
    long long count=0;
    while(i<=mid&&j<=high)
        if(is1[i]<=is1[j])// 此处为稳定排序的关键，不能用小于
            is2[k++]=is1[i++];
        else
        {
            is2[k++]=is1[j++];
            count+=j-k;// 每当后段的数组元素提前时，记录提前的距离
        }
    while(i<=mid)
        is2[k++]=is1[i++];
    while(j<=high)
        is2[k++]=is1[j++];
    for(i=low; i<=high; i++) // 写回原数组
        is1[i]=is2[i];
    return count;
}
long mergeSort(int a,int b)// 下标，例如数组int is[5]，全部排序的调用为mergeSort(0,4)
{
    if(a<b)
    {
        int mid=(a+b)/2;
        long count=0;
        count+=mergeSort(a,mid);
        count+=mergeSort(mid+1,b);
        count+=Merge(a,mid,b);
        return count;
    }
    return 0;
}

用来确定一串数中的逆序数的个数。逆序数：在规定的正序排列后，与正序排列相反的排列。例如：
    

逆序对：数列a[1],a[2],a[3]…中的任意两个数a[i],aj，如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对。

逆序数：一个数列中逆序对的总数。

例如：
       在  1，5，3，6，2，9, 4   这一串数中，逆序数为7.（以从小到大为正序）