分治法-求逆序数

问题：设a1, a2,…, an是集合{1, 2, …, n}的一个排列，如果i<j且ai>aj，则序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。

#include <iostream>
#include<vector>
using namespace std;
int sum=0;
void merge_count(vector<int>&v, int s, int mid, int e, vector<int>&t);
void mergesort(vector<int>&v, int s, int e, vector<int>&t);

void mergesort(vector<int>&v, int s, int e, vector<int>&t)
{
	if (s >= e) return;//递归出口
	else {
		int mid = (s + e) / 2;//划分
		mergesort(v, s, mid, t);//递归求解子问题1
		mergesort(v, mid + 1, e, t);//递归求解子问题2
		merge_count(v, s, mid, e, t);//合并子问题的解并统计逆序数
	}
}
void merge_count(vector<int>&v, int s, int mid, int e, vector<int>&t)
{
	int i = s, j = mid + 1, index = s;
	while (i <= mid && j <= e)
	{
		if (v[i] <= v[j])
			t[index++] = v[i++];
		else
		{
			t[index++] = v[j++];
			sum += mid - i + 1;//v[i]>v[j]时为逆序数
		}
	}
	while (i <= mid)//若第一个子序列未处理完，则进行收尾
		t[index++] = v[i++];
	while (j <= e)//若第二个子序列未处理完，则进行收尾
		t[index++] = v[j++];
	for (int k = s; k <= e; k++)//将有序序列传v中
		v[k] = t[k];

}
int main()
{
	int n;
	vector<int> v, t;
	while (cin >>n)//输入非数字时结束输入
		v.push_back(n);
	int x = v.size();
	t.resize(x);//特别注意！！！
	mergesort(v, 0, v.size() - 1, t);
	cout <<"逆序数为:"<< sum << endl;
	cout << "归并排序的结果为:";
	for (auto it = v.begin(); it != v.end(); it++)
	cout << *it<<" ";
}