首页 > 试题广场 >

输入若已经是排好序的，下列排序算法最快的是？

[单选题]
输入若已经是排好序的（递增），下列排序算法（同样递增）最快的是（） 
  • 插入排序
  • Shell排序
  • 合并排序
  • 快速排序
添加回答
推荐
free斩头像 free斩
选A插入排序最快，遍历一遍即可，时间复杂度为 O（N）;
剩下的 Shell 是基于插入排序的，一般最好情况下才可能达到 O(N),此处明显比插入排序复杂;
C:归并排序必须要建立一个栈来维护而且任何情况下其时间复杂度均为 O(N*logN);
D:众所周知快排最好的情况下，时间复杂度是 O(N*logN).
所以选 Ａ。
编辑于 2015-02-06 10:06:33 回复(1)
霖淼书生头像 霖淼书生
·A
插入排序，遍历一遍，时间复杂度为O（n）
Shell排序，明显大于O（n）
归并排序属于稳定的最好最坏时间复杂度都一致的，复杂度为O（nlgn）
快排，在有序的情况下，最慢，O（n^2）
发表于 2015-09-05 11:57:44 回复(0)
阿诺41头像 阿诺41
在输入数据近乎有序的情况下，插入排序时间复杂度O(n)，表现最好
发表于 2017-10-01 23:25:07 回复(0)
sunlight_run头像 sunlight_run
A：插入排序只需要遍历一遍，时间复杂度为O（n）
B：希尔排序基于插入排序，只有好的情况下才能达到O（n）
C：归并排序时间复杂度为nlogn
D：快速排序在排好序的情况下，时间复杂度为n^2
发表于 2017-07-03 20:24:33 回复(0)
美团到店招聘头像 美团到店招聘
此题选C。有序分为正序和逆序。
请告诉我，如果是逆序，插入排序如何能胜过归并排序？！
编辑于 2017-02-27 10:48:55 回复(4)
nomico271头像 nomico271
若已排好序，使用插入排序的时候只要两两比较一次即可，复杂度为O(n)。
发表于 2017-07-21 19:14:58 回复(0)
huixieqingchun头像 huixieqingchun
要理解各种排序算法的原理。
发表于 2016-05-12 14:57:41 回复(0)
Juventus-小九头像 Juventus-小九
直接选择的时间复杂度为o(n^2)
发表于 2022-01-11 00:05:57 回复(0)
我是萌新有人信吗头像 我是萌新有人信吗
快排也可以达到N
发表于 2019-04-03 09:20:17 回复(0)
提交观点

问题信息

搜狐 复杂度 排序
来自：搜狐2013校招研发工...
上传者：ShelterFromTheS
难度：
9条回答 13010浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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