在 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 选项。
