sorting - 在内存使用方面的有效排序算法？

Question

因此，对于一个项目，我正在处理其中一个需要排序的部分。这一切都是用 MIPS 汇编语言完成的。目前我正在争论使用插入或冒泡排序。我知道这两个与合并和快速排序相比很慢，但我试图让这是最少数量的静态/动态指令。在这种情况下，哪个更有效？我觉得在速度和内存使用之间总是有一个权衡。真的吗？

Answer 1

这在很大程度上取决于您要排序的数组的大小。对于大数组，简单的排序算法，因为冒泡排序往往很慢。

大多数人不知道，由于代码量小，对于足够小的数组，冒泡排序甚至比快速排序（和其他“快速”排序）还要快。

所以：

1. 如果您的数组是可变大小并且最大大小如果非常大 - 使用快速排序（或类似） - 或者稍后您应该解释汇编程序如何如此缓慢。:)

2. 如果数组足够小（可能多达数百个元素），请使用冒泡排序，您将拥有两者 - 小代码大小和高性能。

3. 以我的经验，数组排序并不是那么常见的操作。您真的非常确定需要对这些数组进行排序吗？

Answer 2

我对插入排序的回忆是您一次收到一条新记录，因此如果您已经有数据要排序，您将需要两倍大小的数据 - 一个用于读取，一个用于写入。对于任何重要的数据集，这可能会比排序算法消耗更多的内存。冒泡排序可以就地完成（即，如果您已经有一块数据要排序，它只需要足够的额外内存来存储一条记录，甚至一个字节，具体取决于数据。

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

至于在速度和内存（或者实际上是任何两种资源）之间总是存在权衡，情况并非总是如此。但是，如果方法 A 比方法 B 更快、更简单，并且使用的内存更少，那么 B 就不会真正出现争用。