首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
下面哪种排序方法不属于比较排序:( )
[单选题]
下面哪种排序方法不属于比较排序:( )
选择排序
鸡尾酒排序
奇偶排序
计数排序
查看正确选项
添加笔记
求解答(0)
邀请回答
收藏(2)
分享
纠错
1个回答
添加回答
2
ChopinXBP
D
计数排序是一个非基于比较的排序算法
,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。
当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)
假设输入的线性表L的长度为n,L=L1,L2,..,Ln;线性表的元素属于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk};则计数排序可以描述如下:
1、扫描整个集合S,对每一个Si∈S,找到在线性表L中小于等于Si的元素的个数T(Si);
2、扫描整个线性表L,对L中的每一个元素Li,将Li放在输出线性表的第T(Li)个位置上,并将T(Li)减1。
发表于 2019-02-22 21:05:29
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
设计
算法工程师
第四范式
2019
上传者:
小小
难度:
1条回答
2收藏
1218浏览
热门推荐
相关试题
下面描述中,符合结构化程序设计风格...
搜狐
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
为什么要想做一位互联网行业的设计师...
欢聚集团
2018
设计
评论
(0)
为校园短视频达人招募活动设计一张海...
欢聚集团
2018
设计
评论
(0)
设某二叉树的先序遍历序列为abdg...
树
评论
(1)
2022 诺瓦科技 Perl re...
perl
System Verilog
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题