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