包含时间数据的几乎排序列表的有效排序算法？

Question

这个名字说的都是真的.我怀疑插入排序是最好的,因为它是一般的大多数排序数据的最佳排序.但是,由于我对数据有了更多了解,因此有可能还有其他种类可供选择.所以其他相关的信息是:

1)这是时间数据,这意味着我可以推测可以为数据排序创建有效的哈希值.2)数据不会同时存在.相反,我将阅读可能包含单个向量,或十几个或数百个向量的记录.我想在5秒钟内输出所有时间.因此,在插入数据时进行排序的排序可能是更好的选择.3)内存不是一个大问题,但CPU速度是因为这可能是系统的瓶颈.

鉴于这些条件,任何人都可以提出一个除了插入排序之外可能值得考虑的算法吗？另外,如何定义"主要排序"以确定什么是良好的排序选项？我的意思是我如何查看我的数据并决定'这不像我想象的那样排序,也许插入排序不再是最好的选择'？任何与文章相关的链接都可以理解,该文章考虑了流程复杂性,这些文章更好地定义了相对于学位数据的复杂性.

谢谢

编辑:谢谢大家的信息.我现在将进行简单的插入或合并排序(无论我已经预先编写).但是,一旦接近优化阶段,我将尝试其他一些方法(因为他们需要付出更多努力才能实现).我很感激帮助

Answer 1

您可以采用您建议的选项（2） - 在插入元素时对数据进行排序。

使用按时间升序排序的跳跃列表来维护数据。

• 一旦新的主菜到达 - 检查它是否比最后一个元素大（简单快捷）如果是 - 只需将其附加（很容易在跳过列表中执行）。对于这些情况，跳跃列表平均需要添加 2 个节点，并且O(1)对于这些情况将平均。
• 如果该元素不大于最后一个元素 - 将其作为标准插入操作添加到跳跃列表中，这将是O(logn).

这种方法将产生O(n+klogn)算法，其中k是无序插入的元素数量。