快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法

admin2019-07-12  23

问题 快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了_______算法设计策略。已知确定着基准元素操作的时间复杂度为O(n),则快速排序算法的最好和最坏情况下的时间复杂度为_______ 。
(62)

选项 A、O(n)和O(nlgn)
B、O(n)和O(n2)
C、O(nlgn)和O(nlgn)
D、O(nlgn)和O(n2)

答案D

解析 将数据分成若干份,每份单独处理后再合并,其思想为分治。理想情况下,快速排序每次将数据划分为规模相近的两部分,并递归至不可再划分,因此其时间复杂度为O(nlgn)。在最坏情况下,每次划分都极不均匀,如一个类别中仅有一个元素,另一个类别中包含剩余所有元素。这时划分的复杂度为0(n),n次操作的总复杂度为O(n2)。
转载请注明原文地址:https://kaotiyun.com/show/m2CZ777K
0

随机试题
最新回复(0)