快排的非递归实现

前提

快排的递归实现,在深度过深时会存在栈溢出的风险,所以我们需要掌握快排的非递归写法

快排的实现

单趟实现

上次我们使用了hoare的快排单趟写法,所以这次我们使用前后指针法.

前后指针法

初始状态下,初始化prev为left,cur为left+1,循环结束条件为cur <= right.  如果cur的值小于keyi,则cur与prev均向后移动,并且交换prev与cur的值;如果比keyi大,则cur向后移动.,同时,为防止prev与cur相等时交换,要写这样一句:

if (a[cur] < a[keyi] && ++prev != cur)
	Swap(&a[prev], &a[cur]);
cur++;//无论如何cur都要加加往后移动

最后实现左边都比keyi小,右边都比keyi大. 实现代码如下:

int PartSort2(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
    //挖坑法
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		cur++;//无论如何cur都要加加往后移动
	}

	Swap(&a[prev], &a[keyi]);
	return prev;//单趟结束	
}
多趟实现          

对于非递归实现,我们一般使用栈存储(属于深度优先遍历). 原理是:循环每走一次取栈顶区间,右左区间入栈.   每次入栈相当于递归的过程:每次入栈都会对左右区间进行单趟排序. 代码实现如下:

//快排非递归(递归深度太可能会栈溢出)
//用栈存储

#include "Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, &left);
	STPush(&st, &right);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort2(a, begin, end);
		//分成三段区间[begin, keyi - 1] keyi [keyi + 1, end]
		//先处理右区间
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		//再处理左区间
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);
}

       

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

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

相关文章

Android Studio Run窗口中文乱码解决办法

Android Studio Run窗口中文乱码解决办法 问题描述&#xff1a; AndroidStudio 编译项目时Run窗口中文乱码&#xff0c;如图&#xff1a; 解决方法&#xff1a; 依次打开菜单&#xff1a;Help--Edit Custom VM Options&#xff0c;打开studio64.exe.vmoptions编辑框&#xf…

CV03_mAP计算以及COCO评价标准

COCO数据集回顾&#xff1a;CV02_超强数据集&#xff1a;MSCOCO数据集的简单介绍-CSDN博客 1.1 简介 在目标检测领域中&#xff0c;mAP&#xff08;mean Average Precision&#xff0c;平均精度均值&#xff09;是一个广泛使用的性能评估指标&#xff0c;用于衡量目标检测模型…

【Unity2D 2022:Particle System】添加命中粒子特效

一、创建粒子特效游戏物体 二、修改粒子系统属性 1. 基础属性 &#xff08;1&#xff09;修改发射粒子持续时间&#xff08;Duration&#xff09;为1s &#xff08;2&#xff09;取消勾选循环&#xff08;Looping&#xff09; &#xff08;2&#xff09;修改粒子存在时间&…

数据库管理工具 -- Navicat Premium v17.0.8 特别版

软件简介 Navicat Premium 是一款功能强大的数据库管理工具&#xff0c;适用于Windows、Mac和Linux平台。它支持多种数据库&#xff0c;包括MySQL、MariaDB、SQL Server、PostgreSQL、Oracle、SQLite等。用户可以通过Navicat Premium轻松地连接到各种数据库服务器&#xff0c;…

mac怎么压缩pdf文件,mac压缩pdf文件大小不改变清晰度

在数字化时代&#xff0c;pdf文件因其良好的兼容性和稳定性&#xff0c;已经成为我们日常办公和学习中不可或缺的文件格式。然而&#xff0c;随着文件内容的增多&#xff0c;pdf文件的体积也往往会变得越来越大&#xff0c;给文件的传输和存储带来不便。本文将为你介绍几种简单…

视觉语言模型:融合视觉与语言的未来

1. 概述 视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;是能够同时处理和理解视觉&#xff08;图像&#xff09;和语言&#xff08;文本&#xff09;两种模态信息的人工智能模型。这种模型结合了计算机视觉和自然语言处理的技术&#xff0c;使得它们能够在…

第一天(点亮led灯+led灯闪烁)——Arduino uno R3 学习之旅

​ 常识: 一般智能手机的额定工作电流大约为200mA Arduino Uno板上I/0(输入/输出)引脚最大输出电流为40 mA Uno板控制器总的输出电流为200 mA 点亮LED灯 发光二极管介绍 发光二极管(Light Emitting Diode&#xff0c;简称LED)是一种能够将电能转化为光能的固态的半导体器件…

016-GeoGebra基础篇-加载项错误_使用此功能所需的服务已关闭,请检查你的隐私设置,

最近有伙伴说遇到一个问题&#xff1a;“加载项错误_使用此功能所需的服务已关闭&#xff0c;请检查你的隐私设置”&#xff0c;该怎么解决&#xff1f; 若大家也遇到同样的问题&#xff0c;建议按照我下边的步骤逐个排查下&#xff0c;基本可以解决“GeoGebra无法完美插入PPT…

计算机网络——数据链路层(以太网)

目录 局域网的数据链路层 局域网可按照网络拓扑分类 局域网与共享信道 以太网的两个主要标准 适配器与mac地址 适配器的组成与运作 MAC地址 MAC地址的详细介绍 局域网的mac地址格式 mac地址的发送顺序 单播、多播&#xff0c;广播mac地址 mac帧 如何取用…

破解宇宙终极奥秘,战胜昊天无上束缚

在幽邃的暗夜下&#xff0c;细品着夫子与昊天跨越千年的智勇交锋&#xff0c;我的思绪不禁飘向了更加深远的宇宙边际&#xff0c;回响起那些关于人类如何挑战天命、战胜上天的过往。 宇宙奥秘 在浩瀚无垠的宇宙深渊中&#xff0c;隐藏着一段超越凡尘的规则。昊天&#xff0c;…

数字信号处理中的难点

数字信号处理中的难点可以归纳为多个方面&#xff0c;这些难点不仅体现在理论知识的理解和掌握上&#xff0c;还涉及到实际工程应用中的各种问题。以下是对这些难点的详细分析&#xff1a; 一、理论知识的难点 信号与系统的基本概念&#xff1a; 理解和区分连续时间信号与离…

【搭建Nacos服务】centos7 docker从0搭建Nacos服务

前言 本次搭建基于阿里云服务器系统为&#xff08;CentOS7 Linux&#xff09;、Nacos&#xff08;2.0.3&#xff09;、Docker version 26.1.4 本次搭建基于一个新的云服务器 安装java yum install -y java-1.8.0-openjdk.x86_64安装驱动以及gcc等前置需要的命令 yum install …

树型结构数据存储实践

很多业务场景会遇到树形结构的数据&#xff0c;如公司的人员职级树、行政区划树等。 使用类似MySQL的数据库进行存储&#xff0c;需要将树形结构&#xff08;二维&#xff09;存储到行格式&#xff08;一维&#xff09;的db中。 本文介绍了树型结构数据存储的三种方式&#xf…

【6】图像分类部署

【6】图像分类部署 文章目录 前言一、将pytorch模型转为ONNX二、本地终端部署2.1. ONNX Runtime部署2.2. pytorch模型部署&#xff08;补充&#xff09; 三、使用flask的web网页部署四、微信小程序部署五、使用pyqt界面化部署总结 前言 包括将训练好的模型部署在本地终端、web…

ubuntu22 sshd设置

专栏总目录 一、安装sshd服务 sudo apt updatesudo apt install -y openssh-server 二、配置sshd 使用文本编辑器打开/etc/ssh/sshd_config sudo vi /etc/ssh/sshd_config &#xff08;一&#xff09;配置sshd服务的侦听端口 建议将ssh的侦听端口改为7000以上的端口&#…

Autosar Dcm配置-0x85服务配置及使用-基于ETAS软件

文章目录 前言Dcm配置DcmDsdDcmDsp代码实现总结前言 0x85服务用来控制DTC设置的开启和关闭。某OEM3.0架构强制支持0x85服务,本文介绍ETAS工具中的配置 Dcm配置 DcmDsd 配置0x85服务 此处配置只在扩展会话下支持(具体需要根据需求决定),两个子服务Disable为0x02,Enable…

pytest使用报错(以及解决pytest所谓的“抑制print输出”)

1. 测试类的类名问题 #codingutf-8import pytestclass TestClass1:def setup(self) -> None:print(setup)def test_01(self) -> None:print(test_01111111111111111111111)def test_02(self) -> None:print(test_02)以上述代码为例&#xff0c;如果类名是Test开头&am…

Docker部署Seata与Nacos整合

本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 Docker部署Seata与Nacos整合 Docker 部署 Seata 与 Nacos 整合 运行所使用的 demo项目地址 …

I2C接口+高度集成的电源管理芯片(PMIC)-iML1942

电源管理芯片 - iML1942是一个高度集成的电源管理IC为TFT液晶面板。它具有完整的I2C接口来编程各种参数。该设备包括一个针对AVDD的电流模式升压调节器&#xff0c;一个针对VBK1的同步升压转换器。VGL可选的反相转换器或负电荷泵调节器&#xff0c;VSS1负线性调节器&#xff0c…

【C++:类的基础认识和this指针】

C的类与C语言的struct结构体有啥区别&#xff1f; 默认的访问限定符不同 类的简要 关键字&#xff1a;class{}里面是类的主体&#xff0c;特别注意&#xff1a;{}后面的&#xff1b;不可以省略类中的变量叫做成员变量&#xff0c;类中的函数叫做成员函数类中访问有三种访问权限…