首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
对一个具有7个记录的文件进行快速排序,请问: (1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
admin
2018-08-12
69
问题
对一个具有7个记录的文件进行快速排序,请问:
(1)在最好情况下需进行多少次比较?说明理由,并给出相应实例。
(2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。
选项
答案
(1)在最好情况下,由于快速排序是一个划分子区间的排序,每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1,显然,第一遍划分得到两个长度均为[n/2]的子文件。第二遍划分得到4个长度均为[n/4]的子文件,以此类推,总共进行k=log
2
(n+1)遍划分,各文件的长度均为1,此时排序结束。由于n=7,k=3,在最好情况下,第一遍经过6次,可找到一个基元是正中间的元素;第二遍分别对两个子文件(此时长度为3)进行排序,各需要2次,这样就可将整个文件排序完毕,从而知n=7的最好情况下需进行10次比较。例如:4,7,5,6,3,1,2。 (2)在最坏情况下,若每次划分时用的基元,它的关键字值是当前记录中最大(或最小),那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此,若初始排列的记录是按关键字递增或递减,而所得的结果必须为递减或递增排列,那么此时,快速排序就退化为与冒泡排序相似,而且时间复杂度为O(n
2
),反而不快了。对于n=7的记录文件,显然最坏情况下的比较次数为21。例如:7,6,5,4,3,2,1。
解析
转载请注明原文地址:https://kaotiyun.com/show/nuRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
文艺复兴运动兴起的时间是()。
简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。
印加人记载事物使用的方法是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
美国历史上第一个具有宪法性质的文件是()。
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
编写判定给定的二叉树是否是二叉排序树的函数。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
随机试题
根据我国《商标法》,关于地理标志的特征,下列选项正确的有()
患者,女性,53岁,胸闷、气急3周,胸片示右侧大量胸腔积液,胸穿抽出血性胸水1000m1。胸腔穿刺抽液时,病人出现头晕、出汗、面色苍白、四肢发凉,应立即
用比色法测定铅一二硫腙配合物时,选择滤光片的颜色应为
有头疽的病因病机哪项不正确( )。
关于典型心绞痛的描述下列哪项不正确( )。
古镇大多有独特的建筑风貌、街巷________和有关的民间传说。它保留了旧时代的生活________,__________在古镇老街,可以发思古之幽情。填入划横线部分最恰当的一项是:
设X1,X2,…,Xn是来自总体X的简单随机样本,已知E(Xk)=ak(k=1,2,3,4).证明:当n充分大时,随机变量Zn=近似服从正态分布,并指出其分布参数.
TheauthorsoftheUnitedStatesConstitutionattemptedtoestablishaneffectivenationalgovernmentwhilepreserving______fo
Despitemajorchangesinthecausesofdeathsincethe1900s,theassociationbetweendeprivationand【C1】______remainsfirmlyen
Thehealth-careeconomyisfilledwithunusualandevenuniqueeconomicrelationships.Oneoftheleastunderstoodinvolvesthe
最新回复
(
0
)