数据结构之排序（七）——归并排序

归并排序（Merging Sort）:假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后俩俩归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；再俩俩归并，....，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

原理

算法

递归法

代码

#include "stdafx.h"
using namespace std;
#include<iostream>
#include"stdafx.h"
//用于要排序数组个数最大值，可根据需要修改  
#define MAXSIZE 10  
typedef struct
{
	//用于存储要排序数组，r[0]用作哨兵或临时变量  
	int r[MAXSIZE + 1];
	//用于记录顺序表的长度  
	int length;
}SqList;
//交换L中数组r的下标为i和j的值  
void swap(SqList *L, int i, int j) {
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[], int TR[], int i, int m, int n)
{
	int j, k, l;
	for (j = m + 1, k = i; i <= m && j <= n; k++)	/* 将SR中记录由小到大地并入TR */
	{
		if (SR[i]<SR[j])
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	}
	if (i <= m)
	{
		for (l = 0; l <= m - i; l++)
			TR[k + l] = SR[i + l];		/* 将剩余的SR[i..m]复制到TR */
	}
	if (j <= n)
	{
		for (l = 0; l <= n - j; l++)
			TR[k + l] = SR[j + l];		/* 将剩余的SR[j..n]复制到TR */
	}
}


/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[], int TR1[], int s, int t)
{
	int m;
	int TR2[MAXSIZE + 1];
	if (s == t)
		TR1[s] = SR[s];
	else
	{
		m = (s + t) / 2;				/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
		MSort(SR, TR2, s, m);		/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
		MSort(SR, TR2, m + 1, t);	/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
		Merge(TR2, TR1, s, m, t);	/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
	}
}

/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{
	MSort(L->r, L->r, 1, L->length);
}
#define N 9
int main()
{
	int d[N] = {50,10,90,30,70,40,80,60,20};
	SqList L0;
	for (int i = 0; i <N; i++) {
		L0.r[i + 1] = d[i];
	}
	L0.length = N;
	cout<< "排序前:";
	for (int j = 1; j <= L0.length; j++) {
		cout<< L0.r[j]<<" ";
	}
	MergeSort(&L0);
	cout << "\n递归归并排序后:";
	for (int j = 1; j <= L0.length; j++) {
		cout << L0.r[j]<<" ";
	}
	cout << endl;
	return 0;
}

运行结果

算法复杂度

递归归并的时间复杂度为：O（nlogn）

归并排序是一种比较占用内存，但却效率高且稳定的算法。

算法稳定性

稳定

非递归法

代码

#include "stdafx.h"
using namespace std;
#include<iostream>
#include"stdafx.h"
//用于要排序数组个数最大值，可根据需要修改  
#define MAXSIZE 10  
typedef struct
{
	//用于存储要排序数组，r[0]用作哨兵或临时变量  
	int r[MAXSIZE + 1];
	//用于记录顺序表的长度  
	int length;
}SqList;
//交换L中数组r的下标为i和j的值  
void swap(SqList *L, int i, int j) {
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[], int TR[], int i, int m, int n)
{
	int j, k, l;
	for (j = m + 1, k = i; i <= m && j <= n; k++)	/* 将SR中记录由小到大地并入TR */
	{
		if (SR[i]<SR[j])
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	}
	if (i <= m)
	{
		for (l = 0; l <= m - i; l++)
			TR[k + l] = SR[i + l];		/* 将剩余的SR[i..m]复制到TR */
	}
	if (j <= n)
	{
		for (l = 0; l <= n - j; l++)
			TR[k + l] = SR[j + l];		/* 将剩余的SR[j..n]复制到TR */
	}
}


/* 非递归法 */
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[], int TR[], int s, int n)
{
	int i = 1;
	int j;
	while (i <= n - 2 * s + 1)
	{/* 两两归并 */
		Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
		i = i + 2 * s;
	}
	if (i<n - s + 1) /* 归并最后两个序列 */
		Merge(SR, TR, i, i + s - 1, n);
	else /* 若最后只剩下单个子序列 */
		for (j = i; j <= n; j++)
			TR[j] = SR[j];
}

/* 对顺序表L作归并非递归排序 */
void MergeSort(SqList *L)
{
	int* TR = (int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
	int k = 1;
	while (k<L->length)
	{
		MergePass(L->r, TR, k, L->length);
		k = 2 * k;/* 子序列长度加倍 */
		MergePass(TR, L->r, k, L->length);
		k = 2 * k;/* 子序列长度加倍 */
	}
}
#define N 9
int main()
{
	int d[N] = {50,10,90,30,70,40,80,60,20};
	SqList L0;
	for (int i = 0; i <N; i++) {
		L0.r[i + 1] = d[i];
	}
	L0.length = N;
	cout<< "排序前:";
	for (int j = 1; j <= L0.length; j++) {
		cout<< L0.r[j]<<" ";
	}
	MergeSort(&L0);
	cout << "\n非递归归并排序后:";
	for (int j = 1; j <= L0.length; j++) {
		cout << L0.r[j]<<" ";
	}
	cout << endl;
	return 0;
}

运行结果

算法复杂度

非递归归并排序的时间复杂度为：O（nlogn）

使用归并排序时，尽量考虑用非递归方法。

算法稳定性

稳定