// 面试题51：数组中的逆序对

// 题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组

// 成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

#include <iostream>

using namespace std;

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

int InversePairs(int* data, int length)

{

    if (data == nullptr || length < )//检测无效输入

        return ;

    int* copy = new int[length];//复制原数组

    for (int i = ; i < length; ++i)

        copy[i] = data[i];

    int count = InversePairsCore(data, copy, , length - );

    delete[] copy;

    return count;

}

int InversePairsCore(int* data, int* copy, int start, int end)//注意这里输入，永远是data去更新copy

{

    if (start == end)

    {

        copy[start] = data[start];

        return ;

    }

    int length = (end - start) / ;

    int left = InversePairsCore(copy, data, start, start + length);//然后将实参copy给形参data传参,最后copy数组完成归并排序，而原数组也被改变了

    int right = InversePairsCore(copy, data, start + length + , end);

    // i初始化为前半段最后一个数字的下标

    int i = start + length;

    // j初始化为后半段最后一个数字的下标

    int j = end;

    int indexCopy = end;

    int count = ;

    while (i >= start && j >= start + length + )//分别从两段的尾巴朝头走

    {

        if (data[i] > data[j])//如果前面的大于后面的

        {

            copy[indexCopy--] = data[i--];//赋值

            count += j - start - length;//逆序对个数加上j下标距离它所处的小段开头的距离，具体看书中推导，抛开这句和return内容，这就是归并排序

        }

        else

        {

            copy[indexCopy--] = data[j--];//后面大于前面，只用赋值，不属于逆序对情况

        }

    }

    for (; i >= start; --i)//万一j下标所处的段里元素比i的多，剩余的i段里的值直接复制

        copy[indexCopy--] = data[i];

    for (; j >= start + length + ; --j)//情况和上面的相反

        copy[indexCopy--] = data[j];

    return left + right + count;

}

// ====================测试代码====================

void Test(const char* testName, int* data, int length, int expected)

{

    if (testName != nullptr)

        printf("%s begins: ", testName);

    if (InversePairs(data, length) == expected)

        printf("Passed.\n");

    else

        printf("Failed.\n");

}

void Test1()

{

    int data[] = { , , , , , ,  };

    int expected = ;

    Test("Test1", data, sizeof(data) / sizeof(int), expected);

}

// 递减排序数组

void Test2()

{

    int data[] = { , , , , ,  };

    int expected = ;

    Test("Test2", data, sizeof(data) / sizeof(int), expected);

}

// 递增排序数组

void Test3()

{

    int data[] = { , , , , ,  };

    int expected = ;

    Test("Test3", data, sizeof(data) / sizeof(int), expected);

}

// 数组中只有一个数字

void Test4()

{

    int data[] = {  };

    int expected = ;

    Test("Test4", data, sizeof(data) / sizeof(int), expected);

}

// 数组中只有两个数字，递增排序

void Test5()

{

    int data[] = { ,  };

    int expected = ;

    Test("Test5", data, sizeof(data) / sizeof(int), expected);

}

// 数组中只有两个数字，递减排序

void Test6()

{

    int data[] = { ,  };

    int expected = ;

    Test("Test6", data, sizeof(data) / sizeof(int), expected);

}

// 数组中有相等的数字

void Test7()

{

    int data[] = { , , , ,  };

    int expected = ;

    Test("Test7", data, sizeof(data) / sizeof(int), expected);

}

void Test8()

{

    int expected = ;

    Test("Test8", nullptr, , expected);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    Test7();

    Test8();

    system("pause");

    return ;

}