数组中的逆序对

/******************************************************************
题目：在数组中的两个数字如果前面的一个数字大于后面的数字，则这两个
数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
*******************************************************************/
/*
解题思路：
先把数组分隔成子数组，先统计子数组内部的逆序对的数目，然后再统计出两个
相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要读数组进行排
序。如果对排序算法很熟悉，我们不难发现这个排序的过程实际上就是归并排序。
*/
#include<stdio.h>

int inversePair(int* data, int* copy, int start, int end);

int inversePair(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 start = 0;
	int end =  length - 1;

	int count = inversePair(data, copy, start, end);
	return count;
}

int inversePair(int* data, int* copy, int start, int end)
{
	if(start == end)
	{
		copy[start] = data[start];
		return 0;
	}

	int midIndex = (start + end)/2;

	int left = inversePair(data,copy,start,midIndex);
	int right = inversePair(data,copy,midIndex+1,end);

	//归并
	int index1 = start;
	int index2 = midIndex+1;
	int index = start;
	int count = 0;

	while(index1 <= midIndex && index2 <= end)
	{
		if(data[index1]<data[index2])
			copy[index++] = data[index1++];
		else
		{
			copy[index++] = data[index2++];
			count += midIndex - index1 + 1;
		}
	}
	while(index1 <= midIndex)
		copy[index++] = data[index1++];

	while(index2 <= end)
		copy[index++] = data[index2++];

	//for(int i=0;i<index;i++) //必须将数组赋值放在这里，否则会导致排好的数列又复原 
     //   data[i] = copy[i]; 

	//返回数值
	return left+right+count;
}


void test()
{
	const int length = 6;
	int arr[length] = {6, 5, 4, 3, 2, 1};
	printf("%d\n",inversePair(arr,length));
}
int main()
{
	test();
	return 0;
}

/*书上的答案
int InversePairsCore(int* data, int* copy, int start, int end);

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 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);

    // i初始化为前半段最后一个数字的下标
    int i = start + length; 
    // j初始化为后半段最后一个数字的下标
    int j = end; 
    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;
        }
        else
        {
            copy[indexCopy--] = data[j--];
        }
    }

    for(; i >= start; --i)
        copy[indexCopy--] = data[i];

    for(; j >= start + length + 1; --j)
        copy[indexCopy--] = data[j];

    return left + right + count;
}
*/