首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2017-01-04
72
问题
对一个具有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
学硕统考专业
相关试题推荐
简述美苏争霸的三个阶段,并分析其影响与教训。
下列关于湘军的叙述中不正确的是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
下列关于克里斯提尼改革的叙述不正确的是()。
原始群是以()为纽带而组成的社会组织形式。
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
中国第一条自行设计修建的铁路是在()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
随机试题
对颅内肿瘤的描述正确的是
为了保证设计指导思想连续地贯彻于设计的各个阶段,一般不单独进行( )招标,由中标的设计单位承担该任务。
根据劳动合同法律制度的规定,下列关于无效劳动合同法律后果的表述中,不正确的是()。
在社会服务机构中,以没有钱作为出发点,根据机构在来年的实际需要而作出预算的是()财务预算方法。
求助者一般资料:某女,24岁,由父母陪同前来进行心理咨询,独生女。父母叙述:女儿整天上网到很晚,经常与家长吵架,脾气很暴躁。咨询师了解到的资料:求助者长得白净、漂亮,衣着得体,她自诉自己主要是情绪低落,后悔上学的时候学习不用心,只读了一
对小班幼儿进行常规教育时,下列哪一种语言描述最合适()
下列属于市场机制构成要素的是()。
ThereasonswhywomenbossareunpopularincludeallofthefollowingEXCEPTthatpeoplethink______.
Breakfastisthefirst______oftheday.
Mostpeoplecanrememberatimeintheirliveswhentheylearnedsomethingalmostbyaccident,thatis,withoutconsciously(有意识地
最新回复
(
0
)