归并排序法求数组中的倒置数量

如果一对元素（A[i],A[j]）是倒序的，即i < j但是A[i] > A[j],则他们被称为一个倒置。设计o(nlogn)的算法来计算数组中的倒置数量。

利用归并排序实现源码如下：

#include <iostream>
#include <cassert>
using namespace std;

void Merge(int *left,int leftSize,int *right,int rightSize,int *result,int &reverseNum)
{
	int *left_end = left + leftSize;
	int *right_end = right + rightSize;
	while(left < left_end && right < right_end) {
		if(*left > *right) {
			*result++ = *right++;
			reverseNum += (left_end - left);
		} else
			*result++ = *left++;
	}
	while(left < left_end)
		*result++ = *left++;
	while(right < right_end)
		*result++ = *right++;
}

void MergeSort(int *arr,int len,int &reverseNum)
{
	if(len == 1)
		return;
	int leftSize = len / 2,rightSize = len - len / 2;
	int *left = new int[leftSize];
	int *right = new int[rightSize];
	for(int i = 0; i < leftSize; i++)
		left[i] = arr[i];
	for(int i = 0; i < rightSize; i++)
		right[i] = arr[i + leftSize];
	MergeSort(arr,leftSize,reverseNum);
	MergeSort(arr + leftSize,rightSize,reverseNum);
	Merge(left,right,arr,reverseNum);
	delete[] left;
	delete[] right;
}

int calReversePair(int *arr,int len)
{
	assert(arr);
	int reverseNum = 0;
	MergeSort(arr,len,reverseNum);
	return reverseNum;
}

int main()
{
	int a[] = {8,7,6,5,4,3,2,1};
	cout << calReversePair(a,sizeof(a) / sizeof(a[0])) << endl;
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!