问题
单项选择题 共用题干题
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（1）算法设计策略。已知确定基准元素操作的时间复杂度为Θ（n），则快速排序算法的最好和最坏情况下的时间复杂度为（2）。
空白（2）处应选择（）
A.Θ（n）和Θ（nlgn）
B.Θ（n）和Θ（n2）
C.Θ（nlgn）和Θ（nlgn）
D.Θ（nlgn）和Θ（n2）
答案
参考答案：D
解析：本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为Θ(n)，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n／2)+Θ(n)解该递归式，可得时间复杂度为Θ(nlgn)。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-1个元素，此时T(n)=T(n-1)+Θ(n)解该递归式，可得时间复杂度为Θ(n)。