C++ 计算数组中的逆序对数量

C++语言实现数组中逆序对的计算

当数组中的某一个数值位于另一个数值之前，并且其值大于后者时，这两个数值便构成一个逆序对。给定一个数组，任务是计算该数组中所有逆序对的总数量。

#include

using namespace std;
//采用归并排序的方式统计逆序对数目
int merge(int num[], int start, int middle, int end, int* temp)
{
int k = 0, i = start, j = middle + 1, count = 0;
for (; i <= middle && j <= end;)
{
if (num[i] > num[j])
{
temp[k++] = num[i++]; //按照降序的方式进行排序
count += end - j + 1; //若左半部分的元素大于右半部分的元素，则产生的逆序对数目等于右半部分剩余元素的数量
}
else
temp[k++] = num[j++];
}
while (i <= middle)
temp[k++] = num[i++];
while (j <= end)
temp[k++] = num[j++];
for (int index =