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

admin2019-08-01 42

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比，两者在促进社会变革的作用上有何不同?为什么?

晚清时期清帝年号的正确排序是

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

对1929—1933年的世界经济危机的特点，表述不正确的是()。

1931年，英国被迫承认自治领在内政外交上都独立自主的根本原因是()。

保加利亚共产党于1990年4月改名为保社会党，它在政府中沦为少数派的时间是()。

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

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

设有A，B，C，D4台主机都处在同一个物理网络中，A主机的IP地址是192．155．28．112，B主机的IP地址是192．155．28．120，C主机的IP地址是192．155．28．135，D主机的IP地址是192．155．28．202。共

既有破血通经作用，又能用治风热痒疹的药物是

土地价格按()方式分类，可以分为交易价格、理论价格、评估价格等。

下列对可燃固体燃烧过程的叙述中，正确的是()。

现金处理中，发现现金短缺300元，研究决定由出纳赔偿200元，余额报损，则批准处理后的会计分录为()。

如图，AABC的顶点都在正方形网格格点上，点A的坐标为(－1，4)，将△ABC沿y轴翻折到第一象限，则点C的对应点C’的坐标是()。

目前，土地资源遭到严重破坏。下列各种原因中不属于人类主观上的原因的有()。

J.Martin明确计算机有四类数据环境,其中独立于应用项目,具有较低的维护成本,应用开发效率较高的是

实时操作系统必须首先考虑的是______。

Camelsareusedtocarryingpeopleorheavygoods.【S1】______.Theyhaveverystrongback.Camelshavel

Fordecades,thetelevisionwastheflagshipofanyconsumer-electronicsproductline-up.Inallthegadgetsinthehome,【M1】___

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

计算机408

学硕统考专业

19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比，两者在促进社会变革的作用上有何不同?为什么?

晚清时期清帝年号的正确排序是

在下列四本部书中有可能记载“甘薯所在，局面便有半年之粮，民间渐次广种”一语的只能是()。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

对1929—1933年的世界经济危机的特点，表述不正确的是()。

1931年，英国被迫承认自治领在内政外交上都独立自主的根本原因是()。

保加利亚共产党于1990年4月改名为保社会党，它在政府中沦为少数派的时间是()。

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

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

设有A，B，C，D4台主机都处在同一个物理网络中，A主机的IP地址是192．155．28．112，B主机的IP地址是192．155．28．120，C主机的IP地址是192．155．28．135，D主机的IP地址是192．155．28．202。共

既有破血通经作用，又能用治风热痒疹的药物是

土地价格按()方式分类，可以分为交易价格、理论价格、评估价格等。

下列对可燃固体燃烧过程的叙述中，正确的是()。

现金处理中，发现现金短缺300元，研究决定由出纳赔偿200元，余额报损，则批准处理后的会计分录为()。

如图，AABC的顶点都在正方形网格格点上，点A的坐标为(－1，4)，将△ABC沿y轴翻折到第一象限，则点C的对应点C’的坐标是()。

目前，土地资源遭到严重破坏。下列各种原因中不属于人类主观上的原因的有()。

J.Martin明确计算机有四类数据环境,其中独立于应用项目,具有较低的维护成本,应用开发效率较高的是

实时操作系统必须首先考虑的是______。

Camelsareusedtocarryingpeopleorheavygoods.【S1】______.Theyhaveverystrongback.Camelshavel

Fordecades,thetelevisionwastheflagshipofanyconsumer-electronicsproductline-up.Inallthegadgetsinthehome,【M1】___

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