对一个具有7个记录的文件进行快速排序，请问：在最好情况下需进行多少次比较?说明理由，并给出相应实例。

admin2019-08-15 52

问题对一个具有7个记录的文件进行快速排序，请问：
在最好情况下需进行多少次比较?说明理由，并给出相应实例。

选项

答案在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一l，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各文件的长度均为1，此时排序结束。由于n=7，k=3，在最好情况下，第一遍经过6次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为3)进行排序，各需要2次，这样就可将整个文件排序完毕，从而知n=7的最好情况下需进行10次比较。例如：4，7，5，6，3，l，2。

解析

转载请注明原文地址:https://kaotiyun.com/show/QKCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对一个具有7个记录的文件进行快速排序，请问：在最好情况下需进行多少次比较?说明理由，并给出相应实例。

计算机408

学硕统考专业

提出电磁感应定律的是物理学家()。

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

路由器采用()方式来发送IP分组。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

下面关于进程的叙述中，正确的是()。

在使用信号量机制实现互斥时，互斥信号量的初值一般为()：而使用信号量机制实现同步时，同步信号量的初值一般为()。

解释下列句子中加下划线的字。风吹仙袂飘飘举，犹似霓裳羽衣舞。

在温病的辨证中，斑疹隐现属于()(1996年第25题)

有降血糖和抗利尿作用的药物是

陶瓷砖按材质特性可分为()。

液化石油气喷出时，产生的静电电压可达()V，其放电火花足以引起燃烧。

证券公司营业部必须在营业场所发布股份转让的价格信息，转让日当天的价格信息发布内容有()。

本票的持票人未按照法定期限提示见票的，丧失对出票人以外的前手的追索权。()

录用特殊职位的公务员，经省级以上组织部门批准，可以简化程序或者采用其他测评办法。（）

从语法上分类，“平时、时常、刚刚、刚才"四个词中()属于名词。

WriteonANSWERSHEETTWOanoteofabout50-60wordsbasedonthefollowingsituation:Youhavegottoknowthatyourcl

对一个具有7个记录的文件进行快速排序，请问： 在最好情况下需进行多少次比较?说明理由，并给出相应实例。

计算机408

学硕统考专业

提出电磁感应定律的是物理学家()。

明清时期专制主义空前加强，据此回答问题：清代在散文方面，声势最大、影响最广的是桐城派，不属于该派的是()

路由器采用()方式来发送IP分组。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

下面关于进程的叙述中，正确的是()。

在使用信号量机制实现互斥时，互斥信号量的初值一般为()：而使用信号量机制实现同步时，同步信号量的初值一般为()。

解释下列句子中加下划线的字。风吹仙袂飘飘举，犹似霓裳羽衣舞。

在温病的辨证中，斑疹隐现属于()(1996年第25题)

有降血糖和抗利尿作用的药物是

陶瓷砖按材质特性可分为()。

液化石油气喷出时，产生的静电电压可达()V，其放电火花足以引起燃烧。

证券公司营业部必须在营业场所发布股份转让的价格信息，转让日当天的价格信息发布内容有()。

本票的持票人未按照法定期限提示见票的，丧失对出票人以外的前手的追索权。()

录用特殊职位的公务员，经省级以上组织部门批准，可以简化程序或者采用其他测评办法。（）

从语法上分类，“平时、时常、刚刚、刚才"四个词中()属于名词。

WriteonANSWERSHEETTWOanoteofabout50-60wordsbasedonthefollowingsituation:Youhavegottoknowthatyourcl

对一个具有7个记录的文件进行快速排序，请问：在最好情况下需进行多少次比较?说明理由，并给出相应实例。