什么是最快的数据结构（和排序算法）来对一组数字进行排序？

Question

4

我需要一个数据结构，能够容纳一组数字并尽可能快地对它们进行排序。

我认为列表很好，因为将新数字插入到列表中比向量更容易（后者需要复制插入后的元素）。但是，遍历链表（我使用排序列表作为查找来自无序映射的对象）可能会慢得多，因为内存分散在堆中。

我想使用map，但由于非连续性质，这也会有不良的内存访问吗？

另一个想法是使用静态分配的数组（带有大量空白空间）和快速的排序算法.....

总之，我需要一个数据结构，允许我插入新元素并尽快重新排序这些元素。这些元素将是数字。

感谢任何帮助！

- intrigued_66

请参考这个问题来选择您的标准容器。 - TemplateRex

这个问题很难回答，因为“最快”的速度不仅取决于大O复杂度，还取决于常数项（即具有糟糕大O的数据结构可能在“较小”的输入大小上优于“更好”的数据结构）。只有使用真实数据进行基准测试才能告诉您什么是“更好的”，因为“小”通常可以相当大。 - Benjamin Bannier

5个回答

0

你可能需要考虑如何在你的vector/map中存储这些对象。使用带有必要比较函数的智能指针可能是你想要的。

- Paul Evans

我只是存储基本类型吗？我想要一个存储容器来存储排序后的数字，并允许我插入/迭代它们。 - intrigued_66

0

如果你所说的“一组数字”是指每个数字只出现一次，并且你想要它排序，那么请使用std::set。老实说，除非你处理的数据量非常大，否则std::list甚至std::vector可能已经足够了。

- Neil Kirk

0

Boost.Containers库包含一个flat_set数据结构。它在std::vector数据存储的基础上实现了std::set接口。根据文档，它有以下优点：

- TemplateRex

-1

什么是最快的数据结构？

一个数组。

（以及排序算法）

如果你可以容忍最坏情况的行为，那么快速排序可能是最快的。否则，可能是堆排序。

- user207421

@downvoters 真的很不可思议。这是数据结构101。你甚至没有给出任何不同意见的提示。 - user207421

没有点踩，但我认为这个问题需要更多的细节才能回答（例如，即使是bogosort在某些输入上也会优于你提到的两种算法）。 - Benjamin Bannier

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikhil · Accepted Answer

最快的数据结构是数组-内存中连续的区域，对缓存非常优化。

排序取决于情况。将快速排序与插入排序结合起来，用于对小于一定大小的子数组进行排序可能是您的最佳选择，而无需采取更奇特的方法。