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

admin2019-08-15 28

问题对一个具有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

学硕统考专业

中国共产党在大革命失败后，根据中国革命的新特点，明确了“工农武装割据”的思想，其核心内容不包括()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

下面元件存取速度最快的是()。

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

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

Researchintobutterflycouldhave(i)________implications,sinceknowledgeoftheiropticalandthermalpropertiesmaybe(ii)_

InKrashen’sview,acquisitionreferstothe______processleadingtothedevelopmentofcompetenceandisnotdependentonthe

于某系方某涉嫌侮辱案的被害人和附带民事诉讼原告人。根据刑事诉讼法和相关司法解释规定，下列关于于某有权委托诉讼代理人的时间的说法中正确的是()

上市公司应当在可转换公司债券期满后()内，办理完毕偿还债券余额本息的事项。

下面四位教师用各自的方法开始了高中化学第一课，其中最符合新课程理念的是()。

全国移动电话用户增长速度最快的是()如果增长趋势与上年保持一致，预计2003年年末移动电话用户约为()

下列关于死缓的说法，正确的有()。

Languageisacognitionthattrulymakesushuman.Whereasotherspeciesdocommunicatewithinnateabilitytoproducea【S1】____

Ahappymarriageapparentlyisgoodmedicine,buthostilespousesmaybeharmfultooneanother’shealth.Couplesinconflict-ri

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

计算机408

学硕统考专业

中国共产党在大革命失败后，根据中国革命的新特点，明确了“工农武装割据”的思想，其核心内容不包括()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

下面元件存取速度最快的是()。

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

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

Researchintobutterflycouldhave(i)________implications,sinceknowledgeoftheiropticalandthermalpropertiesmaybe(ii)_

InKrashen’sview,acquisitionreferstothe______processleadingtothedevelopmentofcompetenceandisnotdependentonthe

于某系方某涉嫌侮辱案的被害人和附带民事诉讼原告人。根据刑事诉讼法和相关司法解释规定，下列关于于某有权委托诉讼代理人的时间的说法中正确的是()

上市公司应当在可转换公司债券期满后()内，办理完毕偿还债券余额本息的事项。

下面四位教师用各自的方法开始了高中化学第一课，其中最符合新课程理念的是()。

全国移动电话用户增长速度最快的是()如果增长趋势与上年保持一致，预计2003年年末移动电话用户约为()

下列关于死缓的说法，正确的有()。

Languageisacognitionthattrulymakesushuman.Whereasotherspeciesdocommunicatewithinnateabilitytoproducea【S1】____

Ahappymarriageapparentlyisgoodmedicine,buthostilespousesmaybeharmfultooneanother’shealth.Couplesinconflict-ri

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