学步园

暴力方法：扫描数组中的每个数，逐个比较该数字和其后面的数字的大小，若后面的数字比其小，则是一个逆序对。
改进方法：先把数组分割成子数组，先统计出子数组内部的逆序对数，然后再统计出两个相邻子数组见的逆序对数。统计逆序对的过程中，需要对数组进行排序。显然排序过程是归并排序。时间复杂度由O(n^2)降为O(nlogn),但需要O(n)的空间复杂度，是用空间换时间的做法。

代码：

#include "stdafx.h"
#include <iostream>
#include <assert.h>
using namespace std;

//合并两个排好序的数组nArr[nStart, nMid]和nArr[nMid+1, nEnd]
void Merge(int nArr[], int nStart, int nMid, int nEnd, int *pTemp, int &nCount)
{
	//设置两个游标指向两个子数组中的元素,初始状态指向尾元素
	int nCur1 = nMid;
	int nCur2 = nEnd;
	int nTempIndex = nEnd;
	//同时遍历两个子数组，依次放入临时数组中
	while ((nCur1 >= nStart) && (nCur2 >= nMid + 1))
	{
		if (nArr[nCur1] > nArr[nCur2])
		{
			nCount += nCur2 - nMid;//注意此处代码
			pTemp[nTempIndex--] = nArr[nCur1--];
		}
		else
		{
			pTemp[nTempIndex--] = nArr[nCur2--];
		}
	}

	while (nCur1 >= nStart)
	{
		pTemp[nTempIndex--] = nArr[nCur1--];
	}

	while (nCur2 >= nMid+1)
	{
		pTemp[nTempIndex--] = nArr[nCur2--];
	}

	//将临时数组中的元素赋值到原数组中
 	for (int i=nStart; i<=nEnd; i++)
 	{
 		nArr[i] = pTemp[i];
 	}
}

//归并排序
void ReverseOrderCount(int nArr[], int nStart, int nEnd, int *pTemp, int &nCount)
{
	assert(nArr != NULL && nStart >= 0 && nEnd >= 0);

	if (nStart < nEnd)
	{
		int nMid = (nStart + nEnd) >> 1;
		ReverseOrderCount(nArr, nStart, nMid, pTemp, nCount);//对数组的前半部分进行归并排序
		ReverseOrderCount(nArr, nMid+1, nEnd, pTemp, nCount);//对数组的后半部分进行归并排序
		Merge(nArr, nStart, nMid, nEnd, pTemp, nCount);//合并两个排好序的数组
	}
}

//求数组中的逆序对
int ReverseOrderCount(int nArr[], int nLength)
{
    if (nArr == NULL || nLength < 0)
    {
		return 0;
    }

	//申请一个长度相等的临时数组
	int *nTemp = new int [nLength];
	int nCount = 0;

	ReverseOrderCount(nArr, 0, nLength-1, nTemp, nCount);
	delete[] nTemp;
	nTemp = NULL;
	return nCount;
}

//打印数组中的逆序对数和排好序的数组
 void PrintMessage(int nArr[], int nLength)
 {
	 cout << "逆序对的个数：" << ReverseOrderCount(nArr,nLength) << endl;
	 cout << "排好序的数组：";
	 for (int i=0; i<nLength; i++)
	 {
		 cout << nArr[i] << " ";
	 }
	 cout << endl << endl;
 }

int _tmain(int argc, _TCHAR* argv[])
{
	//未排好序的数组
	int nArr1[5] = {7,5,6,4,8};
	PrintMessage(nArr1, 5);	

	//递增数组
	int nArr2[5] = {4,5,6,7,8};
	PrintMessage(nArr2, 5);	

	//递减数组
	int nArr3[5] = {8,7,6,5,4};
	PrintMessage(nArr3, 5);	

	//有重复数字的数组
	int nArr4[5] = {7,4,8,4,8};
	PrintMessage(nArr4, 5);	

	//只有两个数字的数字
	int nArr5[2] = {7,5};
	PrintMessage(nArr5, 2);	

	int nArr6[1] = {4};
	PrintMessage(nArr6, 1);

	system("pause");
	return 0;
}

运行结果：