首页 > 试题广场 >

判断下列说法是否正确：在快速排序、堆排序、归并排序和插入排序

[单选题]
判断下列说法是否正确：在快速排序、堆排序、归并排序和插入排序中，堆排序所需要的附加存储开销最大。（）

  • 正确
  • 错误
查看答案及解析
添加回答
onlyxxx头像 onlyxxx
B，归并O(n)
发表于 2019-09-12 16:13:38 回复(0)
更多回答
推荐
白驹之过隙头像 白驹之过隙
选B。考察的是不同排序方式的空间复杂度。
归并排序存储开销大。
  • 快速排序：选一个基准值进行左右分区，比基准小的放到左边，比基准大的放在基准右边。空间复杂度为O(logn )
  • 堆排序：利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。空间复杂度为O(1)
  • 归并排序：先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表。空间复杂度为O(n)
  • 插入排序：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。空间复杂度为O(1)


编辑于 2019-09-11 14:14:19 回复(0)
仙女山的太阳^_^头像 仙女山的太阳^_^
B。
堆排序的空间开销为O(1)，插入排序的空间开销为O（1），归并排序的空间开销为O（n），快速排序的空间开销为O（logn）
发表于 2019-09-11 09:38:52 回复(0)
爱笑的人儿2023头像 爱笑的人儿2023
归并排序的最大！除了递归的深度还需要申请与原数组同样大小的存储空间，所以总的存储开销为O（n+logn）
发表于 2019-09-10 15:27:34 回复(0)
Wilbur.头像 Wilbur.
堆排序不需要附加存储，归并排序所需要的附加存储是O（n）
发表于 2022-08-20 17:55:47 回复(0)
Juventus-小九头像 Juventus-小九
归并排序开销最大
发表于 2022-01-26 16:02:20 回复(1)
jingjinghao头像 jingjinghao
空间复杂度是看算法运行时占用的内存空间大小，在实时操作系统和嵌入式的平台环境下开发时是重要的考量因素。
发表于 2019-09-11 06:59:48 回复(0)
提交观点

问题信息

排序
上传者：zsw3
难度：
7条回答 2767浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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