首页 > 试题广场 >

在下列几种排序方法中，空间复杂度最高的是（）

[单选题]
在下列几种排序方法中，空间复杂度最高的是（） 
  • 归并排序
  • 快速排序
  • 插入排序
  • 选择排序
查看答案及解析
添加回答
推荐
已注销头像 已注销
正确答案选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)
fghfghggh头像 fghfghggh
归并不是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)
sunlight_run头像 sunlight_run
归并涉及到合并问题，需要较多中间存储空间
发表于 2017-07-06 19:56:31 回复(0)
提交观点

问题信息

C++工程师 4399游戏 2017 复杂度 排序 Java工程师 销售
来自：职能类模拟题1
上传者：牛100
难度：
8条回答 6115浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号