首页 > 试题广场 >

下述几种排序方法中，要求内存最大的是（）

[单选题]
下述几种排序方法中，要求内存最大的是（） 
  • 快速排序
  • 插入排序
  • 选择排序
  • 归并排序
查看答案及解析
添加回答
程序猿Go师傅头像 程序猿Go师傅
编辑于 2019-10-21 21:27:27 回复(0)
菜鸟葫芦娃头像 菜鸟葫芦娃
这个题要求的是空间复杂度。

冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)

快速排序空间复杂度为logn(因为递归调用了) ,
归并排序空间复杂是O(n),需要一个大小为n的临时数组.

基数排序的空间复杂是O(n),桶排序的空间复杂度不确定

发表于 2015-10-12 13:18:45 回复(2)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
快排 O(1)
插排 O(1)
选择排序 O(1)
归并      O(n)
多说一点 堆排 根据实现策略，有O(1)的方法，也有O(n)的笨方法
发表于 2018-06-17 17:26:51 回复(0)
扛竹子的伙夫头像 扛竹子的伙夫
一般这种问题考察时间复杂度，没想到这里考察空间复杂度，可见基础还是要扎实，不能只学重点
发表于 2017-08-26 14:05:13 回复(0)
细雨湿身头像 细雨湿身
归并排序空间复杂是O(n),需要一个大小为n的临时数组.

基数排序的空间复杂是O(n)

发表于 2016-10-03 08:58:01 回复(0)
水水echo头像 水水echo
这个问题做的时候有点困惑，因为快排最好情况下空间复杂度是O(logn),但是最坏的情况下栈的深度达到O（n）
发表于 2016-09-18 11:53:29 回复(0)
Mila呀头像 Mila呀
快排的空间复杂度不是O(nlogn)么
发表于 2016-08-26 16:01:43 回复(1)
提交观点

问题信息

排序
来自：滴滴出行2016研发工...
难度：
7条回答 20525浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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