。

输入一个数组#xff0c;求出这个数组中的逆序对的总数。

例如#xff0c;在数组{7,5,6,4}中#xff0c;一共存在5个逆序对#xff0c;分别是(7…题目描述在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。

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

例如在数组{7,5,6,4}中一共存在5个逆序对分别是(7,6)、(7,5)、74、(6,4)、(5,4)。

分析可以用类似归并排序的思想将数组二分直到数组中只有一个元素时此时数组逆序数组个数为0然后开始合并数组分别统计两个合并数组中逆序对的个数这样自底向上地完成数组的排序及逆序对的统计实际上是和归并排序是相同的方法。

具体地对于计算统计两个子数组的逆序对的个数我们用两个指针分别指向两个子数组的末尾并每次比较两个指针指向的数字如果第一个子数组中的数字大于第二个子数组中的数字则构成逆序对并且逆序对的数目等于第二个子数组中剩余数字的个数。

如果第一个数组中的数字小于或等于第二个数组中的数字则不构成逆序对。

每次比较我们都把较大的数字从后往前复制到一个辅助数组确保辅助数组中的数字是递增排列。

int

//****归并排序需要将辅助数组元素merge回原数组完成排序*****//}int

count

InversePairsCore(data,copy,0,length

1);//如果要保存排序后的数组可将data和copy参数交换位置即InversePairCore(copy,data,0,length

1);delete[]

InversePairsCore(copy,data,start,start

length);

//copy数组中存放已排序的子数组接下来会对copy数组作合并和排序操作//操作的结果放在data数组中作为下一次合并排序的copy数组(即两个数组是互相备份的关系)

right

InversePairsCore(copy,data,start

length