在 n 个数数组中确定其第 i(1 ≤ i ≤ n) 小数时，可以采用快速排序算法中划分思想 , 对 n 个元素划分，先确定第 k 小数，根据 i 和 k 大小关系 , 进一步处理，最终得到第 i 小数。划分过程中，最佳基准元素选择方法是选择待划分数组（ 此空作答 ）元素。此时，算法在最坏情况下时间复杂度为（不考虑所有元素均相等情况）（ ）。
- A.Θ(n)
- B.Θ(lgn)
- C.Θ(nlgn)
- D.Θ(n2)
正确答案及解析
正确答案
D
解析
本题考查数据结构基础知识。快速排序一种分治排序方法，其思想是：将原问题分解为若干个规模更小但结构与原问题相似子问题。递归地解这些子问题，然后将这些子问题解组合为原问题解。快速排序每一趟结果都是找到一个基准元素放置于线性表中部位置，将原来线性表划分为前后两部分，前部分元素都小于基准元素，后部分元素都大于基准元素。快速排序总关键字比较次数为 Θ (nlog2n), 最坏情况下时间复杂度为 Θ ( n 2 ) ，最好情况下时间复杂度为 Θ (nlog2n) ；快速排序是不稳定排序。最坏情况下需要栈空间为 Θ （ n ），其他需要 Θ (nlog2n) 。根据以上描述，本题依次选 C、D 选项。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案