首页 > 试题广场 >

下面的哪种排序算法在算复杂度平均不是O(nlogn)的?

[单选题]
下面的哪种排序算法在算复杂度平均不是O(nlogn)的? 
  • 快速排序
  • 桶排序
  • 合并排序
  • 二叉树排序树排序
  • 堆排序
查看正确选项
添加回答
zhisheng_blog头像 zhisheng_blog
发表于 2016-08-24 11:27:56 回复(0)
LittleBaby头像 LittleBaby
桶排序的时间复杂度是线性的，即O(n)的。比如：对n个数排序，这n个数的值在一定范围内（比如在1到100之间），那么直接构建一个大小为100的数组arr，在遍历包含n个数的数组num时，令arr[num[i]]++即可，最后从头到尾遍历arr，若arr[i]=m，则输出m个i即可。
发表于 2016-09-04 12:09:51 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
二叉排序树排序，如果已经建好这棵二叉排序树了，那就只遍历一次就可以了。但是就这个题目来看，应该是先根据关键字序列建立这棵二叉排序树。所以时间复杂度为O(nlogn)
发表于 2017-10-24 11:05:46 回复(0)
小黑牛头像 小黑牛

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

发表于 2017-03-23 14:34:01 回复(0)
暮夏+1头像 暮夏+1
桶排序的平均算法复杂度为O(n+c) n为待排序数的个数 c为桶个数
发表于 2017-04-25 08:20:54 回复(0)
面向未来编程头像 面向未来编程
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
发表于 2016-05-07 15:45:46 回复(5)
小白菜菜菜头像 小白菜菜菜
发表于 2016-07-26 20:29:47 回复(0)
在打卡的安德鲁很纠结头像 在打卡的安德鲁很纠结
好烦要记
编辑于 2024-03-27 22:06:20 回复(0)
云云云一飞冲天头像 云云云一飞冲天
道理我都懂，就是有时候桶这个字容易看成堆，很迷惑。
发表于 2022-08-18 22:29:55 回复(0)
学术废物头像 学术废物
是时间还是空间？
发表于 2022-03-19 16:36:41 回复(0)
一只老风铃头像 一只老风铃
桶排序最快o(n)
发表于 2019-02-03 13:03:19 回复(0)
Sc0tt头像 Sc0tt


发表于 2018-05-18 09:38:30 回复(0)
逍遥程序员头像 逍遥程序员
b
发表于 2016-08-28 00:04:31 回复(0)
塞达斯兰头像 塞达斯兰
希尔排序我知道不是
桶排序难道就是了吗。。。？不是o(N)吗
发表于 2016-05-06 02:21:32 回复(1)
提交观点

问题信息

排序
来自：网易内推笔试练习卷
难度：
14条回答 14498浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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