当前位置: 首页 > news >正文

数据结构——排序(3):交换排序(续)

目录

一、快速排序

(1)hoare版本

①思路

②过程图示

③思考

④代码实现

⑤代码解释 

(2)挖坑法

①思路

②过程图示

③思考

④代码实现

⑤代码解释

(3)lomuto前后指针

①思路

②过程图示

③思考

④代码实现

⑤代码解释

(4)快速排序的复杂度

(5)非递归版本

①代码实现

②代码解释

二、写在最后


一、快速排序

我们上次学到了快速排序的递归方式,但是找基准值的函数(_QuickSort)如何实现呢?

(1)hoare版本

①思路

首先创建左右指针来寻找基准值。具体步骤为

一个指针从左到右找出比基准值大的数据,另一个指针从右到左找出比基准值小的数据,交换两者的位置,进入下一次循环。

②过程图示

1. 首先key指向第一个数据,left指向第二个数据,right指向最后一个数据;

2.right从右向左遍历找比key小的数据(3),left从左向右遍历找比key大的数据(7);

3.将两者交换位置;

4..right往后走一步,left往前走一步;(此时两者相遇)

5.right向左找比key小的数据(3),left向右找比key大的数据(9);(此时,left走到了right右边,跳出循环);

6.将right位置和key位置的数据交换位置,此时right位置的数据就是我们要找的key值(基准值);

7.基准值为6,此时基准值左侧的数据比其小,右侧的数据比其大。

③思考

1.若left==right是否继续循环?

 场景1:过程图示中的例子,此处不再赘述。

假设left==right时不再进行循环,则:

此时得到基准值为6,但是不满足“基准值左边都是小于它的数据,基准值右边都是大于它的数据”。 


场景2:

1. 首先key指向第一个数据,left指向第二个数据,right指向最后一个数据;

2.right从右向左遍历找比key小的数据(3),left从左向右遍历找比key大的数据(7);

3.将两者交换位置;

4.right往后走一步,left往前走一步;(此时两者相遇)

5.right找到了比基准值<=的数据(6),left找到了比基准值>=的数据(6);(此时,left走到了right右边,跳出循环);

6.将right位置和key位置的数据交换位置,此时right位置的数据就是我们要找的key值(基准值);

7.基准值为6,此时基准值左侧的数据比其小,右侧的数据比其大(或等于)。


 场景3:

1. 首先key指向第一个数据,left指向第二个数据,right指向最后一个数据;

2.right从右向左遍历找比key小的数据(3),left从左向右遍历找比key大的数据(7);

3.将两者交换位置;

4.right往后走一步,left往前走一步;(此时两者相遇)

5.right找到了比基准值小的数据(4),left找到了比基准值大的数据(7);(此时,left走到了right右边,跳出循环);

6.将right位置和key位置的数据交换位置,此时right位置的数据就是我们要找的key值(基准值);

7.基准值为6,此时基准值左侧的数据比其小,右侧的数据比其大。


通过场景1我们得出left==right仍继续循环,否则在“相遇值大于key值”的情况下会出错!


2.当left或right指向的值与key相等时,是否进行交换?

我们以数组{6,6,6,8,6,6}为例:

(1)假设left或right指向的值与key相等时交换:

在第三次交换中,left和right相遇,我们不跳出循环(思考1中已经解释)。因此得到基准值为6。 


 (2)假设left或right指向的值与key相等时不交换: 

1. 首先key指向第一个数据,left指向第二个数据,right指向最后一个数据;

2.right从右向左遍历找比key小的数据,没找到且越界了(此时left在right右边,跳出循环);

3.将right位置与key交换(right和key在同一个位置,相当于没交换);

4.基准值为6,那么没有左子树。

如果left或right指向的值与key相等时不交换,对于这种情况,分割后数据的个数为:n、n-1、n-2……并不是我们理想的类似于二叉树的分割,效率较低。


我们得出left或right指向的值与key相等时应该交换,否则效率会降低!


④代码实现

int _QuickSort(int* arr, int begin, int end)
{int left = begin;int right = end;int key = left;left++;while(left <= right){while(left <= right && arr[right] > arr[key]){right--;}while(left <= right && arr[left] < arr[key]){left++;}if(left <= right){swap(&arr[left++], &arr[right--]);}}swap(&arr[right], &arr[key]);return right;}

⑤代码解释 

首先我们让left位于第二个数据位置,right位于最后一个数据的位置,假设key为第一个数据。在left<=right的情况下,right从右向左找小于基准值的数据,left从左向右找大于基准值的数据,当两者均找到时交换位置,(不要忘记让两者继续遍历),直至left>right跳出循环。

(2)挖坑法

①思路

创建两个指针left和right,第一个数据的位置为“坑”。right从右向左找出比基准值小的数据,放入“坑”中,当前位置变成新的“坑”;接着lleft从左向右找出比基准值大的数据,放入“坑”中,当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中,当前位置即基准值。

②过程图示

我们以数组{6,1,2,7,9,3}为例:

1.首先left、hole指向第一个数据,right指向最后一个数据;

2.right找到比基准值小的数据(3),将该位置的数据放入原来的坑中,该位置变成新的“坑” ;

3.left找到比新基准值大的数据(7),将该位置的数据放入原来的坑中,该位置变成新的“坑”;

4..right找到比新基准值<=的数据(7),将该位置的数据放入原来的坑中,该位置变成新的“坑” ;

5.将最开始坑位置的数据放在当前坑中,当前数据为基准值。

③思考

1.若left==right是否继续循环?

假设left==right继续循环:

我们得到基准值为6,不满足“基准值左边都是小于它的数据,基准值右边都是大于它的数据”。


因此若left==right时不继续循环 !


 2.当left或right指向的值与key相等时,是否将其设为新的“坑”?

假设当left或right指向的值与key相等时,将其设为新的“坑”:

我们可以看到,如果将其设为新的坑,会降低效率。


因此,当left或right指向的值与key相等时,不必将其设为新的“坑”!


④代码实现

int _QuickSort(int* arr, int left, int right)
{int mid = arr[left];int hole = left;int key = arr[hole];while(left < right){while(left < right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;while(left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}

⑤代码解释

创建两个指针left和right,第一个数据的位置为“坑”。在left<right的情况下,right从右向左找出比基准值小的数据,放入“坑”中,当前位置变成新的“坑”;接着lleft从左向右找出比基准值大的数据,放入“坑”中,当前位置又变成新的“坑”。以此循环……最后将最开始“坑”位置的值放入当前位置的坑中,返回当前位置(即基准值)。

(3)lomuto前后指针

①思路

创建前后两个指针,从左向右找比基准值小的数据进行交换,使小的数据都排在基准值的左边。

②过程图示

我们以数组{6,1,2,7,9,3}为例:

1. prev指向第一个数据,cur指向第二个数据位置,key指向第一个数据位置;

2.此时cur指向的数据小于key,但是prev的下一个数据为cur;

3.让cur往后走一步;

4.此时cur指向的数据也小于key,但是prev的下一个数据仍为cur;

5.让cur继续往后走一步;

6.此时cur指向的数据小于key且prev的下一个数据不为cur,我们让prev和cur位置的数据交换位置;

7.cur继续往后走,此时越界,跳出循环;

8.让key和prev位置的数据交换;

9.此时prev位置的数据就是我们要找的基准值(prev左边的数据都比它小,prev右边的数据都比它大)。

③思考

1.当cur==right是否继续循环?

当然继续循环,在这个代码中,cur相当于在前面遍历,需要遍历到每个元素,而right位置的元素就是最后一个元素。


2.如果cur和key指向的元素相同,cur和prev是否交换?

其实两者情况的结果是一样的。


解释:

我们以数组{6,6,6,6,6}为例:

如果相等不交换:

 如果相等交换:

因此,相等交不交换都是一样的,要么递归左区间,要么递归右区间(二叉树理想下为递归左右区间)。对于全部相等的数组,复杂度都很高。 

④代码实现

int _QuickSort(int* arr, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while(cur <= right){if(arr[cur] < arr[key] && ++prev != cur)//如果prev和cur相同就不进行交换{swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[key], &arr[prev]);return prev;
}

⑤代码解释

我们先假定第一个元素是基准值,用cur来递归数组的每一个元素,如果小于(或小于等于)基准值,我们设法将它放在前面,即将其放在cur前面的prev位置(prev是一直在++的),循环进行。最后将key和prev交换位置,返回的prev即为基准值。

(4)快速排序的复杂度

1.时间复杂度:O(N*logN);

2.空间复杂度:O(logN)。

(5)非递归版本

需要借助数据结构——栈 。

①代码实现

void QuickSortNonR(int* arr, int left, int right)
{Stack st;//初始化StackInit(&st);//入栈StackPush(&st, right);StackPush(&st, left);while(!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//新数组int key = begin;int prev = begin;int cur = begin + 1;//找基准值while(cur <= end){if(arr[cur] < arr[key] && ++prev != cur){swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[key], &arr[prev]);key = prev;//右子树if(key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}//左子树if(begin < key -1){StackPush(&st, key - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

②代码解释

首先非递归实现排序,我们用到栈,也就是说用栈来模拟递归。

二、写在最后

至此,我们已经学习了插入排序、选择排序、交换排序,还剩下最后一个归并排序,我们下期见~

相关文章:

数据结构——排序(3):交换排序(续)

目录 一、快速排序 (1)hoare版本 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 &#xff08;2&#xff09;挖坑法 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代码解释 &#xff08;3&#xff09;lomuto前后指针 ①思路 ②过程图示 ③思考 ④代码实现 ⑤代…...

2024最新版本Python安装及开发环境配置(vscodepython)

python安装 去Python官网下载最新版本&#xff1a; 接下来请一步步按照图片操作&#xff1a; 这样子就安装完成了 测试Python安装是否成功 先打开终端 右键Windows徽标&#xff0c;点击终端 然后输入python&#xff0c;如果如下图所示&#xff0c;就说明安装成功&#xff0…...

机器学习的定义

机器学习 机器学习的定义 机器学习是人工智能的一个分支&#xff0c;它使计算机系统能够从经验中学习并改进&#xff0c;而无需进行明确的编程。机器学习算法分析和解释数据&#xff0c;然后使用该数据来做出预测或决策&#xff0c;随着时间的推移&#xff0c;它们会变得更加准…...

2024-08-05升级问题:Android中ScrollView嵌套listview并解决listview显示问题

问题&#xff1a; 当ScrollView嵌套ListView时&#xff0c;ListView的高度设置为wrap_content时出现ListView的高度不能完全展开&#xff0c;而只显示的第一个Item。 解决方法&#xff1a; 按item的个数乘以高度计算出listview的总高度&#xff0c;并在数据变化时直接设置lis…...

【热度文章】Java设计模式之中介者模 式

ava 中的中介者模式 中介者模式&#xff08;Mediator Pattern&#xff09;是一种行为型设计模式&#xff0c;它通过一个中介对象来封装一系列对象之间的交互&#xff0c;使这些对象之间不需要显式地相互引用&#xff0c;从而降低了对象之间的耦合度。 中介者模式的主要角色&…...

【3.0】vue3语法

【3】vue3语法 【一】vue前提 【1】定义变量 # 1 const是常量--》不允许变的 # 2 咱们用 ref包裹后&#xff0c;是个对象&#xff0c;虽然对象是常量&#xff0c;对象不能变&#xff0c;对象.value可以变化 # 3 之所以定义成const原因是&#xff0c;后期不能修改对象 【对象.…...

Navicat Monitor 荣获 2024 年 DBTA “最佳数据库性能解决方案”读者选择奖

近期&#xff0c;Navicat 以其卓越的服务器监控与深度分析能力在众多杰出竞争者中脱颖而出&#xff0c;其监控产品 Navicat Monitor 荣获了 2024 年度 DBTA 读者选择奖中的“最佳数据库性能解决方案”殊荣。该奖项不仅是对 Navicat Monitor 在数据库监控与分析领域非凡实力的权…...

[论文笔记]ZeRO: Memory Optimizations Toward Training Trillion Parameter Models

引言 今天带来ZeRO: Memory Optimizations Toward Training Trillion Parameter Models的论文笔记。 大型深度模型提供了显著的准确性提升&#xff0c;但训练数十亿到数万亿个参数是具有挑战性的。现有的解决方案&#xff0c;如数据并行和模型并行&#xff0c;存在基本的局限…...

shuashuashua

CVE-2023-2130 靶标介绍&#xff1a; 在SourceCodester采购订单管理系统1.0中发现了一项被分类为关键的漏洞。受影响的是组件GET参数处理器的文件/admin/suppliers/view_details.php中的一个未知函数。对参数id的操纵导致了SQL注入。可以远程发起攻击。 通过标靶介绍可以知道…...

k8s之HPA

目录 1.HPA 2.部署 metrics-server 3.部署 HPA 4.总结 1.HPA HPA&#xff08;Horizontal Pod Autoscaling&#xff09;Pod 水平自动伸缩&#xff0c;Kubernetes 有一个 HPA 的资源&#xff0c;HPA 可以根据 CPU 利用率自动伸缩一个 Replication Controller、 Deployment 或…...

fun状态上传,并可手动控制

文章目录 引言上传原因:矛盾点:基础工程源码: 代码实操fun状态上传fun状态下发控制 引言 上传原因: 续上一节, 我们把fun像小灯一样, 加入了预警工程, 但是我们fun其实还有其他用处, 比如我们人工手动开风扇, 排风, 所以我们需要把fun的状态上传, 然后也可以通过服务器手动控制…...

【Canvas与艺术】四扇叶结

注意&#xff1a;此是一个看起来简单&#xff0c;实际上需要细细计算调整的拓扑图。 【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head&…...

基于DVWA-Brute Force(LowMedium)的渗透测试

Brute force主要是通过爆破达到渗透目的&#xff1a; Low 查看源代码&#xff1a; <?phpif( isset( $_GET[ Login ] ) ) {// Get username$user $_GET[ username ];// Get password$pass $_GET[ password ];$pass md5( $pass );// Check the database$query "SE…...

水库大坝安全预警系统的作用

“汛情就是命令&#xff0c;防汛就是责任”&#xff0c;为了防治和减轻洪涝带来的危害&#xff0c;需要一种以预警为先导的临灾位移监测系统--水库大坝安全预警系统&#xff0c;对可能会出现的灾害进行实时远程监控&#xff0c;尽可能做到隐患早发现、早决策、早治理&#xff0…...

容器化部署ES集群

文章目录 一、ElasticSearch基本概念1、索引(Index)2、文档(Document)3、分片和副本4、映射(Mapping) 二、容器部署ElasticSearch集群三、容器部署ElasticSearch伪集群 一、ElasticSearch基本概念 1、索引(Index) 在ElasticSearch中&#xff0c;索引是文档的集合&#xff0c;类…...

使用排名前三的华为解锁工具来绕过忘记的华为锁屏密码

如果您在未使用“设置”应用的情况下将华为手机恢复出厂设置&#xff0c;同时启用了出厂重置保护 (FRP) 安全功能&#xff0c;您的华为设备将卡在帐户验证界面。您可以使用帐户凭据轻松绕过此锁定。但是&#xff0c;假设您无法回忆起旧的帐户信息。在这种情况下&#xff0c;您应…...

战神之父和前暴雪总裁都很期待《黑神话》:太酷想玩

近日《战神》之父David Jaffe在油管上发布视频&#xff0c;分享了他对《黑神话&#xff1a;悟空》的看法。他表示自己一直很关注这款游戏&#xff0c;该作的最终预告画面让他惊讶。而战斗部分更是让他大呼&#xff1a;“OMG”。 David Jaffe表示&#xff1a;“我必须要购买《黑…...

用户体验的优化:观测云在用户行为分析中的应用

在数字化商业环境中&#xff0c;用户体验的质量直接影响到品牌形象和客户忠诚度。观测云平台&#xff0c;作为一款专业的数据监控和分析工具&#xff0c;为企业提供了一个全面的解决方案&#xff0c;以深入分析用户行为并优化用户体验。 观测云的核心优势在于其能够实时处理和…...

ModelScope 部署 Flux 模型

Flux 文生图模型&#xff0c;是 Black Forest Labs 最近发布的模型&#xff0c;图片生成清晰度很高&#xff0c;模型可以在 ModelScope 上进行下载&#xff0c;本文将在本地环境中部署 Flex。使用环境如下 2080 TI 22GUbuntu 22Amd R7 2700 / 128G 启动 Model Scope 容器 Mo…...

ArkTs基础语法-声明式UI-基本概念

声明式UI语法 基本概念声明式UI描述创建组件无参数有参数 配置属性配置事件 配置子组件 基本概念 装饰器&#xff1a;用于装饰类、结构、方法及变量&#xff0c;并赋予其特殊的含义。 例如&#xff1a; Entry 有该装饰器的自定义组件&#xff0c;可以在UIAbility中使用&#xf…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...