首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
对于排序算法,经常关注的是其时间复杂度和稳定性。下列排序算法
[单选题]
对于排序算法,经常关注的是其时间复杂度和稳定性。下列排序算法中平均时间复杂度是O(nlogn)且稳定的是?()
冒泡排序
插入排序
归并排序
堆排序
快速排序
查看答案及解析
添加笔记
求解答(4)
邀请回答
收藏(67)
分享
3个回答
添加回答
1
liyanan12
先考虑时间复杂度:
冒泡排序:O(N^2)
插入排序:O(N^2)
归并排序:O(N*logN)
堆排序:O(N*logN)
快速排序:经典快速排序:O(N^2),随机快速排序:O(N*logN),不知道题目中指的是哪个。
符合时间复杂度要求的是归并排序、堆排序和随机快速排序,而其中符合稳定性要求的只有归并排序。
排序算法的稳定性指的是:原序列有相同的元素时,排序过后是否这些相同的元素和原来的顺序相同。
举例:对学生的成绩排序
姓名 班级 成绩
A 1 20
B 1 50
C 2 30
D 1 30
按照班级排序后:
姓名 班级 成绩
A 1 20
B 1 50
D 1 30
C 2 30
此时按照成绩排序,我希望如果将同一个班的同学抽离出来,依然有序,此时就需要用到排序算法的稳定性。
姓名 班级 成绩
A 1 20
D 1 30
C 2 30
B 1 50
这样如果将 1 班的同学单独抽离出来,成绩也是有序的。
发表于 2019-01-18 19:59:20
回复(0)
17
程序猿Go师傅
编辑于 2019-10-21 21:32:30
回复(0)
0
Wilbur.
归并排序是稳定的,复杂度也是稳定的
发表于 2022-08-22 07:27:42
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
排序
上传者:
林呼
难度:
3条回答
67收藏
3879浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3693)
来自
华为研发工程师编程题
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
有20000人的就餐需求,现建了一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题