首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2018-08-12
96
问题
对一个具有7个记录的文件进行快速排序,请问:
(1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于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/nuRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
《论十大关系》
印加人记载事物使用的方法是()。
美国首次提出争夺世界霸权的纲领性文件是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
尚书一职,秦置于宫禁;西汉沿置,为皇帝收发文书,传达记录诏命章奏;东汉置尚书台,“出纳王命,赋政四海,权尊势重”,成为朝廷的政务中心。这一过程反映了()
下列哪两个国家是第二次工业革命的发源地和“中心”?
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用的是()。
随机试题
定金的数额由当事人约定,但不得超过主合同标的额的【】
女,50岁,颈部淋巴结肿大。活检示:B细胞性淋巴瘤。我国最常见的B细胞性淋巴瘤是
A.胸膜肺炎放线杆菌B.多杀性巴氏杆菌C.牛支原体D.支气管败血波氏菌E.牛分支杆菌黄牛,初期干咳,后期湿咳,鼻孔流出黄色黏液。取鼻腔分泌物经抗酸染色、镜检见红色杆菌。该病例最可能的病原是
逍遥散的作用是
计算机中,“数据”是一个广义的概念,包括()等多种形式。
借贷记账法起源于12世纪的()。
根据以下资料,回答下列小题。2012年,全国国内旅游人数29.57亿人次,比上年增长12.0%。其中,城镇居民19.33亿人次。2012年,全国国内旅游收入22706.22亿元人民币,比上年增长17.6%。2012年全年人境外国游客人数比上年增长
马克思指出,“社会形态发展是自然历史过程”,这是指()
SinceHenryFordturneditintoamass-marketproductacenturyago,thecarhasdeliveredmanybenefits.Ithas【C1】______econom
TheAmericanbabyboomafterthewarmadeunconvincingU.S.advicetopoorcountriesthattheyrestraintheirbirths.However,t
最新回复
(
0
)