快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作时间复杂度为Θ(n)，则快速排序算法最好和最坏情况下时间复杂度为（请作答此空）。
- A.见图A
- B.见图B
- C.见图C
- D.见图D
正确答案及解析
正确答案
D
解析
快速排序采用分治法思想。快速排序最好情况时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序时间复杂度为O(n2)。
