首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
如表r有100000个元素,前99999个元素递增有序,则采
[单选题]
如表r有100000个元素,前99999个元素递增有序,则采用( )方法比较次数较少。
折半插入排序
冒泡排序
归并排序
基数排序
查看正确选项
添加笔记
求解答(10)
邀请回答
收藏(106)
分享
纠错
8个回答
添加回答
7
阿诺41
在数据近乎有序的情况下,插入排序时间复杂度低
发表于 2017-10-01 23:22:27
回复(0)
2
黏黏糖
元素已有序时,插入排序的时间复杂度为O(n)
发表于 2017-06-26 16:35:12
回复(4)
3
路飞的小伙伴9
折半插入排序的比较次数约为O(nlog
2
n),该比较次数与待排序表的初始状态无关,仅与元素个数n有关。
若是直接插入排序,比较次数为:99998(第一个元素不比较,后面99998个元素分别比较一次)+99999(最差情况)=199997次。
若是冒泡排序(带flag),最好比较次数为:99999(已经排序好了)+99998(根据flag退出)=199997次。
最坏比较次数为:99999*100000/2=好大的数(此时对应最后一个数最小)。
归并排序:共需进行
O(log
2
n)趟排序,每趟最差比较次数反正比n小一点。。。。
发表于 2017-09-17 22:38:20
回复(0)
0
向宁冋桌
有序两个字注意了,敲黑板!
发表于 2019-05-09 23:05:37
回复(0)
0
阳光下的米雪
在本身已经有序的表中进行插入排序时,可以利用折半查找到待排元素的插入位置,而折半查找的比较次数相对较少。
发表于 2019-04-16 10:39:27
回复(0)
0
xxxxxxxxxxxxxxxa
我一直很不理解 一直会出题目: 比较次数和数据初识顺序的关系
很多人等同于时间复杂度和初始序列逆序的关系,但其实两者有区别。时间复杂度大于比较次数。(比较是时间复杂度的组成成分)
反正这个题 比较次数,
冒泡归并和序列初始顺序无关,(时间复杂度也是!),但是插排或者折半 时间复杂度和比较次数都是有关系的,
直接插排比较次数减少了很多,时间复杂度也相应降低了很多。
基数排序,不是基于比较的,(虽然它暗含了比较)。
发表于 2018-06-27 17:48:26
回复(0)
0
xfei
问题中要求比较次数较少的,那基数排序不是基于比较排序,岂不是比较次数最少?求解答
发表于 2017-08-14 14:00:39
回复(3)
0
徒步の旅行者
个人观点应该选择折半插入排序吧。
发表于 2017-06-26 17:29:42
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
排序
上传者:
阿奻_
难度:
8条回答
106收藏
3513浏览
热门推荐
相关试题
假定一个待哈希存储的线性表为(32...
哈希
评论
(1)
5.下列判断正确的是( )
资料分析
言语理解与表达
资料分析
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
《拳皇97》最后BOSS是谁?
游戏常识
评论
(1)
《魔兽世界》中,下列不属于玩家可以...
游戏常识
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题