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

admin2019-08-01 79

问题对一个具有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://www.kaotiyun.com/show/i3Ci777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

试述1946年政治协商会议的主要原因及意义。

太平天国在1853年冬颁布的纲领性文件是()。

根据1931年的威斯敏斯特法，英国()。

文件系统的主要目的是()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

在网络中计算机接收的信号是()。

计算机系统中存储器为何采用分级结构?

下列选项中，不属于网络体系结构所描述的内容是____。

19世纪初期，劳动法产生的原因有()

—Doyoumindmytakingthisseat?—______

A．差错造成患者暂时性伤害，需要采取预防措施B．患者已使用，但未造成伤害C．差错对患者的伤害可导致患者住院或延长住院时间D．差错导致患者永久性伤害E．差错导致患者死亡用药错误分为A～I级。F级错误是指()。

红硬，硬结直径6mm，则结核菌素试验反应结果应为（）

支链氨基酸治疗肝性脑病的机制是

银行本票的提示付款期限为(、)。

某剧院演出成本每场15000元，票价每张100元。编剧与制作方达成协议，票房低于30000元利润按二八分成，达到30000元则编剧可得利润的22％。某场话剧开演前．共售出297张票，问编剧这场最多可赚多少?()

2014年12月，习近平总书记在江苏考察时提出，要协调推进全面建成小康社会，全面深化改革，全面推进依法治国，全面从严治党，推动改革开放和社会主义现代化建设迈上新台阶。“四个全面”重大战略思想的意义有()。

兄弟:棠棣

A、Theyadmirethem.B、Theyfeelhappyforthem.C、Theyfeelinferiortothem.D、Theyfeeljealousandthreatened.D

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

计算机408

学硕统考专业

试述1946年政治协商会议的主要原因及意义。

太平天国在1853年冬颁布的纲领性文件是()。

根据1931年的威斯敏斯特法，英国()。

文件系统的主要目的是()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

在网络中计算机接收的信号是()。

计算机系统中存储器为何采用分级结构?

下列选项中，不属于网络体系结构所描述的内容是____。

19世纪初期，劳动法产生的原因有()

—Doyoumindmytakingthisseat?—______

A．差错造成患者暂时性伤害，需要采取预防措施B．患者已使用，但未造成伤害C．差错对患者的伤害可导致患者住院或延长住院时间D．差错导致患者永久性伤害E．差错导致患者死亡用药错误分为A～I级。F级错误是指()。

红硬，硬结直径6mm，则结核菌素试验反应结果应为（）

支链氨基酸治疗肝性脑病的机制是

银行本票的提示付款期限为(、)。

某剧院演出成本每场15000元，票价每张100元。编剧与制作方达成协议，票房低于30000元利润按二八分成，达到30000元则编剧可得利润的22％。某场话剧开演前．共售出297张票，问编剧这场最多可赚多少?()

2014年12月，习近平总书记在江苏考察时提出，要协调推进全面建成小康社会，全面深化改革，全面推进依法治国，全面从严治党，推动改革开放和社会主义现代化建设迈上新台阶。“四个全面”重大战略思想的意义有()。

兄弟:棠棣

A、Theyadmirethem.B、Theyfeelhappyforthem.C、Theyfeelinferiortothem.D、Theyfeeljealousandthreatened.D

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