合并排序法求n个数的逆序对

设A[1...n]是一个包含n个不同数的数组。如果在i < j 的情况下， 有A[i] > A[j]， 则（i, j）就称为A中的一个逆序对(inversion)。

合并排序使用了分治法，每一层递归都有三个步骤：分解，解决，合并。

下面用合并排序的算法求一个数组的逆序对数。时间复杂度 ο(nlgn)。

运行结果为：1 2 3 4 5 6 7 8 9  10 arr has 45 reversions.

#include <iostream>
using namespace std;
/*合并排序的合并过程*/
void merge(int arr[], int low, int mid, int high);
/*合并排序*/
void merge_sort(int arr[], int low, int high);

/*逆序数的计数*/
int reverse_count = 0;

int main()
{
	int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	merge_sort(arr, 0, 9);
	for (int k = 0; k < 10; ++k)
	{
		cout << arr[k] << " ";
	}
	cout << "arr has " << reverse_count << " reversions." << endl;
	return 0;
}

void merge(int arr[], int low, int mid, int high)
{
	int i, j;
	
	//动态创建左右两个数组，用来暂存合并排序要合并的已排好序的两个部分
	int LeftListCount = mid - low + 1;
	int RightListCount = high - mid;

	int* LeftList = new int[LeftListCount];
	int* RightList = new int[RightListCount];

	//初始化左右两个数组
	for (i = 0; i < LeftListCount; ++i)
	{
		LeftList[i] = arr[low + i];
	}
	for (j = 0; j < RightListCount; ++j)
	{
		RightList[j] = arr[mid + j + 1];
	}
	i = 0;
	j = 0;
	int k = low;
 
	//按序将左右数组合并到主数组中
	while (i < LeftListCount && j < RightListCount)
	{
		if (LeftList[i] < RightList[j])
		{
			arr[k] = LeftList[i];
			++k;
			++i;
		}
		else
		{
			arr[k] = RightList[j];
			++k;
			++j;
 
			//若左数组某个数x比右数组y大，则x所在位置i后面的数都比y大，记录逆序
			reverse_count += LeftListCount - i;
		}
	}
	//左数组合并完毕
	if (i == LeftListCount)
	{
		while (k <= high)
		{
			arr[k] = RightList[j];
			++k;
			++j;
		}
	}
	//右数组合并完毕
	if (j == RightListCount)
	{
		while (k <= high)
		{
			arr[k] = LeftList[i];
			++k;
			++i;
		}
	}
}

//递归调用合并排序
void merge_sort(int arr[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high)/2;
		merge_sort(arr, low, mid);
		merge_sort(arr, mid+1, high);
		merge(arr, low, mid, high);
	}
}

最后

以上就是合适枫叶为你收集整理的合并排序法求n个数的逆序对的全部内容，希望文章能够帮你解决合并排序法求n个数的逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。