对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问： (1)当n=7时，在最好情况下需进行多少次比较?请说明理由。 (2)当n=7时，给出一个最好情况的初始排序的实例。 (3)当n=7时，在最坏情况下需进行多少次比较?

admin2023-02-06 80

问题对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：
(1)当n=7时，在最好情况下需进行多少次比较?请说明理由。
(2)当n=7时，给出一个最好情况的初始排序的实例。
(3)当n=7时，在最坏情况下需进行多少次比较?请说明理由。
(4)当n=7时，给出一个最坏情况的初始排序的实例。

选项

答案(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k-1，那么第一遍划分得到两个长度均为[n／2]的子文件，第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log₂(n+1)遍划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一遍需比较6次，第二遍分别对两个子文件(长度均为3，k=2)进行排序，各需2次，共10次即可。 (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。 (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n²)。所以当n=7时，最坏情况下的比较次数为21次。 (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在学习立体几何的时候，有些学生能够非常迅速地接受并绘制出三维立体图形，而有些学生则要经过很长时间的学习才能慢慢接受。这体现了学生在()方面的差异。

“两个一百年目标”就是到新中国成立一百年时全面建成小康社会，到中国共产党成立一百年时建成富强民主文明和谐的社会主义现代化国家的目标。()

下列关于电磁波的说法正确的是：

米德冲突

脊休克的主要表现是

A、commandB、commonC、commentD、communistA

具有益卫固表，利尿功效的药物是

合同法的基本原则中，(　　)原则是民事活动的最重要的基本原则。

金属的燃烧能力取决于()

应收账款赊销效果的好坏，依赖于企业的信用政策。公司在对是否改变信用期间进行决策时，不需要考虑的因素是()。

采用股利增长模型计算普通股的资本成本时，下列各项中，会导致资本成本降低的有()。

求向量组α1=(1，1，4，2)T，α2=(1，一1，一2，4)T，α3=(一3，2，3，一11)T，α4=(1，3，10，0)T的一个极大线性无关组．

下列数据结构中，能够按照“先进后出”原则存取数据的是

WhichofthefollowingstatementsaboutthetelephoneofthefutureisNOTtrue?

计算机408

学硕统考专业

在学习立体几何的时候，有些学生能够非常迅速地接受并绘制出三维立体图形，而有些学生则要经过很长时间的学习才能慢慢接受。这体现了学生在()方面的差异。

“两个一百年目标”就是到新中国成立一百年时全面建成小康社会，到中国共产党成立一百年时建成富强民主文明和谐的社会主义现代化国家的目标。()

下列关于电磁波的说法正确的是：

米德冲突

脊休克的主要表现是

A、commandB、commonC、commentD、communistA

具有益卫固表，利尿功效的药物是

合同法的基本原则中，( )原则是民事活动的最重要的基本原则。

金属的燃烧能力取决于()

应收账款赊销效果的好坏，依赖于企业的信用政策。公司在对是否改变信用期间进行决策时，不需要考虑的因素是()。

采用股利增长模型计算普通股的资本成本时，下列各项中，会导致资本成本降低的有()。

求向量组α1=(1，1，4，2)T，α2=(1，一1，一2，4)T，α3=(一3，2，3，一11)T，α4=(1，3，10，0)T的一个极大线性无关组．

下列数据结构中，能够按照“先进后出”原则存取数据的是

WhichofthefollowingstatementsaboutthetelephoneofthefutureisNOTtrue?

合同法的基本原则中，(　　)原则是民事活动的最重要的基本原则。