排序算法之归并排序（递归和非递归版）

  个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 

 ☄： 本期重点：排序算法的递归和非递归实现

  希望大家每天都心情愉悦的学习工作。 

---

目录

 ☄： 本期重点：排序算法的递归和非递归实现

归并排序思想：

代码实现：

归并的非递归

归并排序特点：

---

 

 

 

归并排序思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

 

递归的思想：

简单而言就是把原来的范围分割为两个区间，然后让左区间有序，右区间有序，进行归并即可，但是此时的左右区间还没有有序，我们就要在进行拆分，直到区间内元素个数为一时停止，这个部分我们可以叫做拆分的过程。

 下面进行一一的合并，就是归到一个数组。

此时的数组就是有序的。 

代码实现：

递归时，我们实际的流程如下图所示：

首先，我们先把区间分割开。

 然后，利用临时数组进行归并

 

 

递归代码实现：

void _Merge(int*a, int*tmp, int begin1, int end1, int begin2, int end2)
{
	//定义两个循环变量
	int i = begin1;
	int j = begin1;
 
	//进行循环，结束条件为两个区间中一个结束
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
 
	//把没有走完的区间插入到后面
	//有两个循环，但是只会走一个
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
 
	//最后把归并完的结果拷贝回原数组
	for (; j <= end2; ++j)
	{
		a[j] = tmp[j];
	}
}
 
 
void _MergeSort(int* a, int left, int right, int* tmp)
{
	//如果区间只有一个元素就停止
	if (left >= right)
	{
		return;
	}
 
	//取区间的中间，分为两个区间
	int mid = (right + left) >> 1;
 
	//分别递归左区间和右区间
 	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);
 
 
	//此时的区间要么已经有序了，要么区间内只有一个元素。
	
	int begin1 = left, end1 = mid;
 	int begin2 = mid+1, end2 = right;
	
	//下标从left，左区间的左边开始
 
	//归并部分的代码
	_Merge(a, tmp, begin1, end1, begin2, end2);
 
}
 
void MergeSort(int* a, int n)
{
	//开辟临时数组
	int* tmp = (int *)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("MergeSort: malloc fail");
		exit(-1);
	}
 
	//排序的子函数，因为不能每次都开辟临时数组
	_MergeSort(a, 0, n - 1, tmp);
 
	//释放数组空间，并置为NULL
	free(tmp);
	tmp = NULL;
}

 

 

归并的非递归

归并排序的非递归我们可以看做是原数组直接进行合并的过程，不需要拆分，每次只需要控制循环时的区间内的元素个数即可。

 

我们先数据一个一个进行归并，在拷贝回原数组

 在两个两个归并，拷贝回原数组。

 

 最后四个四个归并，拷贝回原数组

在这个过程中我们要考虑三种情况：

1.第一个区间不够 gap 个元素

2.没有第二个区间，只有一个区间。

3.第二个区间不够 gap个元素

 

其中第一种和第二种我们可以不用进行归并了，直接跳出本轮循环，第三种情况是越界行为我们要修正最后的范围。

 

代码如下：
 

void _Merge(int*a, int*tmp, int begin1, int end1, int begin2, int end2)
{
	//定义两个循环变量
	int i = begin1;
	int j = begin1;
 
	//进行循环，结束条件为两个区间中一个结束
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
 
	//把没有走完的区间插入到后面
	//有两个循环，但是只会走一个
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
 
	//最后把归并完的结果拷贝回原数组
	for (; j <= end2; ++j)
	{
		a[j] = tmp[j];
	}
}
 
 
void MergeSortNonR(int* a, int n)
{
	//开辟临时数组
	int* tmp = (int *)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("MergeSort: malloc fail");
		exit(-1);
	}
	
	//区间的步长
	int gap = 1;
 
	//保证步长不大于数据范围
	while (gap < n)
	{
		//每个步长下，归并多少次
		for (int i = 0; i < n; i += 2*gap)
		{
			//保存左右区间的开始结束
			int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1;
			
			//如果右区间的开始处大于总的数据个数，第一区间不够gap个
			//或者不存在第二个区间，不进行归并，直接跳出循环
			if (begin2 >= n)
			{
				break;
			}
 
			//如果右区间的结束处大于数据个数，
			//表示第二个区间数据量不够gap个，越界了，修改结束位置。
			if (end2 >= n)
			{
				end2 = n-1;
			}
 
			//归并部分的代码
			_Merge(a, tmp, begin1, end1, begin2, end2);
		}
 
		//每次循环结束，gap要变为2倍
		gap *= 2;
	}
 
	//释放空间。
	free(tmp);
	tmp = NULL;
}

归并排序特点：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定