37_数组中的逆序对

#include <iostream>
#include <vector>
using namespace std;
/*
题目描述:
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
*/


// 1 3 5 6 4 2 1
class Solution 
{
public:
	//最笨的方法
	int InversePairsFool(vector<int> data)
	{
		int RetCount = 0;
		for (int i = 0; i < data.size(); ++i)
		{
			for (int j = 0; j < i; j++)
			{
				if (data[j] > data[i])
				{
					++RetCount;
				}
			}
		}
		return RetCount;
	}

	int InversePairs(vector<int> data)
	{
		int RetCount = 0;
		if (data.empty())
		{
			return RetCount;
		}
		vector<int> UsedVal;
		for (int i = 0; i < data.size(); ++i)
		{
			int tmp = data[i];
			int usize = UsedVal.size() - 1;
			if (UsedVal.empty())
			{
				UsedVal.push_back(tmp);
				continue;
			}
			UsedVal.push_back(tmp);
			++usize;
			while (usize >= 1 && UsedVal[usize] < UsedVal[usize - 1])
			{
				swap(UsedVal[usize], UsedVal[usize - 1]);
				++RetCount;
				--usize;
			}
		}
		return RetCount;
	}
};

void Test()
{
	vector<int> ivec = { 1, 2, 3, 4, 7, 6, 5 };
	cout << Solution().InversePairs(ivec) << endl;
}

int main()
{
	Test();
	return 0;
}