回顾快速排序

快速排序

快速排序的核心:

找到一个key

通常左边的数比key小,右边的数比key大。

找key通常有三种方法:

1.

挖坑法:

 

代码实现:

//
int _pivot(int* a, int left, int right)
{
	int begin = left, end = right;
	int index = get_mid(a, left, right);
	swap(a[index], a[begin]);
	int key = a[begin];
	int pivot = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		//swap(a[end], a[pivot]);
		a[pivot] = a[end];
		pivot = end;
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//swap(a[begin], a[pivot]);
		a[pivot] = a[begin];
		pivot = begin;
	}
	//swap(a[begin], a[pivot]);
	pivot = begin;
	a[pivot] = key;
	return pivot;
}

 该代码的注意点为:

如果a[begin]或a[end]与key相等时,key原来在key的那边,while循环后key还在原来那边。

swap交换是错误的例子。

pivot是坑,a[pivot]是图里面类似于马赛克的位置(a[pivot]是空),所以不能是交换,应该是赋值。

左右指针法:(最左侧的一列是其示例图)

 图中代码有本质差别,图一正确(左)。

 

 先end--

后end--

二者有质的区别,完全不同

前后指针法:

 

 

找到key之后的核心:

 

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

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

相关文章

动态图学习新突破!最新SOTA实现性能全面升级,效率与精度兼得

现实世界中的许多图数据是动态变化的&#xff0c;比如社交网络、交通流量等。而传统的图学习方法通常处理的是静态图&#xff0c;这就导致它缺乏处理动态变化的能力&#xff0c;在适应性方面存在局限性。 相较之下&#xff0c;动态图学习能够捕捉到图数据的动态变化&#xff0…

MuJoCo 入门教程(一)

系列文章目录 前言 一、简介 MuJoCo 是多关节接触动力学&#xff08;Multi-Joint dynamics with Contact&#xff09;的缩写。它是一个通用物理引擎&#xff0c;旨在促进机器人、生物力学、图形和动画、机器学习以及其他需要快速、准确地仿真铰接结构与环境交互的领域的研究和开…

ssm016基于 Java Web 的校园驿站管理系统+jsp

校园驿站管理系统的设计与实现 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对校园快递信息管理混乱&#xff0c;出…

阿里云优惠券如何领取使用?

阿里云是阿里巴巴旗下云计算及人工智能科技公司&#xff0c;提供云服务器、云数据库、云存储等云计算服务和云解决方案。为了吸引更多的用户&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中就包括阿里云优惠券。本文将为大家详细介绍阿里云优惠券领取方法及使用教程&a…

Nginx 基础

文章目录 Nginx概念安装下载上传安装包执行准备条件指定安装位置编译和安装启动服务创建启动脚本 linux文件目录nginx运行原理nginx配置域名概念和原理域名配置 Nginx 概念 Nginx 是一个高性能的HTTP和反向代理web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是…

211基于matlab的多类结构动力学

基于matlab的多类结构动力学&#xff0c;凸轮机构、双凸轮、弦振动模拟、阻尼振动 、四连杆机构 、套杆运动 、三根弹簧作用的振子。程序已调通&#xff0c;可直接运行。 211 matlab 结构动力学 根弹簧作用的振子 - 小红书 (xiaohongshu.com)

javaweb学习(day10-服务器渲染技术)

一、基本介绍 1.前言 目前主流的技术是 前后端分离 (比如: Spring Boot Vue/React)JSP 技术使用在逐渐减少&#xff0c;但使用少和没有使用是两个意思&#xff0c;一些老项目和中小公司还在使用 JSP&#xff0c;工作期间&#xff0c;你很有可能遇到 JSPJSP 使用在减少(但是现…

Python深度学习034:cuda的环境如何配置

文章目录 1.安装nvidia cuda驱动CMD中看一下cuda版本:下载并安装cuda驱动2.创建虚拟环境并安装pytorch的torch_cuda3.测试附录1.安装nvidia cuda驱动 CMD中看一下cuda版本: 注意: 红框的cuda版本,是你的显卡能装的最高的cuda版本,所以可以选择低于它的版本。比如我的是11…

人工智能|深度学习——基于Xception算法模型实现一个图像分类识别系统

一、Xception简介 在计算机视觉领域&#xff0c;图像识别是一个非常重要的任务&#xff0c;其应用涵盖了人脸识别、物体检测、场景理解等众多领域。随着深度学习技术的发展&#xff0c;深度卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;简称CNN&#xff…

阿赵UE学习笔记——24、动画播放控制

阿赵UE学习笔记目录   大家好&#xff0c;我是阿赵。   继续学习虚幻引擎的使用。关于UE的动画系统&#xff0c;之前学习了很多&#xff0c;包括动画合成或者动画蒙太奇等&#xff0c;实际上最后得到的都是一个动画片段。那么这些动画片段&#xff0c;是需要怎样播放控制呢…

乐观锁解决超卖问题

3.6 乐观锁解决超卖问题 修改代码方案一、 VoucherOrderServiceImpl 在扣减库存时&#xff0c;改为&#xff1a; boolean success seckillVoucherService.update().setSql("stock stock -1") //set stock stock -1.eq("voucher_id", voucherId).eq(&q…

STM32-02基于HAL库(CubeMX+MDK+Proteus)GPIO输出案例(LED流水灯)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的GPIO输出代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 在完成开发环境搭建之后&#xff0c;开始使用STM32GP…

TCP和UDP区别和使用场景

TCP 和 UDP 是计算机⽹络中两种常⽤的传输层协议&#xff0c;⽤于实现可靠传输和⽆连接传输。 TCP TCP&#xff08;Transmission Control Protocol&#xff09;是⼀种⾯向连接的、可靠的传输协议。它通过三次握⼿四次挥⼿进⾏连接和断开链接&#xff0c;保证数据的可靠性、…

H5类似Word文档输入框小记

最近一个需求在客户端编辑输入超长文本带下划线。 最开始的input、textarea无法像span一样换行pass了。柳暗无天日之际&#xff0c;被投喂了一个contenteditable 。试了一下&#xff0c;嗯... 乌龟看绿豆--对眼了。 div 加上 contenteditable 后便继承了inputEvent 开启输入模…

【“状态机” 解析UART不定长度的协议帧】

【“状态机” 解析UART不定长度的协议帧】 1. 数据帧格式2. 状态机原理3. 代码实现 通信设计中考虑协议的灵活性&#xff0c;经常把协议设计成“不定长度”。如果一个系统接收上述“不定长度”的协议帧&#xff0c;将会有一个挑战–如何高效接收与解析。一个实例如下图&#xf…

流量卡VS随身WIFI?手把手教你怎么选!流量卡和随身WiFi哪个好?流量卡和随身WiFi的区别!流量卡和随身WiFi哪个更划算?流量卡和随身WiFi怎么选?

出门在外&#xff0c;网络、流量已经成为了我们必不可少需要考虑的问题&#xff01;在选择如何获取大流量时&#xff0c;很多人都选择困难&#xff1a;是选择一张流量卡&#xff0c;还是一个随身WIFI&#xff1f; 今天&#xff0c;将从功能与形态、信号、适用场景、限制条件等多…

初阶数据结构—算法的时间复杂度和空间复杂度

第一章&#xff1a;数据结构前言&#xff08;Lesson 1&#xff09; 1. 什么是数据结构&#xff1f; 数据结构 (Data Structure) 是计算机存储、组织数据的方式&#xff0c;指相互之间存在一种或多种特定关系的 数据元素的集合。 2. 什么是算法&#xff1f; 算法(Algorithm)…

Linux学习笔记————C 语言版 LED 灯实验

这里写目录标题 一、实验程序编写二、 汇编部分实验程序编写三、C 语言部分实验程序编写四、编译下载验证 汇编 LED 灯实验中&#xff0c;我们讲解了如何使用汇编来编写 LED 灯驱动&#xff0c;实际工作中是很少用到汇编去写嵌入式驱动的&#xff0c;毕竟汇编太难&#xff0c;而…

X射线源电流电压的实际影响

在进行实际实验的时候&#xff0c;感觉X射线电流电压好像对于成像质量的影响差不多&#xff0c;分不清楚了&#xff0c;这里记录一下&#xff0c;还没探索到原因。 80kv 500uA 功率&#xff1a;40W 90kv 300uA 功率&#xff1a;27W 90kev 600uA 110v 300uA

java的警示之有危险的行为

&#x1f468;‍&#x1f4bb;作者简介&#xff1a;&#x1f468;&#x1f3fb;‍&#x1f393;告别&#xff0c;今天 &#x1f4d4;高质量专栏 &#xff1a;☕java趣味之旅 欢迎&#x1f64f;点赞&#x1f5e3;️评论&#x1f4e5;收藏&#x1f493;关注 &#x1f496;衷心的希…