方法一(来源：http://blog.csdn.net/lyy289065406/article/details/6647346)：

//Memory Time
//3768K 2422MS 

#include
using namespace std;

const int inf=1000000000;  //10E

__int64 t; //s[]数列逆序数

void compute_t(int* s,int top,int mid,int end)
{
	int len_L=mid-top+1;
	int len_R=end-mid;

	int* left=new int[len_L+2];
	int* right=new int[len_R+2];

	int i,j;
	for(i=1;i<=len_L;i++)
		left[i]=s[top+i-1];
	left[len_L+1]=inf;   //设置无穷上界，避免比较大小时越界

	for(j=1;j<=len_R;j++)
		right[j]=s[mid+j];
	right[len_R+1]=inf;   //设置无穷上界，避免比较大小时越界

	i=j=1;
	for(int k=top;k<=end;)
		if(left[i]<=right[j])
			s[k++]=left[i++];
		else
		{
			s[k++]=right[j++];
			t+=len_L-i+1;    //计算逆序数
		}

	delete left;
	delete right;

	return;
}

void mergesort(int* s,int top,int end)
{
	if(top<end) { int mid=(top+end)/2; mergesort(s,top,mid); mergesort(s,mid+1,end); compute_t(s,top,mid,end); } return; } int main(void) { int n; //序列长度 while(cin>>n)
	{
		if(!n)
			break;

		/*Input*/

		int* s=new int[n+1];
		for(int i=1;i<=n;i++) cin>>s[i];

		/*Merge-Sort*/

		t=0;  //initial
		mergesort(s,1,n);

		/*Output*/

		printf("%I64d\n",t);

		/*Relax*/

		delete s;

	}
	return 0;
}

方法二(来源：http://blog.csdn.net/cjf_iceking/article/details/7920153)：

/********************************************************
*函数名称：Merge
*参数说明：pDataArray 无序数组；
*          int *pTempArray 临时存储合并后的序列
*          bIndex 需要合并的序列1的起始位置
*          mIndex 需要合并的序列1的结束位置
                  并且作为序列2的起始位置
*          eIndex 需要合并的序列2的结束位置
*说明：    将数组中连续的两个子序列合并为一个有序序列
*********************************************************/
void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex)
{
	int mLength = eIndex - bIndex;    //合并后的序列长度
	int i = 0;    //记录合并后序列插入数据的偏移
	int j = bIndex;    //记录子序列1插入数据的偏移
	int k = mIndex;    //记录子序列2掺入数据的偏移

	while (j < mIndex && k < eIndex)
	{
		if (pDataArray[j] <= pDataArray[k])
		{
			pTempArray[i++] = pDataArray[j];
			j++;
		}
		else
		{
			pTempArray[i++] = pDataArray[k];
			k++;
		}
	}

	if (j == mIndex)    //说明序列1已经插入完毕
		while (k < eIndex)
			pTempArray[i++] = pDataArray[k++];
	else                //说明序列2已经插入完毕
		while (j < mIndex)
			pTempArray[i++] = pDataArray[j++];

	for (i = 0; i < mLength; i++)    //将合并后序列重新放入pDataArray
		pDataArray[bIndex + i] = pTempArray[i];
}

/********************************************************
*函数名称：BottomUpMergeSort
*参数说明：pDataArray 无序数组；
*		   iDataNum为无序数据个数
*说明：    自底向上的归并排序
*********************************************************/
void BottomUpMergeSort(int* pDataArray, int iDataNum)
{
	int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);    //临时存放合并后的序列
	int length = 1;    //初始有序子序列长度为1
	while (length < iDataNum)
	{
		int i = 0;
		for (; i + 2*length < iDataNum; i += 2*length)
			Merge(pDataArray, pTempArray, i, i + length, i + 2*length);
		if (i + length < iDataNum)
			Merge(pDataArray, pTempArray, i, i + length, iDataNum);
		length *= 2;    //有序子序列长度*2
	}
	free(pTempArray);
}

35 total views, no views today