《计算机算法设计与分析》课后练习07

news/2024/12/13 17:02:02/

Author:龙箬
Computer Application Technology
Change the World with Data and Artificial Intelligence !
CSDN@weixin_43975035
我行及我道

//算法:用A(m)划分集合A(m:p-1)
procedure PARTITION(m,p)integer m,p,i; global A(m:p-1)v = A(m); i = m //A(m)是划分元素//looploop i = i+1 until A(i) ≥ v repeat //i由左向右移//loop p = p-1 until A(p) ≤ v repeat //i由右向左移//if (i<p) thencall INTERCHANGE(A(i), A(p))else exitendifrepeatA(m) = A(p);A(p) = v //划分元素在位置p//
end PARTITION

(1) 在上述算法 P A R T I T I O N ( m , p ) PARTITION(m,p) PARTITION(m,p) 中,将 i f ( i < p ) if (i<p) if(i<p) 改为 i f ( i ≤ p ) if (i≤p) if(ip),有何优缺点?
(2) 在数据集 ( 5 , 4 , 3 , 2 , 5 , 8 , 9 ) (5,4,3,2,5,8,9) (5,4,3,2,5,8,9) 上执行这两个算法,看看他们在执行时有何不同。

解:
(1)优点:不改变所排序数据的稳定性
缺点:当 i = = p i==p i==p 时,原地置换 A [ i ] A[i] A[i] A [ p ] A[p] A[p] ,并且多进入一轮循环,然后 i > p i>p i>p 跳出循环,导致多进行一次比较及运算。

(2)当 i f ( i < p ) if (i<p) if(i<p)
5 1 , 4 , 3 , 2 , 5 2 , 8 , 9 5_1,4,3,2,5_2,8,9 514325289
[ 5 2 , 4 , 3 , 2 ] , 5 1 , [ 8 , 9 ] [5_2,4,3,2],5_1,[8,9] [52432]51[89]
[ 2 , 3 , 4 ] , 5 2 , 5 1 , [ 8 , 9 ] [2,3,4],5_2,5_1,[8,9] [234]5251[89]
2 , [ 4 , 3 ] , 5 2 , 5 1 , [ 8 , 9 ] 2,[4,3],5_2,5_1,[8,9] 2[43]5251[89]
2 , [ 3 ] , 4 , 5 2 , 5 1 , [ 8 , 9 ] 2,[3],4,5_2,5_1,[8,9] 2[3]45251[89]
2 , 3 , 4 , 5 2 , 5 1 , [ 8 , 9 ] 2,3,4,5_2,5_1,[8,9] 2345251[89]
2 , 3 , 4 , 5 2 , 5 1 , 8 , [ 9 ] 2,3,4,5_2,5_1,8,[9] 23452518[9]
2 , 3 , 4 , 5 2 , 5 1 , 8 , 9 2,3,4,5_2,5_1,8,9 234525189

(2)当 i f ( i ≤ p ) if (i≤p) if(ip)
5 1 , 4 , 3 , 2 , 5 2 , 8 , 9 5_1,4,3,2,5_2,8,9 514325289
[ 2 , 4 , 3 ] , 5 1 , [ 5 2 , 8 , 9 ] [2,4,3],5_1,[5_2,8,9] [243]51[5289]
2 , [ 4 , 3 ] , 5 1 , [ 5 2 , 8 , 9 ] 2,[4,3],5_1,[5_2,8,9] 2[43]51[5289]
2 , [ 3 ] , 4 , 5 1 , [ 5 2 , 8 , 9 ] 2,[3],4,5_1,[5_2,8,9] 2[3]451[5289]
2 , 3 , 4 , 5 1 , [ 5 2 , 8 , 9 ] 2,3,4,5_1,[5_2,8,9] 23451[5289]
2 , 3 , 4 , 5 1 , 5 2 , [ 8 , 9 ] 2,3,4,5_1,5_2,[8,9] 2345152[89]
2 , 3 , 4 , 5 1 , 5 2 , 8 , [ 9 ] 2,3,4,5_1,5_2,8,[9] 23451528[9]
2 , 3 , 4 , 5 1 , 5 2 , 8 , 9 2,3,4,5_1,5_2,8,9 234515289

参考致谢:
国科大 马丙鹏老师《计算机算法设计与分析》

如有侵权,请联系侵删
需要本实验源数据及代码的小伙伴请联系QQ:2225872659


http://www.ppmy.cn/news/46305.html

相关文章

FVM链的Themis Pro,5日ido超百万美元

交易一直是 DeFi 乃至web3领域最经久不衰的话题&#xff0c;也因此催生了众多优秀的去中心化协议&#xff0c;如 Uniswap 和 Curve。这些协议逐渐成为了整个系统的基石。 在永续合约方面&#xff0c;DYDX 的出现将 WEB2 时代的订单簿带回了web3。其链下交易的设计&#xff0c;仿…

VMware vSphere 8.0 Update 1 正式版发布 - 企业级工作负载平台

ESXi 8.0 U1 & vCenter Server 8.0 U1 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-vsphere-8-u1/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 2023-04-18&#xff0c;VMware vSphere 8.0 Update 1 正式…

IDEA插件-MavenHapler

1.安装Maven Helper Maven Helper 是 IntelliJ IDEA 中的一个插件&#xff0c;可以帮助您管理 Maven 依赖项。它可以帮助您更容易地删除不再需要的依赖项&#xff0c;查看依赖项的冲突&#xff0c;以及执行其他有关 Maven 依赖项的操作。 打开 IDEA 设置页面&#xff1a; 在插…

【SpringBoot2】SpringBoot基础篇

SpringBoot基础篇 JC-1.快速上手SpringBoot ​ 学习任意一项技术&#xff0c;首先要知道这个技术的作用是什么&#xff0c;不然学完以后&#xff0c;你都不知道什么时候使用这个技术&#xff0c;也就是技术对应的应用场景。SpringBoot技术由Pivotal团队研发制作&#xff0c;功…

HummerRisk V1.0.0:架构全面升级,开启新篇章

HummerRisk V1.0.0发布&#xff1a; HummerRisk 由 SpringBoot 单体架构升级为 SpringCloud 微服务架构&#xff0c;性能和效率显著提升。同时新增 K8s 的检测规则组和规则实现&#xff0c;并优化多个模块的设计逻辑。 HummerRisk 保持高速的迭代&#xff0c;期待您的关注。 …

嚣张|微软“光明正大”要数据,Access用户怎么办?WPS笑了

微软“光明正大”要数据 继微软“数据门”事件之后&#xff0c;微软又开始出“幺蛾子”了。 最近&#xff0c;电脑是windows11会提示&#xff1a;你的数据将在所在国家或地区之外进行处理。 最让用户感到霸道的是&#xff0c;竟然没有“跳过”按钮。只能点击继续&#xff0c;…

最近项目开发中遇到的索引优化

简单的搜索功能会使用like like语句的前导模糊查询不能使用索引&#xff0c;根据最左前缀原则&#xff0c;因为页面搜索严禁左模糊或者全模糊&#xff0c;如果需要可以使用搜索引擎来解决。 select * from doc where title like %XX&#xff1b; -- 不能使用索引 select * …

Windows特性,个人理解

Windows是一款广泛使用的操作系统&#xff0c;它具有众多强大的特性和功能&#xff0c;可以满足不同用户的各种需求。本文将介绍Windows的一些主要特性&#xff0c;包括安全性、可靠性、易用性、可定制性等方面。 一、安全性 Windows具有强大的安全性能&#xff0c;包括以下几…