排序算法（二）--归并排序

归并排序：将多个有序的子序列归并成一个有序的序列

1、时间复杂度：O(NlogN)

2、空间复杂度：O(N)-->适合外部排序

3、稳定性；稳定

4、分为递归实现（自上而下）和非递归实现（自下而上）

5、算法实现：

（1）递归实现：

//5.1 归并排序（递归算法）
void Merge(int a[], int tempa[], int L, int R, int Rend)    //将一个序列前后部分归并成一个有序序列
{
	int temp = L;
	int Lend = R - 1;
	int size = Rend - L + 1;
	while (L <= Lend && R <= Rend)
	{
		if (a[L] <= a[R])
			tempa[temp++] = a[L++];
		else
			tempa[temp++] = a[R++];
	}
	while (L <= Lend)
		tempa[temp++] = a[L++];
	while (R <= Rend)
		tempa[temp++] = a[R++];
	for (int i = Rend; i != Rend - size; i--)
		a[i] = tempa[i];
}

void Msort(int a[], int tempa[], int L, int Rend)    //递归归并一个序列
{
	int center;
	if (L < Rend)
	{
		center = (L + Rend) / 2;
		Msort(a, tempa, L, center);
		Msort(a, tempa, center + 1, Rend);
		Merge(a, tempa, L, center + 1, Rend);
	}
}

void Merge_sort(int a[], int n)    //归并排序接口
{
	int *p = new int[n];
	Msort(a, p, 0, n - 1);
	delete p;
}

（2）非递归实现：

//5.2归并排序（非递归）

//不再将tempa[]中元素copy到a[]中
void Merge1(int a[], int tempa[], int L, int R, int Rend)
{
	int temp = L;
	int Lend = R - 1;
	while (L <= Lend && R <= Rend)
	{
		if (a[L] <= a[R])
			tempa[temp++] = a[L++];
		else
			tempa[temp++] = a[R++];
	}
	while (L <= Lend)
		tempa[temp++] = a[L++];
	while (R <= Rend)
		tempa[temp++] = a[R++];
}

//一趟归并
void Merge_pass(int a[], int tempa[], int n, int length)
{
	int i = 0;
	for (i; i <=(n -2*length); i += 2 * length)
	{
		Merge1(a, tempa, i, i + length, i + 2 * length - 1);
	}
	if (i + length < n)
		Merge1(a, tempa, i, i + length, n - 1);
	else
		for (int j = i; j < n; j++)
			tempa[j] = a[j];
}

//通用接口
void Merge_sort1(int a[], int n)
{
	int length = 1;
	int *p = new int[n];
	while (length<n)
	{
		Merge_pass(a, p, n, length);
		length *= 2;
		Merge_pass(p, a, n, length);
		length *= 2;
	}
	free(p);
}