首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2017-01-04
30
问题
对一个具有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
学硕统考专业
相关试题推荐
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
《关于建国以来党的若干历史问题的决议》的主要内容及其意义。
英国封建制度形成的过程。
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
中国第一条自行设计修建的铁路是在()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
随机试题
责任护士对肾病综合征患者给予的饮食指导中,不妥的是
号召德国要摆脱对法国文学的依赖,主张创作“市民悲剧”的是【】
伴有糖尿病的水肿患者,不宜选用
建筑材料的物理性质中属于与温度有关的性质有()。
.以下哪种管材不得用作屋面外排水的雨水管?
给水处理工艺中,设置消毒工序的目的是()。
下列情形中属于诉讼时效中断的事由是( )。
社会是变化发展的,德育不能仅传授给学生固定的价值观点,要教会学生如何分析不同的道德价值,这反映的德育模式是()。
求的渐近线.
微分方程y"-y=ex+x的特解形式为y*=()
最新回复
(
0
)