首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
下面排序算法属于稳定排序且时间复杂度为 O ( nlogn
[单选题]
下面排序算法属于稳定排序且时间复杂度为
的是()
快速排序
冒泡排序
堆排序
归并排序
添加笔记
邀请回答
收藏(277)
分享
8个回答
添加回答
80
推荐
火锅菠菜
为了更好的让你记住,我给你总结一下。
常用的排序有简单插入排序,希尔排序,简单选择排序,冒泡排序,归并排序,堆排序还有快速排序。
其中稳定的排序有:简单插入排序,冒泡排序,归并排序。
不稳定的有:希尔排序,简单选择排序,堆排序,快速排序。
时间复杂度为O(n²)的:简单选择排序,简单插入排序,冒泡排序。
时间复杂度为O(nlogn)的:快速排序,堆排序,归并排序。
其中最快的一般为快速排序,但是如果是有序数列,则快速排序的时间复杂度为O(n2);
快速排序虽然快,但是不稳定。
既稳定又快的就是归并排序。
还有堆排序的作用是快速选出最大的几个数,使用小顶堆、快速选出最小的数,使用大顶堆。
当然还有一个基数排序。这个比较特殊,如果想懂推荐你去百度一下它。
纯自己写。
编辑于 2017-03-18 09:01:55
回复(1)
25
J-Young
我觉得,单靠记忆,治标不治本,时间久了,该忘还是忘。所谓的稳定性是指对于一个序列进行排序,其中数值相同的元素的前后位置关系与序列排序完成时的前后关系保持一致。
A:
快
速排序
,由于前后两个指针所指元素进行交换位置,很容易就把后面的元素提到前面的位置上,快速排序一定是不稳定的。
B:
冒泡排序
,由于是相邻位置元素交换,不会出现前面的元素跳变至后方,不像快速排序那样有那么大的跨度。所以,冒泡排序是稳定的。
C:
堆排序
,同样在初始形成一个完全二叉树之后,父子结点之间的交换同样是跨过了层序列当中的很多结点,因此也是不稳定的排序算法。
D:
归并排序
,归并排序会对于序列当中相邻位置上的元素划成一组,完成组内的排序,所以是相邻位置上的元素的交换,没有跳变的可能,所以归并排序是稳定的。
发表于 2021-07-11 17:04:09
回复(0)
10
创始元灵
发表于 2019-07-09 17:00:26
回复(2)
3
宫保鸡丁没萝卜
快速排序和堆排序都是O(nlogn)但是不稳定,冒泡排序稳定但是O(n²),归并排序稳定且复杂度为O(nlongn)。
选D
发表于 2017-03-03 11:40:07
回复(0)
2
我是萌新有人信吗
堆排序,首先建堆,会从n/2往1调用最大堆,这样不会破坏稳定性,但是排序的时候,也是从尾到头交换,这一步破坏了稳定性,
发表于 2019-04-05 21:23:35
回复(0)
0
阳光下的米雪
稳定排序算法有:插入排序O(n),冒泡排序O(n),归并排序O(nlog2n),计数排序O(n+k),桶排序O(n+k),基数排序O(n+k)
发表于 2019-04-16 11:06:22
回复(1)
0
Peter_Jiang
D
发表于 2017-01-14 16:30:55
回复(0)
0
focusOn
答案选选D
A、B时间复杂度不符合要求
C 堆排序不稳定
发表于 2016-12-14 20:25:13
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
复杂度
排序
上传者:
牛100
难度:
8条回答
277收藏
10168浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题