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

admin2018-08-12 75

问题对一个具有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://www.kaotiyun.com/show/nuRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

第一个五年计划的具体时间段是()。

印加人记载事物使用的方法是()。

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

尚书一职，秦置于宫禁；西汉沿置，为皇帝收发文书，传达记录诏命章奏；东汉置尚书台，“出纳王命，赋政四海，权尊势重”，成为朝廷的政务中心。这一过程反映了()

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是____。

这个标志是何含义？

成人教育理论认为成人教育是一种【】

《简易程序规定》第14条，将调解作为六类案件的前置程序，属于这六类案件是

脱肛不常见于下列何类人群

52岁，妇女，盆浴后，白带多，外阴痒伴尿频，阴道粘膜有散在出血点，后穹有多量黄色泡沫状分泌物，诊断为

内燃机用汽油泵(内燃机的输出功率为95马力)

上海市场A股、基金、债券等品种的清算与交收流程包括()。

下列行为中，构成无因管理的有()。

()是研究学校情境中学与教的基本心理学规律的科学。