数组中的逆序对

在数组中的两个数如果前面一个数大于后面的数字，则这俩个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

例如：数组{7,5,6,4}中，一共存在5个逆序对，分别是（7,6）（7,5）（7,4）（6,4）（5,4）。

有两种方法：

第一种：顺序扫描法，时间复杂度是O(n²)。代码略。

第二种：运用归并排序的方法。思想是：

把数组递归的分成子数组，统计出相邻子数组的逆序对，统计过程中需对数组进行排序，防止重复统计。代码如下：

int InversePairsCore(int* data, int* copy , int start , int end)
{
    if (start == end)
    {
        copy[start] = data[start] ;
        return 0 ;
    }
    int length = (end - start)/ 2 ;
    int left = InversePairsCore(copy, data, start, start + length);
    int right = InversePairsCore(copy, data, start + length + 1 , end);
    int i = start + length ;//i初始化为前半段最后一个数字的下标
    int j = end ;//j初始化为后半段最后一个数字的下标
    int indexCopy = end ;
    int count = 0 ;
    while (i >= start && j >= start + length + 1)
    {
        if (data[i] > data[j])
        {
            copy[indexCopy] = data[i];
            count += j - start - length ;
            i-- ;
            indexCopy-- ;
        }
        else
        {
            copy[indexCopy--] = data[j--] ;
        }
    }
    while (i >= start)
    {
        copy[indexCopy--] = data[i--];
    }
    while (j >= start + length + 1)
    {
        copy[indexCopy--] = data[j--];
    }

    return left + right + count ;     
}

int InversePairs(int* data , int length)
{
    if (data == NULL || length <= 0)
    {
        return 0 ;
    }
    int* copy = new int[length] ;
    for (int i = 0 ; i < length ; i++)
    {
        copy[i] = data[i] ;
    }
    int count =  InversePairsCore(data, copy, 0, length - 1);
    delete[] copy ;
    return count ;
}

int main()
{
    int data[] = {7,5,6,4};
    cout<<InversePairs(data, 4);
    getchar();
    return 0;
}