无序单向链表排序的时间复杂度---拼多多二面编程题

无序单向链表排序的时间复杂度,我认为最快是O(n^2)--->冒泡排序
1归并排序 查找中间元素O(n)
2快排->无法向前遍历
3堆排序-》不会
大家知道有更快的算法吗
#笔试题目#
全部评论
归并排序,两两合并就行,每次合并规模扩大就行,不用找中间元素,复杂度nlogn
点赞 回复 分享
发布于 2020-10-29 20:05
归并排序是NlgN 的 这是我一面的题,你这也太爽了😁 简单分析一下,一共lgN层 每层merge和找中点都是O(N)的
点赞 回复 分享
发布于 2020-10-29 20:08
我知道一种快排写法是可以用在单向链表的
点赞 回复 分享
发布于 2020-10-29 20:24
懂了 谢谢各位
点赞 回复 分享
发布于 2020-10-29 21:19

相关推荐

offer多多的六边形战士很无语:看了你的博客,感觉挺不错的,可以把你的访问量和粉丝数在简历里提一下,闪光点(仅个人意见)
点赞 评论 收藏
分享
威猛的小饼干正在背八股:挂到根本不想整理
点赞 评论 收藏
分享
点赞 1 评论
分享
牛客网
牛客企业服务