首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2018-08-12
80
问题
对一个具有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/nuRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
晚清时期清帝年号的正确排序是()
第二次工业革命引起的生产关系方面最突出的变化是()。
《中美关系白皮书》
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
下列法律文件中,规定内阁对君主负责的是()。
《中国人民解放军宣言》发表的具体时间是()。
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
随机试题
试述离婚后父母对子女的探望权。
患者女,63岁。因“腰部酸痛、乏力、伴行走困难1年”来诊。患者停经7年,无特殊既往史。查体:腰部广泛压痛、叩击痛,腰椎活动受限。双下肢肌力、肌张力、感觉均正常。为明确诊断,应立即进行的检查项目包括
用正硅酸乙酯包埋时,撒干石英砂的作用是
下颌游离端局部义齿基托后缘应位于
涂料应用极广,如港湾的飞机库屋面涂成绿色,而飞机上部涂草绿色而下漆湛蓝,船舰都涂成蓝灰色,请问这属于涂料的下列哪一种作用?[2003—036]
乙公司2005年12月投入使用一台设备,账面原价为800万元,预计可使用5年,预计净残值为50万元,按双倍余额递减法计提折旧;2008年核查该台设备,首次计提减值准备40万元,并预计其尚可使用年限为2年,预计净残值为20万元,自2009年起改用年限平均法计
我国经济已经到了必须依靠深化改革、转变发展方式才能实现持续健康发展的关键时期。党的十八大指出,“深化改革是加快转变经济发展方式的关键”,并把加快完善社会主义市场经济体制和加快转变经济发展方式一同部署。新常态下,转变发展方式,必须坚定不移推进改革,努力做到量
如果使用大量的连接请求攻击计算机,使得所有可用的系统资源都被消耗殆尽,最终计算机无法再处理合法用户的请求,这种手段属于______攻击。A.拒绝服务B.口令入侵C.网络监听D.IP欺骗
为了清除列表框中指定的项目,应使用的方法是
将考生文件夹下BRUST文件夹移动到考生文件夹下TURN文件夹中,并改名为FENG。
最新回复
(
0
)