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

admin2023-02-06 49

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

学硕统考专业

教育心理学常用的方法有()。

关于教师和学生关系的两个对立观点是()。

教师在编写教学目标时，要求学生“概括出《孔乙己》的故事情节”。这属于布卢姆认知目标中的()。

学生在学习时，掌握“鸟”有“前肢为翼”和“无齿有喙”这两个共同的关键特征。这种学习属于()。

党的十九大报告指出，到中华人民共和国成立一百年时，基本实现现代化，把我国建设成社会主义现代化国家。综合分析国际国内形势和我国发展条件，从2020年到本世纪中叶可以分为两个阶段来安排，这两个阶段分别是()。

为了维护自己在大人心目中的“好孩子”形象，晓梅总是会很顺从家长的意愿去做某件事情，即便内心不是特别情愿。按照科尔伯格的阶段理论，晓梅的道德发展水平处于()。

如图所示，为测量珠穆朗玛峰上某点C的海拔高度，测量队选择了两个海拔高度相差100米的珠峰测量点A和B，测得∠ABC为90°，从A观测B、C的仰角分别为30°和45°，从B观测C的仰角也为30°，则C点的海拔高度比A点高：

下列关于《国务院关于加快建立健全绿色低碳循环发展经济体系的指导意见》提出的主要目标的说法，错误的是()。

下面关于m阶B树的说法中，正确的是()。①每个结点至少有两棵非空子树。②树中每个结点至多有m-1个关键字。③所有叶子在同一层上。④当插入一个数据项引起B树结点分裂后，树长高一层。

古代医患关系的特点是现代医患关系的特点是

A．乙胺丁醇B．异烟肼C．利福平D．链霉素E．吡嗪酰胺结构中含有吡嗪结构的是

患者，男，62岁，突感心前区痛，硝酸甘油不能缓解，伴气促、大汗，恐惧感，有助于诊断心肌梗死的心电图改变是

我国农村土地产权制度的核心是()。

一建筑物高90m、宽25m、长180m，建筑物为金属屋面的砖木结构，该地区年平均雷暴日为80天，求该建筑物年预计雷击次数为下列哪一项数值?()

期货市场上，如果保证金比例为10%，则当价格变动1%时，投资者的盈亏变动()

不出单意外伤害保险中的“不出单”是指()。

某银行为了减少顾客等待的时间，提高银行效率并为顾客创造价值，开发了一种叫号系统，这种系统能使客户知道自己的等待时间并提示他们要办理业务的柜台号。根据以上信息，从价值链分析的角度可以判断这个活动属于()。

简述近代中国外交制度的演变。