首页 > 试题广场 >

在下列几种排序方法中,空间复杂度最高的是()

[单选题]
在下列几种排序方法中,空间复杂度最高的是()
  • 归并排序
  • 快速排序
  • 插入排序
  • 选择排序
推荐
正确答案选A
归并排序空间复杂度为O(n)
快速排序:
      就地快排空间复杂度为O(1) 
      使用递归:
            每一次都平分数组,即最优情况是O(logn)
            退化为冒泡排序,即最差情况是O(n)
插入和选择都是O(1)
编辑于 2017-05-24 14:55:59 回复(0)
 关于快速排序的空间复杂度的问题并不是简单的nlogn
首先就地快速排序使用的空间是O(1)的,也就是个常数级;而真正消耗空间的就是递归调用了,因为每次递归就要保持一些数据;
    最优的情况下空间复杂度为:O(logn)  ;每一次都平分数组的情况
    最差的情况下空间复杂度为:O( n )      ;退化为冒泡排序的情况

发表于 2018-06-12 21:02:09 回复(0)
归并涉及到合并问题,需要申请临时空间存放临时结果
发表于 2016-12-20 17:37:53 回复(0)
空间复杂度:
归并排序:O(n)
快排:O(logn)
插入排序:O(1)
选择排序:O(1)
发表于 2017-02-19 20:00:45 回复(0)
归并不是O(1)吗?
发表于 2018-10-07 14:10:18 回复(0)
其实归并排序的空间复杂度可以优化为O(1),感兴趣的同学可以Google一下。
发表于 2018-01-26 10:44:06 回复(0)
归并需要构造多个辅助数组,必然需要很多空间
发表于 2017-12-18 12:17:07 回复(0)
归并涉及到合并问题,需要较多中间存储空间
发表于 2017-07-06 19:56:31 回复(0)