首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 归并排序
题目

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

A.归并排序

B.快速排序

C.插入排序

D.选择排序

上一题 下一题
解答

正确答案是 A

归并排序空间复杂度为O（n）
快速排序：
      就地快排空间复杂度为O（1） 
      使用递归：
            每一次都平分数组，即最优情况是O（logn）
            退化为冒泡排序，即最差情况是O（n）
插入和选择都是O（1）
C 8条回复 评论
匀斋

看了两遍，慢慢消化吸收知识点

发表于 2021-09-14 12:40:00
0 0
简书

哇塞，果然还是学习是最重要的。

发表于 2021-09-14 12:15:00
0 0
小小精灵

归并涉及到合并问题，需要较多中间存储空间

发表于 2018-10-13 14:58:41
0 0
站桩灵

归并需要构造多个辅助数组，必然需要很多空间

发表于 2018-10-13 14:58:22
0 0
落地成盒

其实归并排序的空间复杂度可以优化为O(1)，感兴趣的同学可以Google一下。

发表于 2018-10-13 14:58:11
0 0
猪猪猪

归并涉及到合并问题，需要申请临时空间存放临时结果

发表于 2018-10-13 14:58:02
0 0
浅色回忆

空间复杂度：
归并排序：O(n)
快排：O(logn)
插入排序：O(1)
选择排序：O(1)

发表于 2018-10-13 14:57:47
0 0
浅色回忆

关于快速排序的空间复杂度的问题并不是简单的nlogn
首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
    最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况
    最差的情况下空间复杂度为：O( n )      ；退化为冒泡排序的情况

发表于 2018-10-13 14:57:34
0 0
问题信息
分类：数据结构 - 归并排序
难度:
最新校招难题刷题，快来进刷题群吧
相关试题