迭代归并：归并排序非递归实现解析

鸽芷咕

发布于 2023-12-31 08:06:22

1140

发布于 2023-12-31 08:06:22

文章被收录于专栏：C++干货基地C++干货基地

🎬 鸽芷咕：个人主页 🔥 个人专栏: 《数据结构&算法》

⛺️生活的理想，就是为了理想的生活!

📋 前言

归并排序的思想上我们已经全部介绍完了，但是同时也面临和快速排序一样的问题那就是递归消耗的栈帧空间太大了，所以对此我们必须掌握非递归的排序思想。

文章目录

📋 前言
一、非递归实现的思想
二、非递归实现的过程
- 2.1 非递归实现的调整
- 2.2 调整思路讲解
- 2.3 归并非递归完整代码
三、归并排序的总结
📝文章结语：

一、非递归实现的思想

归并实现的思想无非就是先将每个数都递归分割为一个小区间然后再进行排序，之后递归回溯上一个区间这时上一个区间都排好了所以可以在进行排序就这样循环上去。

既然要用非递归那么我们是不是可以这样想直接吧每个区间定义为 1 进行归并然后再来进行循环到上一组归并排序：

这样就可以利用循环来吧归并排序非递归化了

二、非递归实现的过程

好了具体思想那么我们懂了，既然要进行从最小区间 1 开始那么我们肯定需要需要定义一个 gap = 1 开始循环

然后每次 gap * = 2； 来进行调整我们的归并区间的间距进行归并
而排序的时候则又需要一个循环了来进行进行对每个区间进行归并排序
int i = 0; i < n; i += (gap*2)
为什么每次 i += (gap*2)因为每次当这个区间排完了之后就需要跳到下一个区间开始

🍸 代码演示：

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

	int gap = 1;

	while (gap < n)
	{
		for (int i = 0; i < n; i += (gap*2))
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + (2 * gap) - 1;
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{


				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			
			memcpy(a + i, tmp + i, sizeof(int) * (2*gap));
		}
		printf("\n");
		gap *= 2;
	}

	free(tmp);
}

2.1 非递归实现的调整

以上就是非递归实现的代码了，但你真的以为非递归就这样结束了？哈哈哈其实没有我们前面举例的是2的倍数来进行排序的但是当我们排序10之类的不是2的倍数就会出现越界的情况：

🔥 注：是上面我们每次第二个区间都是 i + (2 * gap) - 1 但是当不是2的整数倍来实现的话不就越界了

2.2 调整思路讲解

哦豁大家是不是看到了当第二次排序的时候 begin2 和 end2 都越界了，第三次归并的时候甚至 end2 都越界了

这其实非常简单既然第二个区间都越界的话那么是不是就不需要进行归并了，你想啊连第二个区间都不存在的话第一个区间和谁归并？

而只有 end2 越界的话咱们修正一下不就好了，只让它归并一个数

🔥 注：这里还要注意memcpy 的时候的copy大小。

以前我们进行 copy 的时候都是 2倍的gap 但是当才不是整数倍的时候就需要调整了

i 每次都是要归并的区间开头，而 end2 倍修正了之后就是区间尾了他们一相减就好了 🔥 注：相减了之后要加1，因为是闭区间。（3-0）虽然是相减了但是我们实际复制的是4个数

2.3 归并非递归完整代码

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

	int gap = 1;

	while (gap < n)
	{
		for (int i = 0; i < n; i += (gap*2))
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + (2 * gap) - 1;

			if (begin2 >= n)
				break;

			if (end2 >= n)
				end2 = n-1;
			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{


				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}

			
			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
		}
		printf("\n");
		gap *= 2;
	}


	free(tmp);
}