这个名字真的说明了一切。我怀疑插入排序是最好的，因为它通常是大多数排序数据的最佳排序。但是，由于我对这些数据了解更多，所以有可能还有其他类型的数据值得关注。所以其他相关信息是:
1) 这是时间数据，这意味着我推测可以创建一个有效的散列来排序数据。 2)数据不会同时存在。相反，我将阅读可能包含单个 vector 或十几个或数百个 vector 的记录。我想在 5 秒的窗口内输出所有时间。因此，在我插入数据时进行排序的排序可能是更好的选择。 3) 内存不是大问题，但CPU 速度可能是系统的瓶颈。
鉴于这些条件，除了插入排序之外，任何人都可以提出一个可能值得考虑的算法吗？另外，如何定义“大多数排序”来决定什么是好的排序选项？我的意思是我如何查看我的数据并决定“这不像我想象的那样排序，也许插入排序不再是最佳选择”？任何链接到一篇考虑过程复杂性的文章的链接都将受到赞赏，该文章更好地定义了相对于学位数据的复杂性。
谢谢
编辑: 谢谢大家提供的信息。我现在将使用简单的插入或合并排序(无论我已经预先编写的)。但是，一旦接近优化阶段，我将尝试其他一些方法(因为它们需要更多的努力来实现)。感谢您的帮助
最佳答案
您可以采用您建议的选项 (2) - 在插入元素时对数据进行排序。
使用 skip list ，按时间排序，升序维护您的数据。
- 一旦新主菜到达 - 检查它是否比上一个大
元素(简单快捷)如果是 - 只需附加它(在跳过列表中很容易做到)。这
对于这些情况，跳跃列表平均需要添加 2 个节点，并且将是
O(1)这些案例的平均值。 - 如果元素不大于最后一个元素 - 将其添加到
跳过列表作为标准插入操作，这将是
O(logn)。
这种方法将产生O(n+klogn) 算法，其中k 是乱序插入的元素数。
关于c++ - 包含时间数据的几乎排序列表的有效排序算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11016630/