在快速排序中，要使最坏情况的空间复杂度为O(log2n )则

[单选题]

在快速排序中，要使最坏情况的空间复杂度为O(log₂n )则要对快速排序作( )修改。

```
划分元素为三者取中
```
```
采用表排序
```
```
先排最小集合
```
```
先排大集合
```

查看答案及解析

推荐

白驹之过隙

选A。

快速排序的思想：

先从数列中取出一个数作为基准数
分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
再对左右区间重复第二步，直到各区间只有一个数

最优的情况下空间复杂度为：O(log₂n) ；每一次都平分数组的情况，基准数尽量为中间数。

编辑于 2019-09-16 14:27:44 回复(0)

emptyCoder

快速排序的最坏情形是数组为正序或逆序，如果pivot总是选择第一个元素，那么每次划分只得到一个比上一次划分少一个记录的子序列，此时需要执行 $n$ 次递归调用。显然，采用A（划分元素为三者居中），能够将每次待排序的part尽可能一分为二，从而使得递归深度为 $\lceil log(2, n) \rceil$ )，即空间复杂度为 $O(log2n)$