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

admin2019-08-01 40

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

学硕统考专业

法国学者商博良从古代铭文中的托勒密国王名字人手，通过与希腊语等其他资料对比后，成功破译了埃及象形文字。该铭文出自()

洪武八年，朱元璋仿照元朝的办法，印造()，命令民间通行，形成了钱、钞并用的货币制度。

下列选项中，控制了西域政权的是()。

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响

下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

下列关于隋唐时期货币表述准确的是()。①隋朝使用五铢钱②开元年间开始统一使用开元通宝③开元通宝是唐朝的通用货币④开元通宝是唐代以后历代王朝货币的范式

网络拓扑结构如下图所示，与C相连接的节点B，E，D的权值分别是6，5，3。如果C收到的三张矢量表分别为：试根据距离矢量路由算法给出C所构造的路由表，并给出计算过程，路由表结构如下表所示。

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

宫内节育器的避孕原理不包括：

治疗黄疸消退后湿热留恋证，首选的方剂是

保险是最普遍的合同转移方式之一,是风险管理最重要的手段之一,它属于()

在股份有限公司的新设分立方式下，公司将其()分割为两个部分以上另外设立两个公司。

保证合同的内容应包括()。[2013年11月真题]

某运输设备原值80000元，规定折旧年限8年，预计月平均行驶里程5000km，预计净残值率4％，某月实际行驶里程4000km。若按照工作量法计算，该月折旧额应是()元。[2008年真题]

有三个关系R、S和T如下则由关系R和S得到关系T的操作是

QuantityA:thestandarddeviationofx-3,x-2,x-1,x,x+1,x+2QuantityB:thestandarddeviationofy-3,y-2,y,y+1,y+2

【B1】【B10】

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

计算机408

学硕统考专业

法国学者商博良从古代铭文中的托勒密国王名字人手，通过与希腊语等其他资料对比后，成功破译了埃及象形文字。该铭文出自()

洪武八年，朱元璋仿照元朝的办法，印造()，命令民间通行，形成了钱、钞并用的货币制度。

下列选项中，控制了西域政权的是()。

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响

下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

下列关于隋唐时期货币表述准确的是()。①隋朝使用五铢钱②开元年间开始统一使用开元通宝③开元通宝是唐朝的通用货币④开元通宝是唐代以后历代王朝货币的范式

网络拓扑结构如下图所示，与C相连接的节点B，E，D的权值分别是6，5，3。如果C收到的三张矢量表分别为：试根据距离矢量路由算法给出C所构造的路由表，并给出计算过程，路由表结构如下表所示。

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

宫内节育器的避孕原理不包括：

治疗黄疸消退后湿热留恋证，首选的方剂是

保险是最普遍的合同转移方式之一,是风险管理最重要的手段之一,它属于()

在股份有限公司的新设分立方式下，公司将其()分割为两个部分以上另外设立两个公司。

保证合同的内容应包括()。[2013年11月真题]

某运输设备原值80000元，规定折旧年限8年，预计月平均行驶里程5000km，预计净残值率4％，某月实际行驶里程4000km。若按照工作量法计算，该月折旧额应是()元。[2008年真题]

有三个关系R、S和T如下则由关系R和S得到关系T的操作是

QuantityA:thestandarddeviationofx-3,x-2,x-1,x,x+1,x+2QuantityB:thestandarddeviationofy-3,y-2,y,y+1,y+2

【B1】【B10】

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