数据结构---递归转化为非递归

递归转化为非递归

  • 前言
  • 快速排序非递归
  • 归并排序的非递归

前言

为什么要学习非递归写法呢?
当我们在用递归实现一个程序的时候,要考虑一个问题,这个程序用递归去实现,当数据量庞大的时候,会不会造成栈溢出(STACK OVERFLOW)呢?
如果没有造成还好,造成了怎么解决这个问题呢?这个时候就需要用到非递归,把一个递归实现的程序转化为非递归,是一个程序猿的基本功。

int Sum(int n)
{
	if (n == 1)
	{
		return 1;
	}
	return n + Sum(n - 1);
}

int main()
{
	int ret = Sum(100);
	cout << ret;
	return 0;
}

比如这个代码,把这个代码转化为非递归特别简单,一个for循环即可搞定。

	int ret = 0;
	for (int i = 1; i <= 100; i++)
	{
		ret += i;
	}
	cout << ret;

那么一个复杂的代码呢?比如快速排序,归并排序

快速排序非递归

快速排序在递归的时候,每次都是把区间压入栈中,
这是一个快排的代码,前后指针版本的。
在这里插入图片描述
从代码的最后,每次都是把基准值的左面先压入栈中,然后在继续划分,直到不能在划分为止,这个时候,就开始划分基准值的右面,直到完成排序。根据这个思想我们可以考虑手动模拟一个栈,然后用非递归来实现快排。


C++有库函数可以直接使用,在这里就不再写栈是怎么实现的了,不会的点击->传送门。
因为是把栈的左右区间压入,还要在定义一个pair<int,int>,不知道这个是什么的,也可以使用结构体,让结构体里面存左右区间也行

typedef pair<int, int> PII;

typedef struct Stack
{
	int l, r;
}stk;
  1. 首先,把最开始的区间压入栈中,然后以栈是否为空做为循环条件进行判断
  2. 定义临时变量存储左(begin)右(end)区间,然后用我们之前学过的快排,来模拟这一过程,快排里不在使用递归。
  3. 将区间划分,并压入栈中
  4. 重复2和3,直到循环结束,此时排序完成

代码如下

//挖坑法的快排代码
int PartSort2(int* a, int l, int r)
{
	//if (l >= r)
	//{
	//	return;
	//}

	int key = a[l];
	int hole = l;

	int bg = l;
	int ed = r;

	while (l < r)
	{
		while (l < r && a[r] >= key)
		{
			r--;
		}
		a[hole] = a[r];
		hole = r;

		while (l < r && a[l] <= key)
		{
			l++;
		}

		a[hole] = a[l];
		hole = l;

	}

	a[hole] = key;

	return hole;
}

//非递归形式实现快排
void QuickSort(int* a, int l, int r)
{

	stack<PII> stk;
	stk.push({ l, r });

	while (!stk.empty())
	{
		auto t = stk.top();
		stk.pop();
		
		int begin = t.first;
		int end = t.second;

		if (begin >= end)
		{
			continue;
		}
		
		int key_i = PartSort2(a, begin, end);

		stk.push({ begin,key_i - 1 });
		stk.push({ key_i + 1, end });

	}
}

在这里插入图片描述

归并排序的非递归

归并排序的非递归,这玩意有难度,学了好久才学会。
归并排序并不是用栈去实现的,因为归并排序是八一个序列分成n个子序列,然后归并归并归并,得到一个呈上升或者下降的序列,从这里,我们可以考虑直接从n个子序列开始归并,类似于树的后续遍历。
这里就要个问题了,归并排序需要一个临时数组,然后把临时数组赋值给原数组,从而得到有序序列,那么,这个拷贝的过程是一次性拷贝完,还是归并一次拷贝一次呢?
答案是这两种方式都可以,直接拷贝完的话呢,需要考虑的情况有点多,不推荐,归并一次拷贝一次最好。

  1. 首先定义一个gap,gap表示几几归并,刚开始肯定是一一归并,然后二二归并,四四归并
for (int i = 0; i < n; i += 2 * gap)
  1. 创建临时变量,将序列分隔开,
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;//建议自己手动模拟一下这个过程
  1. 对边界问题进行修正
if (end1 >= n || begin2 >= n)
{
	break;
}

if (end2 >= n)
{
	end2 = n - 1;
}
  1. 开始归并
while (begin1 <= end1 && begin2 <= end2)
{
	if (a[begin1] < a[begin2])
	{
		tmp[j++] = a[begin1++];
	}
	else
	{
		tmp[j++] = a[begin2++];
	}
}

while (begin1 <= end1)
{
	tmp[j++] = a[begin1++];
}

while (begin2 <= end2)
{
	tmp[j++] = a[begin2++];
}
  1. 将临时数组拷贝到原数组中
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
  1. 将gap扩大
		gap *= 2;

  1. 重复上述2,3,4,5,6操作
  2. 释放掉临时数组
	free(tmp);


代码如下

void UMergeSort(int* a, int n ,int* tmp)
{
	int gap = 1;

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

			if (end1 >= n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = i;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}


void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * (n));
	UMergeSort(a, n,tmp);

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/10634.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

代码随想录_226翻转二叉树、101对称二叉树

leetcode 226. 翻转二叉树 ​​​226. 翻转二叉树 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例 2&#xff1a; 输入&#xff1a;r…

算法训练第五十五天 | 392.判断子序列、115.不同的子序列

动态规划part15392.判断子序列题目描述思路总结115.不同的子序列题目描述思路392.判断子序列 题目链接&#xff1a;392.判断子序列 参考&#xff1a;https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html 题目描述 给定字符串 s 和 t &…

【CocosCreator入门】CocosCreator组件 | Graphics(绘制)组件

Cocos Creator 是一款流行的游戏开发引擎&#xff0c;具有丰富的组件和工具&#xff0c;其中Graphics组件允许您在游戏中绘制2D图形和几何形状&#xff0c;并通过编写脚本来控制其外观和行为。 目录 一、组件属性 二、组件方法 三、脚本示例 一、组件属性 属性功能说明lineW…

面试篇-Java并发之CAS:掌握原理、优缺点和应用场景分析,避免竞态问题

1、CAS介绍及原理 多线程中的CAS&#xff08;Compare-and-Swap&#xff09;操作是一种常见的并发控制方法&#xff0c;用于实现原子性更新共享变量的值。其核心思想是通过比较内存地址上的值和期望值是否相等来确定是否可以进行更新操作&#xff0c;从而避免多线程条件下的竞态…

用PyTorch构建基于卷积神经网络的手写数字识别模型

本文参加新星计划人工智能(Pytorch)赛道&#xff1a;https://bbs.csdn.net/topics/613989052 目录 一、MINST数据集介绍与分析 二、卷积神经网络 三、基于卷积神经网络的手写数字识别 一、MINST数据集介绍与分析 MINST数据库是机器学习领域非常经典的一个数据集&#xff0c…

动力节点王鹤SpringBoot3笔记——第八章 文章管理模块

目录 第八章 文章管理模块 8.1 配置文件 8.2 视图文件 8.3 Java代码 第八章 文章管理模块 创建新的Spring Boot项目&#xff0c;综合运用视频中的知识点&#xff0c;做一个文章管理的后台应用。 新的Spring Boot项目Lession20-BlogAdmin。Maven构建工具&#xff0c;包…

【UE4】关卡流送的demo

关卡流送功能可以将地图文件加载到内存中&#xff0c;或者从内存中卸载&#xff0c;并在游戏过程中切换地图的可视性。 这样一来&#xff0c;场景便能拆分为较小的地图块&#xff0c;并且只有相关部分才会占用资源并被渲染。 正确设置后&#xff0c;开发者便能创建大型、无缝衔…

开源流媒体服务器ZLMediaKit在Windows上运行、配置、按需拉流拉取摄像头rtsp视频流)并使用http-flv网页播放

场景 目前市面上有很多开源的流媒体服务器解决方案&#xff0c;常见的有SRS、EasyDarwin、ZLMediaKit和Monibuca等。 1、SRS GitHub - ossrs/srs: SRS is a simple, high efficiency and realtime video server, supports RTMP, WebRTC, HLS, HTTP-FLV, SRT, MPEG-DASH and …

ChatGPT批量翻译-ChatGPT批量生成多国语言

ChatGPT翻译的准吗 ChatGPT是一种基于Transformer架构的自然语言处理技术&#xff0c;其翻译准确性取决于所训练的模型和数据集的质量。在特定的语料库和训练数据下&#xff0c;ChatGPT可以实现一定程度的准确翻译。但是&#xff0c;与人工翻译相比&#xff0c;ChatGPT的翻译质…

LeetCode_101

千奇百怪的排序算法 快速排序 采用左闭右开的二分写法 归并排序 插入排序 冒泡排序 选择排序 以上代码的调用方式&#xff1a; 快速选择 在一个未排序的数组中&#xff0c;找到第 k 大的数字 快速选择一般用于求解 k-th Element 问题&#xff0c;可以在 O(n) 时间复杂度&…

Unix、UTC、GPS时间戳及转换

UTC时间 UTC时间的英文全称&#xff1a;Universal Time Coordinated&#xff0c;中文名称&#xff1a;协调世界时。俗的理解为&#xff0c;这个时间是全世界通用的&#xff0c;即全世界都公用的一个时间。可以认为格林威治时间就是时间协调时间&#xff08;GMTUTC&#xff09;&…

测试名词介绍

测试名词介绍一&#xff1a;敏捷测试1. 定义&#xff1a;2. 敏捷测试的核心&#xff1a;3. 敏捷测试的8大原则和传统测试的区别二&#xff1a;测试名词介绍瀑布模型回归测试Alpha测试Beta测试性能测试白盒测试黑盒测试灰盒测试三&#xff1a;测试流程单元测试 (unit test)集成测…

ChatGPT想干掉开发人员,做梦去吧

很多人都发现ChatGPT可以做一些代码相关的工作&#xff0c;不仅可以写一些基础的类似python、java、js的代码段&#xff0c;还可以做一定量的调优&#xff0c;于是就开始担忧起来&#xff0c;到哪天我的开发工作会不会被ChatGPT这个工具给取代了&#xff1f; 目录 1. ChatGPT…

前 K 个高频元素(力扣刷题代码随想录刷题)

给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 思路&#xff1a; 要统计元素出现频率对频率排序找出前K个高频元素首先统计元素出现的频率&#xff0c;这一类的问题可以使用map来进行统计。 然后是对频率…

【血泪建议】软件测试岗位现状,可惜之前没人告诉我,肠子都晦青了....

谈到现状&#xff0c;国内的软件测试行情目前呈现了两极分化的极端情况。 一个是早期的手工测试人员吐槽工作不好做&#xff0c;即使有工作也是外包&#xff0c;而且薪资太低&#xff1b;一方面是很多互联网企业感叹自动化测试人才难找&#xff0c;有技术的自动化测试工程师&a…

批量自动翻译软件-准确的翻译软件

现代社会&#xff0c;在全球化背景下&#xff0c;语言障碍是碍企业发展的主要因素之一。而翻译软件的出现&#xff0c;为人们跨越语言障碍带来了新的解决方案。针对翻译需要大量文字内容的情况&#xff0c;有一些能翻译大量文字的翻译软件&#xff1a; 147CGPT翻译软件特点&…

面试篇-揭开Spring Bean加载的神秘面纱

SpringBean加载完整过程 启动spring容器&#xff08;创建beanfactory&#xff09;->加载配置(注解、xml)->实例化bean(执行构造方法)->注入依赖->初始化bean&#xff08;设置属性值&#xff09;->使用->销毁 解析和读取 XML 配置文件或注解配置类&#xff0…

【C++基础】引用(引用的概念;引用的特性;常引用;使用场景:做输出型参数、大对象传参、做输出型返回值、返回大对象的引用);引用和指针的区别)

六、引用 6.1 引用的概念 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变量开辟内存空间&#xff0c;它和它引用的变量共用同一块内存空间。&#xff08;语法上&#xff09; 格式&#xff1a;类型& 引用变量名(对象名) …

用vscode运行Java程序初体验

最近开始学习Java编程了&#xff0c;以前学习过C、C 、Python&#xff0c;主要用微软的visual studio code来运行python程序&#xff0c;于是就尝试了用vscode来运行java代码&#xff0c;记录一下使用的经验&#xff0c;帮助大家少走弯路。 安装了Java的集成编辑器IDE "Ec…

Docker环境安装

Docker环境安装Docker简介Docker工作原理Docker的应用场景Docker 的优点CentOS Docker 安装与配置Docker 安装Docker 配置Docker容器概念Docker容器操作拉取镜像删除镜像容器相关命令创建并启动容器停止和恢复容器删除容器Docker简介 Docker 是一个开源的应用容器引擎&#xf…
最新文章