归并排序

归并排序是建立在归并操作上的一种有效的排序算法，是采用分治法的一个典型应用。其时间复杂度为O(n log n)

归并排序的步骤如下：

划分求解：将序列分成元素个数尽量相等的两半。

递归求解：将两半元素分别排序。

合并问题：将两个有序表合并在一起

当我们要排序一个数组的时候，归并排序法首先将这个数字分成一半，然后给左边的数组排序，右边的数组给排序，之后将它们归并起来，而我们在对左边和右边的数组排序的时候，又可以将它们继续划分成一半，然排序，归并，如此递归，到一定程度的时候，我们就将这个数组分成了一个又一个的元素，此时不用排序，对它们进行一次简单的归并就可以

例；将8,6,2,3,1,5,7,4进行排序。

​ 先将数组进行划分，依次划分后如图所示

​ 然后进行第一次排序归并，如图所示

​ 依次归并

​ 直至最后一次归并完成

对于两个数组的归并，我们可以开一个临时数组来辅助我们归并，然后两个指针分别扫两个数组，按照大小归于辅助数组

具体代码实现如下

/*******************************归并算法*****************************/
#include<stdio.h>
#include<string.h>
#define ll long long
const ll maxn = 600000 + 5;
ll ans = 0;
ll a[maxn], b[maxn];
void Merge(ll sourceArr[], ll tempArr[], ll startIndex, ll midIndex, ll endIndex)
{
	ll i = startIndex, j = midIndex + 1, k = startIndex;
	while (i != midIndex + 1 && j != endIndex + 1)
	{
		if (sourceArr[i] > sourceArr[j])
			tempArr[k++] = sourceArr[j++], ans += midIndex - i + 1;//ans这一句为统计逆序数
        //类似于寻找冒泡排序的交换次数，用树状数组（BIT）可以求解，树状数组求解过程要注意不能有0的出现
		else
			tempArr[k++] = sourceArr[i++];
	}
	while (i != midIndex + 1)
		tempArr[k++] = sourceArr[i++];
	while (j != endIndex + 1)
		tempArr[k++] = sourceArr[j++];
	for (i = startIndex; i <= endIndex; i++)
		sourceArr[i] = tempArr[i];
}

//内部使用递归
void MergeSort(ll sourceArr[], ll tempArr[], ll startIndex, ll endIndex)
{
	if (startIndex >= endIndex)
		return;
	ll midIndex=(startIndex+endIndex)/2;
	MergeSort(sourceArr, tempArr, startIndex, midIndex);
	MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
	Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}

int main()
{
	int n;
	while (scanf("%d", &n) != EOF && n) {
		ans = 0;
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		for (int i = 0; i < n; i++)
			scanf("%lld", &a[i]);
		MergeSort(a, b, 0, n - 1);
		//for (int i = 0; i < n; i++)
		//	printf("%d ", a[i]);
		//printf("\n");
		printf("%lld\n", ans);
	}
	return 0;
}

例题：poj 2299

​解法：
a.归并排序求逆序对

​b.线段树动态开点求逆序对（在线段树的博客中有做简单的介绍）

关于逆序对（奇数码问题）：两个矩阵的线性数组的逆序对的奇偶相同时，它们其中一个可以通过相邻元素之间的交换变成另外一个，前提是列数为奇数；若列数不为奇数，则需判断空格位置的竖直距离与逆序对数目对2取余的情况