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

admin2023-02-06 38

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

学硕统考专业

教师劳动所创造的价值，并不是以物化的形式表现出来的，而是作为一种潜在价值因素存在于学生身上。这说明教师劳动具有滞后性的特点。()

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

教育目的的功能有()。

数学老师在考试前提醒学生，考试时若遇到难题可以放一放，先把后面相对简单的题答完了再回过头来思考。可小明却不喜欢这样，他每次都是一步一步地依照试卷的顺序答题。小明的认知风格更可能属于()。

有5支足球队进行单循环比赛，每场比赛胜者得3分，负者不得分，平局双方各得1分。比赛结束后，若5支球队的总得分为25分，冠军得12分，则亚军得：

患者，男性，55岁，肛周感染反复发作，伴瘙痒、疼痛，有渗出，肛周皮肤可见一孔道，应诊断为

患者，女性，敌百虫中毒，为其洗胃时应用

境外捐赠人宋先生拟在某县单独捐建一所小学。根据《公益事业捐赠法》，下列关于办理宋先生捐赠事务的说法，不符合规定的是()。

中国教育史上以美国学制为蓝本，第一次明确以学龄儿童和青少年身心发展规律作为划分学校教育阶段的依据的现代学制是()。

我在繁忙的工作之余，时常拿起相机，游走于城市的大街小巷，去探寻城市中那些的古迹和古迹后面那些有韵味的老故事。填入横线部分最恰当的一项是()。

鸳∶鸯()

根据下面材料回答下列题。与前一年相比，工业废水排放达标率增幅最大的年份是()。

甲公司的员工王某被劳务派遣至乙公司工作，在乙公司工作期间，王某在执行乙公司工作任务时造成丙损害，对此，甲公司并不知情。根据《侵权责任法》的有关规定，对内的损害承担责任的主体是()。

Sothat’swhatadigitalrevoltlookslike.Amillion-and-a-halfemailsandalmost90,000phonecallstoUSCongress.Publiccom

September30MargaretHamiltonCharmanteCustomerService10OldShoalsRoadArden,NorthCarolina28704DearMs.Hamilton,I