剑指Offer51.归并排序的应用之一——逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在归并排序的思路中，我们总是分开解决一半，最后在将两个数组合并，那么如果我们更改合并函数的代码，使它不仅仅排序，而且在特定条件下计数逆序对，这样就能计算出所有的逆序对。

排序和逆序对有什么关系？

数组中的数没有改变，只是改变位置。

假设这个数组只有两个数，我们通过归并排序知道，它满足归并的最后一道工序，如果同时满足了逆序对，那么计数器加一，并排序。

如果是一个n位数组，在一半和后一半分别计算完逆序对和排序完成后，左边的下标是整体小于右边的，无论哪边的数的位置在它那半边的位置如何改变，都不会影响它与对边那群数的比较，因为每次排序我们都是在不影响逆序对（不计数）和影响逆序对（但计数）的情况下排序的。

C++实现:

int merge_sort(vector<int>& nums, int left, int right, vector<int>& temp)
{
	//先写递归出口
	if (left == right)
	{
		return 0;
	}
	//再写递归条件
	int mid = left + (right - left) / 2;
	int num = merge_sort(nums, left, mid, temp) + merge_sort(nums, mid + 1, right, temp);//逆序对的数量 = 左边的数量+右边的数量
	//排序并查找
	int i = left;
	int j = mid + 1;
	for (int k = left; k <= right; k++)
	{
		temp.at(k) = nums.at(k);
	}
	for (int k = left; k <= right; k++)
	{
		if (i > mid)
		{
			nums.at(k) = temp.at(j++);
		}
		else if (j > right || temp.at(i) <= temp.at(j))
		{
			nums.at(k) = temp.at(i++);
		}
		else
		{
			nums.at(k) = temp.at(j++);
			num += mid - i + 1; //去掉这句，再修改一下返回值，就是归并排序
		}
	}
	return num;
}

int reversePairs(vector<int>& nums)
{
	vector<int> temp(nums.size());//辅助数组
	//先判断一下nums需不需要排序
	if (nums.size() < 2)
	{
		return 0;
	}
	return merge_sort(nums, 0, nums.size() - 1, temp);
}