学步园

归并排序（Merge Sort）：

归并排序（Merge Sort）的基本思想是：“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。因此归并排序就是利用归并的思想来实现的，假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到 (n+1)/2个长度为2或1的有序子序列；再两两归并，….，如此重复，直至得到一个长度为n的有序序列位置，这种排序方法称为2路归并排序。

例题：假设现在我们要对数组{50, 10, 90, 30, 70, 40, 80, 60, 20}进行排序。算法实现如下：

#include <iostream>
using namespace std;

const int maxSize = 100;

/*
函数名：	Merge
函数功能：	将有序的SR[begin, middle]和SR[middle+1, end]排序后存储到TR中。
函数参数：	int SR	原数组
			int TR	目标数组
*/
void Merge(int SR[], int TR[], int begin, int middle, int end)
{
	int i, j, k;
	i = begin;
	j = middle + 1;
	k = begin;
	while (i <= middle && j <= end)
	{
		if (SR[i] <= SR[j])
		{
			TR[k] = SR[i];
			k++;
			i++;
		}
		else
		{
			TR[k] = SR[j];
			k++;
			j++;
		}
	}

	while (i <= middle)
	{
		TR[k] = SR[i];
		k++;
		i++;
	}

	while (j <= end)
	{
		TR[k] = SR[j];
		k++;
		j++;
	}
}

void MergeSort(int SR[], int TR1[], int begin, int end)
{
	if (begin == end)
	{
		TR1[begin] = SR[begin];
	}
	else
	{
		int TR2[maxSize + 1];
		int middle = begin + (end - begin) / 2;		/* 将SR[begin,end]平均分成SR[begin, middle]和SR[middle+1, t] */
		MergeSort(SR, TR2, begin, middle);			/* 递归地将SR[begin, middle]归并为有序的TR2[begin, middle] */
		MergeSort(SR, TR2, middle+1, end);			/* 递归地将SR[middle+1, end]归并为有序的TR2[middle+1, end] */
		Merge(TR2, TR1, begin, middle, end);		/* 将TR2[begin, middle]和TR2[middle+1, end]归并到TR2[begin,end] */
	}
}

int main()
{
	int array[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
	MergeSort(array, array, 0, 8);
	for (int i = 0; i < 9; i++)
	{
		cout << array[i] << " " ;
	}
	cout << endl;
}

例1：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。（剑指offer，面试题36，页数：189）

同理，我们将数组分成长度为1的子数组，然后两两结合，合并相邻的子数组，统计逆序对的数目。

也就是在Merge函数里，如果SR[i] > SR[j]，则相当于SR[i] > SR[j],SR[j-1],SR[j-2]....SR[middle+1]  故逆序对为 j-middle

#include <iostream>
using namespace std;

const int maxSize = 100;

/*
函数名：	Merge
函数功能：	将有序的SR[begin, middle]和SR[middle+1, end]排序后存储到TR中，并统计逆序对
函数参数：	int SR	原数组
			int TR	目标数组
返回值：	返回逆序对
*/
int Merge(int SR[], int TR[], int begin, int middle, int end)
{
	int i, j, k, InversePairs = 0;
	i = middle;
	j = end;
	k = end;
	while (i >= begin && j >= middle + 1)
	{
		if (SR[i] <= SR[j])
		{
			TR[k] = SR[j];
			k--;
			j--;
		}
		else
		{
			InversePairs += j - middle;
			TR[k] = SR[i];
			k--;
			i--;
		}
	}

	while (i >= begin)
	{
		TR[k] = SR[i];
		k--;
		i--;
	}

	while (j >= middle + 1)
	{
		TR[k] = SR[j];
		k--;
		j--;
	}

	return InversePairs;
}

int MergeSort(int SR[], int TR1[], int begin, int end)
{
	int left = 0, right = 0, current = 0;
	if (begin == end)
	{
		TR1[begin] = SR[begin];
	}
	else
	{
		int TR2[maxSize + 1];
		int middle = begin + (end - begin) / 2;				/* 将SR[begin,end]平均分成SR[begin, middle]和SR[middle+1, t] */
		left = MergeSort(SR, TR2, begin, middle);			/* 递归地将SR[begin, middle]归并为有序的TR2[begin, middle] */
		right = MergeSort(SR, TR2, middle+1, end);			/* 递归地将SR[middle+1, end]归并为有序的TR2[middle+1, end] */
		current = Merge(TR2, TR1, begin, middle, end);		/* 将TR2[begin, middle]和TR2[middle+1, end]归并到TR2[begin,end] */
	}
	return left + right + current;
}

int main()
{
	int array[] = {7, 5, 6, 4};
	cout << MergeSort(array, array, 0, 3) << endl;
}