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

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

admin2016-05-10  73
问题 快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了  (61)  算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为  (62)  。
(62)
选项 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)
    解该递归式，可得时间复杂度为Θ(n2)。
转载请注明原文地址:https://kaotiyun.com/show/KkRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)