首页 > 试题广场 >

下面排序算法属于稳定排序且时间复杂度为 O ( nlogn

[单选题]

下面排序算法属于稳定排序且时间复杂度为的是()

  • 快速排序
  • 冒泡排序
  • 堆排序
  • 归并排序
推荐
为了更好的让你记住,我给你总结一下。
常用的排序有简单插入排序,希尔排序,简单选择排序,冒泡排序,归并排序,堆排序还有快速排序。
其中稳定的排序有:简单插入排序,冒泡排序,归并排序。
不稳定的有:希尔排序,简单选择排序,堆排序,快速排序。
时间复杂度为O(n²)的:简单选择排序,简单插入排序,冒泡排序。
时间复杂度为O(nlogn)的:快速排序,堆排序,归并排序。
其中最快的一般为快速排序,但是如果是有序数列,则快速排序的时间复杂度为O(n2);
快速排序虽然快,但是不稳定。
既稳定又快的就是归并排序。
还有堆排序的作用是快速选出最大的几个数,使用小顶堆、快速选出最小的数,使用大顶堆。
当然还有一个基数排序。这个比较特殊,如果想懂推荐你去百度一下它。
纯自己写。
编辑于 2017-03-18 09:01:55 回复(1)
我觉得,单靠记忆,治标不治本,时间久了,该忘还是忘。所谓的稳定性是指对于一个序列进行排序,其中数值相同的元素的前后位置关系与序列排序完成时的前后关系保持一致。
A:速排序,由于前后两个指针所指元素进行交换位置,很容易就把后面的元素提到前面的位置上,快速排序一定是不稳定的。
B:冒泡排序,由于是相邻位置元素交换,不会出现前面的元素跳变至后方,不像快速排序那样有那么大的跨度。所以,冒泡排序是稳定的。
C:堆排序,同样在初始形成一个完全二叉树之后,父子结点之间的交换同样是跨过了层序列当中的很多结点,因此也是不稳定的排序算法。
D:归并排序,归并排序会对于序列当中相邻位置上的元素划成一组,完成组内的排序,所以是相邻位置上的元素的交换,没有跳变的可能,所以归并排序是稳定的。
发表于 2021-07-11 17:04:09 回复(0)
发表于 2019-07-09 17:00:26 回复(2)
快速排序和堆排序都是O(nlogn)但是不稳定,冒泡排序稳定但是O(n²),归并排序稳定且复杂度为O(nlongn)。

选D
发表于 2017-03-03 11:40:07 回复(0)
堆排序,首先建堆,会从n/2往1调用最大堆,这样不会破坏稳定性,但是排序的时候,也是从尾到头交换,这一步破坏了稳定性,
发表于 2019-04-05 21:23:35 回复(0)
稳定排序算法有:插入排序O(n),冒泡排序O(n),归并排序O(nlog2n),计数排序O(n+k),桶排序O(n+k),基数排序O(n+k)
发表于 2019-04-16 11:06:22 回复(1)
D
发表于 2017-01-14 16:30:55 回复(0)
答案选选D
A、B时间复杂度不符合要求 
C  堆排序不稳定
发表于 2016-12-14 20:25:13 回复(0)