校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
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 11条回复 评论
梦里不知身是客

好多HR热衷于这样问……

发表于 2024-07-03 23:00:00
0 0
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