(算法)统计逆序对

题意

逆序对,如果前面的元素大于后面的元素则为一个逆序对,统计一个数组中逆序对的个数并返回

思路

思路:每次遇到左半边数组的元素大于右边数组元素,说明产生逆序对

产生逆序对的个数为:(mid - 左边数组元素当前下标 + 1)。说明有这么多个元素是大于当前右边数组这个元素。

一句话总结就是:如果右半部分数组当前元素小于左半部分数组的当前元素,那么当前左半部分数组的当前元素后面的元素(包括当前元素)都是大于右半部分数组当前元素的,也就是统计左半部分数组当前元素后面元素(包括当前元素)有多少个即可。

例如:左半部分数组为1,3,4 右半部分数组为1,2,5
那么如果当前左半部分数组元素为3,右半部分数组当前元素为2,此时产生的逆序对便是左半部分数组元素3右边所有的元素(包括3这个元素)

算法