首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 快速排序
题目

快速排序的平均时间复杂度和最坏时间复杂度是?

A.O(n^2), O(n^2)

B.O(n^2), O(nlgn)

C.O(nlgn) , O(nlgn)

D.O(nlgn) , O(n^2)

上一题 下一题
解答

正确答案是 D

当排序已经成为基本有序状态时，快速排序退化为O（n^2）
一般情况下，排序为指数复杂度。
C 10条回复 评论
taotao

好多HR热衷于这样问……

发表于 2022-06-27 23:00:00
0 0
青辰

收藏从未停止，学习从未开始

发表于 2021-09-08 16:50:00
0 0
ʚ ɞ

学到了，选d

发表于 2021-05-17 15:33:00
0 0
doopug

选d....

发表于 2021-05-17 13:05:33
0 0
刘玮

就是D，。。。

发表于 2020-09-15 22:54:07
0 0
起石沉浮

由于涉及到一个用来给数据分大小的值 

所以很容易能理解，最好的情况就是，刚刚好取到中间值，然后两边大小相等，这样分下去的就是logN
又需要排序就是N*logN

最坏的情况，就是一串数字已经排序好，每次我都是取最大的值，然后始终都是得到一边有数字，另一边没有数字，这样加上排序，时间复杂度就是n^2

发表于 2018-10-11 19:39:39
0 0
盖子子

D 随机快速排序的平均时间复杂度为O(nlogn)，当数组为逆序的时候，按从小到大的顺序进行排序时为最差情况，时间复杂度为O(n^2)

发表于 2018-10-11 19:39:27
0 0
伸手揪云

如果基准数恰是中位数，每次只需遍历当前数组长度的一半即可排好一个数，如果基准数是极值，就和冒泡，选择没啥区别了

发表于 2018-10-11 19:39:22
0 0
幸运鹅er

D 如果每一次都点背，选到最边的数作为划分的话就是最坏的

发表于 2018-10-11 19:39:15
0 0
初年

D:平均就是数学期望，最坏的时候也就是在随机快速排序的partition过程的时候每次选取标志数的时候都大或者最小值，此时的时间复杂度为O(n^2)

发表于 2018-10-11 19:39:05
0 0
问题信息
分类：数据结构 - 快速排序
难度:
最新校招难题刷题，快来进刷题群吧
相关试题