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

admin2023-02-06 73

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

选项

答案(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k-1，显然，第一遍划分得到两个长度均为[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，1，2。 (2)在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n²)，反而不快了。对于n=7的记录文件，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，1。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

任何一个班里都可能有学困生，学困生的转化是教师尤其是班主任的一项重要工作。下列不属于学困生特征的是()。

做阅读题的时候带着问题去看文章，运用的是()。

课程在纵向结构上的表现形式有()。

正方体切掉一块后剩余部分如下图左侧所示，右侧哪一项是其切去部分的形状?

问题流主要关注于问题的()

烟花爆竹安全生产措施主要包括制造过程措施和生产过程措施两类。下列防止烟花爆竹火灾爆炸的安全措施中，属于生产过程措施的有()。

A．无症状性溃疡B．幽门管溃疡C．复合性溃疡D．球后溃疡夜间痛和背部放射痛显著的是

A．司帕沙星B．金刚烷胺C．利福平D．阿昔洛韦E．磺胺嘧啶极易与金属离子形成螯合物的药物是

在下列医务人员的行为中，不符合有利原则的是

在《合同法》关于预期违约责任制度的规定中，如果当事人一方()不履行合同义务的，对方可以在履行期限届满之前，请求其承担违约责任。

在双代号或单代号网络计划中，工作的最早开始时间应为其所有紧前工作()。

钢绞线质量评定方法中，每批从()做拉力试验，包括整根钢绞线的最大负荷、屈服负荷、伸长率。

简述判断声源方向的主要线索。