首页 > 试题广场 >

对于排序算法，经常关注的是其时间复杂度和稳定性。下列排序算法

[单选题]
对于排序算法，经常关注的是其时间复杂度和稳定性。下列排序算法中平均时间复杂度是O(nlogn)且稳定的是？（） 
  • 冒泡排序
  • 插入排序
  • 归并排序
  • 堆排序
  • 快速排序
查看正确选项
添加回答
liyanan12头像 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)
程序猿Go师傅头像 程序猿Go师傅

编辑于 2019-10-21 21:32:30 回复(0)
Wilbur.头像 Wilbur.
归并排序是稳定的，复杂度也是稳定的
发表于 2022-08-22 07:27:42 回复(0)
提交观点

问题信息

排序
上传者：林呼
难度：
3条回答 3874浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号