9

这个名字真的说明了一切。我怀疑插入排序是最好的，因为它通常是大多数排序数据的最佳排序。但是，由于我对数据了解得更多，因此有可能还有其他类型的数据值得关注。所以其他相关的信息是：

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

鉴于这些条件，除了插入排序之外，任何人都可以提出一种可能值得考虑的算法吗？另外，如何定义“大部分排序”来决定什么是好的排序选项？我的意思是我如何查看我的数据并决定'这不像我想象的那样排序，也许插入排序不再是最好的选择'？任何链接到考虑了过程复杂性的文章，该文章更好地定义了相对于学位数据的复杂性，都将被排序。

谢谢

编辑：谢谢大家的信息。我现在将使用简单的插入或合并排序（无论我已经预先编写过哪个）。但是，一旦接近优化阶段，我将尝试其他一些方法（因为它们需要更多的努力来实现）。我很感激帮助

4

6 回答 6

3

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

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

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

这种方法将为您提供O(n+klogn)算法，其中k是乱序插入的元素数量。

于 2012-06-13T14:17:53.710 回答
2

如果您实现自然版本，我会进行合并排序，如果您有任何问题，您会得到O(N)一个典型和最坏情况的最佳情况。O(N log N)插入你会得到最坏的情况O(N^2)和最好的情况O(N)。

于 2012-06-13T14:12:47.930 回答
2

您可以对包含不合时宜的元素n的大小列表进行排序。kO(n + k lg k)

请参阅：http ://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of- elements-say-up-to-1-4-of-the-total-whose-positions-are-known/answer/Mark-Gordon-6?share=1

基本思想是这样的：

  • 遍历数组的元素，构建一个递增的子序列（如果当前元素大于或等于子序列的最后一个元素，则将其追加到子序列的末尾。否则，丢弃当前元素和最后一个元素子序列）。这需要O(n)时间。
  • 2k由于k元素不合适，您将丢弃的元素不超过元素。
  • 使用归并排序或堆排序等排序算法对丢弃的2k元素进行排序。O(k lg k)
  • 您现在有两个排序列表。O(n)像在合并排序的合并步骤中那样及时合并列表。

总时间复杂度 =O(n + k lg k)

整体空间复杂度 =O(n)

O(1)（如果可以在空间中合并，这可以修改为在空间中运行O(1)，但这绝不是微不足道的）

于 2014-10-31T00:27:54.060 回答
1

在不完全理解问题的情况下，Timsort可能符合要求，因为您声称您的数据大部分已经排序。

于 2012-06-13T22:01:46.137 回答
0

有许多自适应排序算法专门设计用于对大多数排序的数据进行排序。忽略您正在存储日期的事实，您可能希望将平滑排序或笛卡尔树排序视为可以对在最坏情况 O(n log n) 时间和最佳情况 O(n) 时间合理排序的数据进行排序的算法时间。Smoothsort 还具有只需要 O(1) 空间的优点，就像插入排序一样。

使用所有内容都是日期并因此可以转换为整数的事实，您可能希望使用三个枢轴选择的中值来查看二进制快速排序（MSD 基数排序）。该算法具有最佳情况 O(n log n) 性能，但具有非常低的常数因子，使其非常具有竞争力。最坏的情况是 O(n log U)，其中 U 是每个日期的位数（可能是 64），这还不错。

希望这可以帮助！

于 2012-06-13T16:43:11.200 回答
0

如果您的 OS 或 C 库提供了合并排序功能，它很可能已经处理了在 O(N) 时间内运行的给定数据是部分有序（在任何方向上）的情况。

否则，您可以从您最喜欢的 BSD 操作系统中复制可用的合并排序。

于 2012-06-13T16:50:07.950 回答