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

admin2023-02-06 32

问题对于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://jikaoti.com/ti/kXPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在实际教学过程中，张老师采用画小红花、插小红旗等方式鼓励学生的德育方法是()。

教学过程的规律有哪些?()

2018年2月，中央一号文件《中共中央国务院关于实施乡村振兴战略的意见》发布，下列有关实施乡村振兴战略的说法，错误的是()。

学习迁移中的()是指难度和复杂程度基本属于同一水平的学习之间的相互影响，如正弦、余弦概念的相互影响。

保护学生安全不属于《中小学教师职业道德规范》的要求。()

现代学习方式的基本特征有哪些?

下图右侧四个选项中，对左侧零件的四个立面呈现有错误的一项是：

按皮亚杰的观点，以自我为中心，单方面考虑问题的儿童处于

A．华法林B．肝素C．尿激酶D．糖皮质激素E．甲苯磺丁脲引起股骨头无菌性坏死最常见的是

属于病理反射检查结果的是()。

小明和姐姐用2013年的台历做游戏，他们将12个月每一天的日历一揭下，背面粘上放在一个盒子里、姐姐让小明一次性帮她抽出一张任意月份的30号或者31号。问小明一次至少应抽出多少张日历，才能保证满足姐姐的要求?()

下列不是制定工程项目进度计划依据中的制约因素的是()。

在按FOB吊钩下交货的术语成交时，其货物风险转移是()。

“进口口岸”栏应填报()。“起运国”栏应填报()。

关于递延年金，下列说法正确的有()。

函数f(x)=x3一3x2+1在x=__________处取得极小值．

下列叛乱民族不同于其他三项的一项是()。