以下排序方式中占用O（n）辅助存储空间的是

[单选题]

查看答案及解析

Orange。

归并排序在归并过程中需要与原始序列相等的存储空间O（n）用于存放归并结果：

递归实现的归并排序还需考虑深度为log₂n的栈空间，因此空间复杂度为O（n+log₂n）;

而非递归实现的归并排序避免了递归时深度为log₂n的栈空间，因此空间复杂度为O（n）。

归并排序是所有排序中占用内存最多，但是效率比较高且稳定的算法，即牺牲内存提高了效率。

发表于 2017-08-17 09:07:58 回复(0)

和风气

堆排序在原来的数组上就可以进行，归并排序需要创建新数组来完成新顺序存储

发表于 2019-12-16 19:59:18 回复(0)

提交观点

问题信息

排序

上传者：loulou小妖精

难度：

2条回答 128收藏 5487浏览

扫一扫，把题目装进口袋