首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2023-02-06
25
问题
对一个具有7个记录的文件进行快速排序,请问:
(1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k-1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,1,2。 (2)在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1。
解析
转载请注明原文地址:https://kaotiyun.com/show/hIwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在成就测验的类型中,()是在教学过程中实施的,虽然也要让学生做题,对他们的作业评分,但其目的不是为学生划分等级,而是为了获取学生学习进步情况的有关信息,以便据此改进教学并促进学生学习。
班级教学是教学工作的基本组织形式。与个别教学组织形式相比,班级教学具有的基本特征不包括()。
学校教育是由承担教育责任的教师和接受教育的学生共同参与进行的,这是学校活动中()的特殊性。
给定资料1.2018年5月28日晚,微信自媒体公号“视觉志”发布视频类文章《凌晨3点不回家:成年人的世界是你想不到的心酸》,引发无数青年共鸣。有舆论曾质疑,自媒体贩卖焦虑“成瘾”,哪怕是“千夫所指”之下,此类话题阅读量依旧斩获“10万+”。北京
给定资料1.2018年5月28日晚,微信自媒体公号“视觉志”发布视频类文章《凌晨3点不回家:成年人的世界是你想不到的心酸》,引发无数青年共鸣。有舆论曾质疑,自媒体贩卖焦虑“成瘾”,哪怕是“千夫所指”之下,此类话题阅读量依旧斩获“10万+”。北京
长期生活不规律会导致免疫细胞和胆同醇积聚在血管壁上,变成粥样斑块。这些斑块破碎时会形成血栓,血栓有可能脱落,沿血管流动。由于牙周病菌是一种厌氧菌,而血管中有大量氧气,因此牙周病菌单独进入血管并不能存活。但是,因为免疫细胞能够有效隔绝血管中的氧气,所以人们认
深度学习是指在模仿人脑机制的神经网络中,对人工神经元的层进行了“多层处理”。深度学习不仅可以让AI(人工智能)读取大量图片,还可以让AI自主提取图片特征。得益于深度学习技术的面世,只要有大量数据,AI就能以极高的准确率进行学习,从而大幅度拓展了AI的应用范
除了探矿队员,很多矿石收藏家也对铀矿石感兴趣,因为它们实在太漂亮了。然而学过物理、化学的人都知道,不管化学上结合成什么物质,铀元素的放射性都是不会变的,那么把含铀的“毒花”放在博物馆甚至家里,真的没事吗?实际上,只要隔着一层玻璃,这些铀矿石就算放在卧室里都
在公众对不同信息源的信任层级排序中,来自政府的消息历来以权威性和________居于前列。同样是传谣,谣言经政府官微传播后破坏力更强,这________。填入画横线部分最恰当的一项是:
双向链表中有两个指针域,即prior和next,分别指向前驱及后继,设P指向链表中的一个结点,q指向一个待插入结点,现要求在P前插入q,则正确的插入为()。
随机试题
有关月经,下述错误的是
某患者在胃大部分切除后出现巨幼红细胞性贫血,其原因是对维生素B12吸收障碍。()
帕提农神庙是()。
采用小型机具施工水泥混凝土,关于振捣的说法错误的是()。
依据《市政工程施工组织设计规范》GB/T50903的规定,市政公用工程项目的施工组织设计必须经()批准后方可实施。
党的十八大报告指出,必须更加自觉地把()作为深入贯彻落实科学发展观的核心立场。
()年,国家就开始逐步推行城镇住房制度改革,开始实行向居民售房的试点。
下列事件中,属于不可能事件的是().
Oracle针对Internet/Intranet的产品是
奔腾芯片采用流水技术主要是超流水技术和
最新回复
(
0
)