首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2017-01-04
39
问题
对一个具有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
学硕统考专业
相关试题推荐
新王朝时期出现了什么类型的墓?()
评析郑和下西洋的历史条件和意义。
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
袁世凯得以复辟帝制不是因为()
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
首次提出“长期共存,互相监督”观念的是在文件()中。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
随机试题
若级数un收敛于S,则级数(un+un-1)一定().
流产最主要的原因是
A、天门冬B、人参C、斑蝥D、珍珠E、贯众目前仍然存在一药多源情况的药材是
工程交付使用前的必经程序不包括()。
我国现行建筑安装工程费中,财务费包括( )。
2015年初,A制药公司为摆脱经营困境,经股东会讨论决定从其投资方之一的甲个体工商户借款.500万元,同时与公司职工签订借款合同向本公司职工个人借款200万元,共计700万元用于流动资金周转,期限一年。上述借款年利率为7%,利息按月支付,银行同期同类贷款年
请用不超过150字的篇幅,概括出给定资料所反映的主要问题。就给定资料所反映的主要问题,用1200字左右的篇幅,自拟标题进行论述。要求中心明确,内容充实,论述深刻,有说服力。
下面是有关C语言字符数组的描述,其中错误的是()。
Questions29-24•Readthenewspaperarticlebelowaboutthecreationofnewjobs.•Choosethecorrectwordtofilleach
IntheviewoftheprimatologistSarahBlafferHrdy,theextraordinarysocialskillsareattheheartofwhatmakesushumans.T
最新回复
(
0
)