内部排序(五)：归并排序 Merge Sort (2-路归并排序)

作为数据结构的课程笔记，以便查阅。如有出错的地方，还请多多指正！

注：C++忘得太厉害了。。算法先用C实现，等之后复习了再改成C++

• 归并：将两个或两个以上的有序表组合成一个新的有序表
• 通过归并两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度

2-路归并排序 2-way Merge Sort

排序过程

思路

• 设初始序列含有$n$n个记录，则可看成$n$n个有序的子序列，每个子序列长度为1
• 两两合并，得到$\lceil n/2\rceil$⌈n/2⌉个长度为2或1的有序子序列
• 重复上一步，直至得到一个长度为$n$n的有序序列为止
  

将两个有序子序列归并成一个有序子序列

• 初始：$j=m+1, k=i$j=m+1,k=i
• 当 $i<=m\ \&\&\ j<=n$i<=m && j<=n时
  若$SR[i].key<=SR[j].key$SR[i].key<=SR[j].key， $TR[k] = SR[i++]$TR[k]=SR[i++]；否则$TR[k] = SR[j++]$TR[k]=SR[j++]；$k++$k++
• 如有剩余记录，复制
  

递归实现

• 将$SR$SR平分成两个无序子序列$SR[s..m]$SR[s..m]和SR$[m+1..t]$[m+1..t]
• 将$SR[s..m]$SR[s..m]归并为有序$TR2[s..m]$TR2[s..m]
• 将$SR[m+1..t]$SR[m+1..t]归并为有序$TR2[m+1..t]$TR2[m+1..t]
• 调用$Merge()$Merge()将有序$TR2[s..m]$TR2[s..m]和$TR2[m+1..t]$TR2[m+1..t]合并为有序

非递归实现

实现思路与递归实现相反

• 先将待排序列中有序子列的长度看作1
• 对待排序列中所有有序子列进行两两归并，此时待排序列中有序子列的长度翻倍
• 重复上一步，直至有序子列长度大于等于待排序列的长度

算法实现

• 归并两个有序序列

void Merge(Rec_t* src, Rec_t* tmp, int i, int m, int n)
{
	int j = m + 1;
	int k = i;

	while (i <= m && j <= n)
	{
		if (src[i].key <= src[j].key)
		{
			tmp[k++] = src[i++];
		}
		else {
			tmp[k++] = src[j++];
		}
	}
	if (i <= m)
	{
		memcpy(&(tmp[k]), &(src[i]), (m - i + 1) * sizeof(Rec_t));
	}
	if (j <= n)
	{
		memcpy(&(tmp[k]), &(src[j]), (n - j + 1) * sizeof(Rec_t));
	}
}

• 递归实现

//递归地进行归并排序
void M_sort_recursive(Rec_t* src, Rec_t* tmp, int s, int t)
{
	static Rec_t tmp2[MAX_SIZE + 1];

	if (s == t)
	{
		tmp[s] = src[s];
	}
	else {
		int mid = (s + t) / 2;
		
		M_sort_recursive(src, tmp2, s, mid);
		M_sort_recursive(src, tmp2, mid + 1, t);
		Merge(tmp2, tmp, s, mid, t);
	}
}

//2-路归并排序 递归实现
void Merge_sort_recursive(SqList_t* list)
{
	M_sort_recursive(list->rec, list->rec, 1, list->len);
}

• 非递归实现

//n为元素个数，len为当前有序子列的长度
//该函数对所有有序子列进行归并
void Merge_pass(Rec_t* src, Rec_t* tmp, int n, int len)
{
	int i;
	for (i = 1; i + 2 * len <= n; i += len * 2)
	{
		Merge(src, tmp, i, i + len - 1, i + 2 * len - 1);
	}
	if (i + len <= n) //归并最后两个有序子列
	{
		Merge(src, tmp, i, i + len - 1, n);
	}
	else { //归并最后一个有序子列
		memcpy(&tmp[i], &src[i], (n - i + 1) * sizeof(Rec_t));
	}
}

void Merge_sort(SqList_t* list)
{
	Rec_t* tmp = (Rec_t*)malloc((list->len + 1) * sizeof(Rec_t));
	int len = 1; //当前有序子列的长度

	while (len < list->len)
	{
		Merge_pass(list->rec, tmp, list->len, len);
		len *= 2;
		Merge_pass(tmp, list->rec, list->len, len);
		len *= 2;
	}

	free(tmp);
}

算法评价

T(n)

$T(n)=2T(\frac{n}{2}) + cn$T(n)=2T(2n​)+cn$\therefore T(n)=O(nlog_2n)$∴T(n)=O(nlog2​n)

S(n)

$S(n)=O(n)$S(n)=O(n)

是否稳定

• 稳定

总结

• 因为要在空间之间来回复制数据，效率比较低，因此一般很少利用2-路归并排序进行内部排序，特别是递归形式。它一般用在外部排序中