首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在内存使用方面的高效排序算法?

问在内存使用方面的高效排序算法?
EN

Stack Overflow用户
提问于 2013-07-06 10:53:40
回答 2查看 7.6K关注 0票数 4

因此,对于一个项目,我正在工作的一个部分需要排序。这一切都是用MIPS汇编语言完成的。目前,我正在考虑使用插入还是冒泡排序。我知道与Merge和Quick sort相比,这两种方法比较慢,但我想这是最少的静态/动态指令。在这种情况下,哪一个会更有效?我觉得在速度和内存使用之间总是有一个权衡。这是真的吗?

EN

回答 2

Stack Overflow用户

发布于 2013-07-07 17:36:25

这在很大程度上取决于要排序的数组的大小。对于大数组,简单的排序算法,如冒泡排序,往往非常慢。

大多数人不知道,因为代码很小,对于足够小的数组,冒泡排序甚至可以比快速排序(和其他“快速”排序)更快。

所以:

  1. 如果你的数组的大小是可变的,如果你的数组很大,那就是最大的数组大小--使用快速排序(或类似的排序)--或者稍后你应该解释一下汇编语言程序为什么会这么慢。:)
  2. 如果数组足够小(可能多达几百个元素),使用冒泡排序,你就会两者兼得--小代码和高performance.
  3. In我的经验是,数组排序不是那么常见的操作。您真的真的确定需要对这些数组进行排序吗?
票数 2
EN

Stack Overflow用户

发布于 2013-07-06 10:59:09

我对insert sort的记忆是每次接收一条新记录,因此如果您已经有数据要排序,则需要两倍的数据大小-一个用于读取,一个用于写入。对于任何非平凡的数据集,这可能会比排序算法消耗更多的内存。冒泡排序可以就地完成(也就是说,如果你已经有一个数据块要排序,它只需要足够的额外内存来存储一条记录,甚至一个字节,具体取决于数据)。

冒泡排序还需要编写更少的代码。

至于总是在速度和内存(或者,实际上,任何两种资源)之间进行权衡,情况并不总是这样。但是,如果方法A比方法B更快、更简单,并且使用的内存更少,那么B就不会出现争用。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17499213

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档