首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2017-01-04
62
问题
对一个具有7个记录的文件进行快速排序，请问：
(1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log
2
(n+1)遍划分，各文件的长度均为l，此时排序结束。由于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/6QRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于闭关政策的叙述中，不正确的是()。
评述抗战的三个阶段。
《关于建国以来党的若干历史问题的决议》
1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。
1891年标志着电机发展新阶段开始的是在电能实际应用中首次采用()。
宋文帝于元嘉年间发动的对北魏的北伐战争，此战又称()。
下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界
以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
下图是三个计算机局域网A，B和C，分别包含10台，8台和5台计算机，通过路由器互联，并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61．60．21．80的互联网地址)。LANA和LANB公用一个C类IP地址
随机试题
鸟氨酸循环的中间产物是
某建筑施工单位A具备房屋建筑工程总承包特级资质，于2019年11月承建甲市大型商业广场施工工程，总建筑面积约200000m2。目前该建设工程处于主体结构施工阶段，现场使用的主要起重类机械设备有升降机2台、塔式起重机4台、物料提升机4台、汽车起重机2台。
在具体实践中，基金管理人会针对不同的基金类型、不同的认购金额设置不同的认购费率。我国()一般不收取认购费。
当外部环境遇到良好机遇时，企业可以采用()。
“岁寒三友”和“四君子”是中国古代器物、衣物和建筑上常用的装饰题材。“岁寒三友”和“四君子”中均包括()。
动作技能形成过程中期有一个明显的、暂时的停顿现象，心理学上称为()。
学校课外活动的主体部分是()。
Thefirststepinplanningamarketingstrategyforanewproductistoanalyzethebreakdownofsalesfiguresforcompetitivep
Sevenpeoplewerearrestedbecause
PASSAGKTWOWhatdoesSherryTurkleworrymost?
最新回复
(
0
)
