首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: 在最好情况下需进行多少次比较?说明理由,并给出相应实例。
admin
2019-08-01
52
问题
对一个具有7个记录的文件进行快速排序,请问:
在最好情况下需进行多少次比较?说明理由,并给出相应实例。
选项
答案
在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行后=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,1,2。
解析
转载请注明原文地址:https://kaotiyun.com/show/i3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1922年2月,美、英、法、意、日五国通过了《五国海军条约》,规定了各国海军主力舰和航空母舰的限额,以及在东亚设置海军基地的要求等内容。该条约的缔结表明()
中国政府第一次公开提出和平解决台湾问题的方针是在()。
国共十年对峙时期,中国的经济特点包括()。①帝国主义加紧了对中国的经济侵略②民族资本主义经济有了显著发展③官僚资本迅速形成④新民主主义经济有了一定的发展
新文化运动前期的指导思想是()。
下列国家中不是不结盟运动发起者的是()。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。 据此回答问题:中共中央将战略决战的方向首先指向()
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
随机试题
关于合同形式的说法,正确的是()。
二尖瓣狭窄病人并发下列哪种心律失常最易有血栓形成()。
关于肱骨穿胸侧位,适用的病变是
降结肠癌最早常见的临床表现是()。
施工组织与规划的内容包括()。
下列关于交易所上市基金ETF的特征的说法中,正确的有()。
下面属于劳动权的是()。(2007年11月三级真题)
社会主义协商民主是中国社会主义民主政治独特优势,有利于发挥我国政治制度优越性,增强中国特色社会主义道路自信、理论自信、制度自信、文化自信,有利于
若C程序的表达式中引用了未赋初值的变量,则_______。
PoliceinthepopularresortcityVirginiaBeachrecentlybeganoperatingvideosurveillancecameraswithcontroversialfacerec
最新回复
(
0
)