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

admin2023-02-06 62

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

学硕统考专业

以下选项除了()都是教师仪容仪态需要遵守的要求。

赫尔巴特提出的四段教学法的四个阶段是领会、联想、系统、方法。()

强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。

关于发展性教师评价，以下说法正确的有()。

利用分度头可以在工件上划出等分线或不等分线。()

市场细分的原则有_______。

要约邀请是希望他人向自己发出要约的意思表示，寄送价目表、()、招股说明书、商业广告等。

在施工过程中对信息收集，整理、处理、存储与应用等进行的管理，被称为(　　)。

暂准进口的施工机械、工程车辆、安装用仪器应在规定期限内复运出境，超过规定期限，应从()开始按月征收进口关税和进口环节代征税。

王某未经许可，以营利为目的非法复制某公司拥有著作权的唱片，情节严重，构成犯罪；同时王某还将该侵权复制品销售给李某，违法所得数额巨大，也构成犯罪。根据刑法及相关规定，对王某的上述行为应当如何定罪处罚?

个体身心发展具有不均衡性，因此教育要()。

已知实数a，6，c满足，a+b+c＝0，abc＞O，且则x97-96xy+y³＝()。

Hewaschosenleaderbygeneral______.

A、Alcoholcanincreasethedangerofheartdisease.B、Properdailyalcoholdoesgoodtoone’sheart.C、Solidandsoftdrinkscan

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

计算机408

学硕统考专业

以下选项除了()都是教师仪容仪态需要遵守的要求。

赫尔巴特提出的四段教学法的四个阶段是领会、联想、系统、方法。()

强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。

关于发展性教师评价，以下说法正确的有()。

利用分度头可以在工件上划出等分线或不等分线。()

市场细分的原则有_______。

要约邀请是希望他人向自己发出要约的意思表示，寄送价目表、()、招股说明书、商业广告等。

在施工过程中对信息收集，整理、处理、存储与应用等进行的管理，被称为( )。

暂准进口的施工机械、工程车辆、安装用仪器应在规定期限内复运出境，超过规定期限，应从()开始按月征收进口关税和进口环节代征税。

王某未经许可，以营利为目的非法复制某公司拥有著作权的唱片，情节严重，构成犯罪；同时王某还将该侵权复制品销售给李某，违法所得数额巨大，也构成犯罪。根据刑法及相关规定，对王某的上述行为应当如何定罪处罚?

个体身心发展具有不均衡性，因此教育要()。

已知实数a，6，c满足，a+b+c＝0，abc＞O，且则x97-96xy+y³＝()。

Hewaschosenleaderbygeneral______.

A、Alcoholcanincreasethedangerofheartdisease.B、Properdailyalcoholdoesgoodtoone’sheart.C、Solidandsoftdrinkscan

在施工过程中对信息收集，整理、处理、存储与应用等进行的管理，被称为(　　)。