首页
登录
从业资格
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
练习题库
2022-08-02
88
问题
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1, i-2, …个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序,则需要进行( )次整数之间的比较。对于该排序算法,输入数据具有( )特点时,对整数进行从小到大排序,所需的比较次数最多。问题1选项A.9B.10C.12D.13问题2选项A.从小到大B.从大到小C.所有元素相同D.随机分布
选项
答案
CB
解析
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
⒈ 从第一个元素开始,该元素可以认为已经被排序
⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描
⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置
⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
对于本题:{5.2.4.6.1.3}
第一趟:第一次比较,5大于2(新元素),元素5向后位移一位,而5之前无数据,即将2插入到1位,2,5
第二趟:第一次比较,5大于4(新元素),元素5向后移一位,再进行第二次比较,2小于4(新元素),即将4插入2之后的一位,即 2,4,5
依次类推…
所以比较的次数为1+2+1+4+4=12
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2417919.html
本试题收录于:
中级 软件评测师题库软件水平考试初中高级分类
中级 软件评测师
软件水平考试初中高级
相关试题推荐
数据结构和算法设计的原则不包括()。A.先设计全局的,再设计局部的 B.为
()并不是算法必须具备的特征。A.可行性 B.可移植性 C.确定性 D
在直接插入排序、冒泡排序、简单选择排序和快速排序方法中,能在第一趟排序结束后就得
程序员需要用文档来表述自己的思想。文档设计的要点不包括()。A.文档制作应先
非空二叉排序树的定义是:若根结点具有左子树,则左子树中所有结点的关键码均小于根结
若对二进制整数X,Y的各位进行异或运算后的结果为全0,则说明()。A.X>Y
下面加密算法中,加密和解密需要用不同密钥的是()。A.AES B.RSA
()最不适用于处理序列已经正序有序的情况。A.冒泡排序 B.快速排序 C
要判断16位二进制整数x的低三位是否全为0,则令其与十六进制数0007进行(
某二叉排序树如下所示,新的元素45应作为()插入该二叉树中。 A.11的左
随机试题
Whatisthewoman’sproblem?[originaltext]W:Didyoucontacttechnicalsupport
Thediscountdo-it-yourselfstore,Aldi,hasseensomebig【T1】______recently
Youshouldhaveputthemilkintherefrigerator.Iexpectit______undrinkable.A
[originaltext]M:Weseemtobehavingthisconversationoverandoveragain.W:
A.动脉粥样硬化 B.纤维肌性发育异常 C.多发性大动脉炎 D.先天性肾动
我国初次分配关系尚未理顺,应当考虑增加劳动者的劳动报酬。
半刚性材料在使用时主要应保证()满足要求。A.压实度 B.7d抗压强度 C
患者男性,75岁,疲劳、面色苍白、无力,诊断为“缺铁性贫血”,给予口服铁剂治疗,
在员工援助计划问题诊断阶段主要关注的层面包括()。A.社会层面 B.组织
(2013年真题)在以下4种组织类型中,不能对环境变化和不确定性做出适当反应
最新回复
(
0
)