2. 从业资格
  3. 快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待

快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待

资格题库2022-08-02  104
问题 快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（  ）算法设计策略。已知确定着基准元素操作的时间复杂度为 O(n) ，则快速排序算法的最好和最坏情况下的时间复杂度为（ 此空作答 ）。A.O(n)和O(nlgn)B.O(n)和O(n2)C.O(nlgn)和O(nlgn)D.O(nlgn)和O(n2)
选项 A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)
答案 D
解析 将数据分成若干份，每份单独处理后再合并，其思想为分治。 理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为 O(nlgn) 。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为 O(n) ， ” 次操作的总复杂度为 O(n2) 。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2408354.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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