2. 从业资格
  3. 在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思

在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思

练习题库2022-08-02  65
问题 在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思想,对n个元素划分，先确定第k小的数，根据i和k的大小关系,进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的（64）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（65）。A.Θ（n）B.Θ（lgn）C.Θ（nlgn）D.Θ（n2）
选项 A.Θ（n）
B.Θ（lgn）
C.Θ（nlgn）
D.Θ（n2）
答案 D
解析 本题考查数据结构基础知识。快速排序一种分治的排序方法，其思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置，将原来的线性表划分为前后两部分，前部分元素都小于基准元素，后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ（nlog2n）,最坏情况下时间复杂度为Θ（n2），最好情况下的时间复杂度为Θ（nlog2n）；快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ（n），其他需要Θ（nlog2n）。根据以上描述，本题依次选C、D选项。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2407853.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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