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

admin2019-08-01 44

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

选项

答案在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行后=log₂(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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

尚书一职，秦置于宫禁；西汉沿置，为皇帝收发文书，传达记录诏命章奏；东汉置尚书台，“出纳王命，赋政四海，权尊势重”，成为朝廷的政务中心。这一过程反映了()

罗马法的集大成《查士丁尼民法大全》产生的时间是在()。

完整地表述电磁场理论的物理学家是()。

卡德纳斯改革的内容不包括()。

太平天国作为几千年来农民运动的高峰，所遇到的历次农民运动中不曾有过的新情况是(

对于清政府在预备立宪的过程中的做法，表述不正确的是()

武则天时期，为了管理天山以北的广大区域而设立了()。

在AOE网络中关键路径叙述正确的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

下列属于2型糖尿病的发病阶段的是

青春期自我意识中的主要矛盾不包括

根据我国民事诉讼法的有关规定，下列关于证据保全的说法错误的有：()

泊位检疫适用于()等。

在企业培训需求分析系统中，属于企业层面培训需求分析的内容有()。

下图所示UML图为___(1)，用于展示_(2)。①和②分别表示_____(3)。(3)

TheOldGateIntheMiddleAgesthevastmajorityofEuropeancitieshadwallsaroundthem.Thiswaspartlyfor(51)(变化)

Somehousesaredesignedtobesmart.Othershavesmartdesigns.AnexampleofthesecondtypeofhousewonanAwardofExcellen

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

计算机408

学硕统考专业

尚书一职，秦置于宫禁；西汉沿置，为皇帝收发文书，传达记录诏命章奏；东汉置尚书台，“出纳王命，赋政四海，权尊势重”，成为朝廷的政务中心。这一过程反映了()

罗马法的集大成《查士丁尼民法大全》产生的时间是在()。

完整地表述电磁场理论的物理学家是()。

卡德纳斯改革的内容不包括()。

太平天国作为几千年来农民运动的高峰，所遇到的历次农民运动中不曾有过的新情况是(

对于清政府在预备立宪的过程中的做法，表述不正确的是()

武则天时期，为了管理天山以北的广大区域而设立了()。

在AOE网络中关键路径叙述正确的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

下列属于2型糖尿病的发病阶段的是

青春期自我意识中的主要矛盾不包括

根据我国民事诉讼法的有关规定，下列关于证据保全的说法错误的有：()

泊位检疫适用于()等。

在企业培训需求分析系统中，属于企业层面培训需求分析的内容有()。

下图所示UML图为_______(1)，用于展示_______(2)。①和②分别表示_______(3)。(3)

TheOldGateIntheMiddleAgesthevastmajorityofEuropeancitieshadwallsaroundthem.Thiswaspartlyfor(51)(变化)

Somehousesaredesignedtobesmart.Othershavesmartdesigns.AnexampleofthesecondtypeofhousewonanAwardofExcellen

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

下图所示UML图为___(1)，用于展示_(2)。①和②分别表示_____(3)。(3)