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

admin2019-08-01 55

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列()的社会思想突出表现为“仁”。

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

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

中世纪战争史上有过两次君士坦丁堡陷落，分别简述其发生的时间、征战的双方、导致的历史变动。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。

试比较脱机I／／O和联机I／O。

下列不属于我国劳动法调整范围的有()

衡量外债规模的指标中，债储率的国际标准安全线为

关于液体制剂特点的说法，错误的是()。

当事人采用合同书形式订立合同的，自(　　)。

以下关于宪法的表述，错误的是()

换入资产的未来现金流量在风险、时间和金额方面与换出资产显著不同，表明非货币性资产交换具有商业实质。()

根据契税法律制度的规定，下列各项中，应征收契税的有()。

澳大利亚出口量居世界前列的矿产品是()。

简述成就目标理论的主要观点。

For:OwenParkFrom:SallyPorterMessage:1.Shehasbeenaskedto(1)______thedecisiononthelaunchofDietCrus

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

计算机408

学硕统考专业

下列()的社会思想突出表现为“仁”。

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

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

中世纪战争史上有过两次君士坦丁堡陷落，分别简述其发生的时间、征战的双方、导致的历史变动。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补码表示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知X=0．1011000011×20.0101，Y=0．0001100000×20.1000，试求X+Y．要求写出详细的

设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。

试比较脱机I／／O和联机I／O。

下列不属于我国劳动法调整范围的有()

衡量外债规模的指标中，债储率的国际标准安全线为

关于液体制剂特点的说法，错误的是()。

当事人采用合同书形式订立合同的，自( )。

以下关于宪法的表述，错误的是()

换入资产的未来现金流量在风险、时间和金额方面与换出资产显著不同，表明非货币性资产交换具有商业实质。()

根据契税法律制度的规定，下列各项中，应征收契税的有()。

澳大利亚出口量居世界前列的矿产品是()。

简述成就目标理论的主要观点。

For:OwenParkFrom:SallyPorterMessage:1.Shehasbeenaskedto(1)______thedecisiononthelaunchofDietCrus

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

当事人采用合同书形式订立合同的，自(　　)。