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

admin2017-01-04 37

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

选项

答案(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各文件的长度均为l，此时排序结束。由于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://jikaoti.com/ti/56fjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

东欧国家的私有化方式一般有四种，其中波兰采取的主要方式是()

近代自然科学产生的条件及其发展情况。

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。

中国第一条自行设计修建的铁路是在（）。

生成多项式为x3+x+1，则数据信息10101的CRC编码是()。

动脉粥样硬化的特点包括

关于萎缩，下列说法正确的是

正常心尖搏动位于

人民法院判决认定财产无主后，原财产所有人或继承人出现，对财产提出请求，应如何处理?()

()是开展工程咨询的业务基础和重要手段。

下列不属于镇规划具体任务的是()。

供应链管理的实践始于供应链上末端的零售行业。()

()是用于测定从事某项特殊工作所具备的某种潜在能力。

(2012年真题)下列选项中，符合我国刑法关于假释规定的是()。

Theonlysafewayofdistinguishingbetweenedibleandpoisonousmushroomsistolearnto______theindividualspecies.