首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
某线性表中有100000个元素,其中前99990个元素递增有
[单选题]
某线性表中有100000个元素,其中前99990个元素递增有序,则采用()方法进行递增排序时关键字比较次数最少。
简单选择排序
直接插入排序
二路归并排序
快速排序
添加笔记
邀请回答
收藏(125)
分享
纠错
4个回答
添加回答
6
推荐
白驹之过隙
选
B
。考察的是
排序原理和适用场景
。
根据题目中的“前99990个元素递增有序”,得出关键字比较次数最少的原理就是这99990个元素
不参与比较或者移动等耗时
操作。
根据以下对各种排序的思想分析,二路归并和快速排序没有利用大部分为递增序列而不参与比较或者移动的操作,简单排序的时间复杂度大于直接插入排序。所以选B。
简单选择排序思想为在当前待排序数列中选出最小值添加到有序序列中,
其移动次数正序为0次,比较次数复杂度O(n
2
)
。
直接插入排序思想为整个排序过程为n-1趟,先将序列中的第一个当成有序子序列,然后从第二个开始逐个进行插入,直至整个序列有序,最好的情况下
正序移动次数为0,比较次数为n-1,时间复杂度为O(n)
。
二路归并排序初始序列含有n个记录则可以看成n个有序的子序列,每个子序列长度为1;两两合并,得到n/2个长度为2或1的有序子序列,再两两合并,……如此重复,直到得到一个长度为n的有序序列为止。
归并时间复杂度O(nlog
2
n)
快速排序选定一个基准值,通过一趟排序将待排分割成独立的两部分,前一部分均小于或等于基准值,后一部分大于基准值,然后对每个部分继续进行上述的重复操作,直到整个序列有序。最好的情况是基准值能够均衡分为两部分,最坏的就是只得到一个比上一次划分少一个记录的子序列O(n
2
)
编辑于 2020-01-21 15:48:51
回复(0)
4
你永远得不到的祖奶奶
直接插入排序:分两部分,一部分有序,一部分无序。相当于前面99990是有序的,后面部分是无序的,将无序部分进行有序化就更好符合插入排序的思想。
发表于 2020-05-26 10:20:23
回复(0)
3
Jino.
选
B
。
A项,
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素,则比较次数总是N (N - 1) / 2。
简单排序的时间复杂度为 O(N*2)。因此A项错误。
B项,整体数据已经基本有序,在这种情形下直接插入排序
执行效率最好,
前99990个元素
每次插入都不用移动前面的元素,时间复杂度为O(N)
。后面10个元素对总体复杂度影响较小。因此B项正确。
C项,二路归并排序平均时间复杂度
O( nlogn )。
D项,
快速排序在
序列基本有序时此算法性能最差。因此D项错误。
综上本题选B。
发表于 2020-01-14 17:32:05
回复(1)
0
Juventus-小九
直接插入排序,一部分有序,一部分无序。
发表于 2022-01-23 15:38:13
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
排序
上传者:
赞花婆
难度:
4条回答
125收藏
2959浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题