首页 > 试题广场 > 在快速排序中,要使最坏情况的空间复杂度为O(log2n )则
[单选题]
在快速排序中,要使最坏情况的空间复杂度为O(log2n )则要对快速排序作(  )修改。


  • 划分元素为三者取中
  • 采用表排序
  • 先排最小集合
  • 先排大集合
推荐
A
快速排序的思想:
  1. 先从数列中取出一个数作为基准数
  2. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
  3. 再对左右区间重复第二步,直到各区间只有一个数
最优的情况下空间复杂度为:O(log2n)  ;每一次都平分数组的情况基准数尽量为中间数
编辑于 2019-09-16 14:27:44 回复(0)

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

编辑于 2019-09-13 10:02:55 回复(0)