首页 > 试题广场 >

快速排序在最坏情况下的时间复杂度为？

[单选题]

快速排序在最坏情况下的时间复杂度为（）

查看答案及解析

推荐

MyGoodHelper

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为

，最终其时间复杂度为O(n*n)。

编辑于 2015-01-31 10:45:10 回复(0)

ellie2dina

快排最坏情况，退化成冒泡排序

发表于 2015-08-31 17:04:54 回复(0)

程序猿Go师傅

编辑于 2019-10-21 20:56:27 回复(0)

牛客-007

答案：D

快速排序是不稳定的排序，平均情况下时间复杂度为O(nlog2n)最坏情况下时间复杂度为O(n*n)

发表于 2015-01-12 16:00:13 回复(0)

kiracici

最坏情况下是D

发表于 2015-05-20 14:14:47 回复(0)

牛客874504号

快排平均情况O(nlogn)

最好情况O(nlogn)

最坏情况O(n的平方)

发表于 2015-03-31 22:55:26 回复(0)

提交观点

问题信息

复杂度欢聚集团排序

来自：2025年秋招-中国移...

上传者：小牧魔法袋

难度：

6条回答 186收藏 25712浏览

扫一扫，把题目装进口袋