最佳的连续排序算法？

Question

我有一组双精度数据，需要始终按顺序排序。在添加数据时，最好的排序算法是什么？

所谓“最好”，是指数据数量的大O表示法尽可能小，最坏情况下数据数量的小O表示法尽可能小，并且空间需求尽量小，如果可能的话，按照这个顺序。

数据集大小非常不确定，从少量数据（30）到大量数据（+10M）。

- Wilhelm

---

是否有其他相关要求会对内存分配方案的使用产生限制？性能要求呢？在许多情况下，“最佳”算法取决于特定的应用程序。 - NoMoreZealots

Pete：显然，我们在谈论非常大量的数据。否则，超级效率是不需要的。 - lkessler

问题中并没有暗示任何具体的要求。而且也没有说明是否有特定的接口要求。例如，使用这些数据的函数可能会期望一个数组或链表。这两者都会对排序算法产生影响。询问实际需求比推测更好。 - NoMoreZealots

我需要的唯一功能是知道集合中第i个排序元素。 - Wilhelm

如果是一个大数据集，中序遍历树将不会很高效。也就是说，如果我需要第1,000,000个元素，意味着我必须遍历999,999个元素才能获得它。你可以提供更多关于问题空间的细节吗？ - NoMoreZealots

Answer 1

构建一个自平衡二叉树，例如红黑树或AVL树，将允许Θ(lg n)的插入和删除操作，并且通过深度优先遍历以Θ(n)的时间复杂度检索所有元素的排序顺序，内存使用量为Θ(n)。虽然实现有些复杂，但它们是高效的，大多数语言都会有库实现，因此在大多数情况下它们是一个不错的首选。

此外，可以通过在树中注释每个边缘（或等价地，节点）下面的总节点数来完成第i个元素的检索。然后，可以使用类似于以下内容的东西在Θ(lg n)的时间和Θ(1)的空间内查找第i个元素：

node *find_index(node *root, int i) {
  while (node) {
    if (i == root->left_count)
      return root;
    else if (i < root->left_count)
      root = root->left;
    else {
      i -= root->left_count + 1;
      root = root->right;
    }
  }
  return NULL; // i > number of nodes
}

在 Debian 的 libavl 中可以找到支持此功能的实现；不幸的是，维护者的网站似乎已经关闭，但可以从 Debian 的服务器 检索到。

- bdonlan

---

B+树在包含超过16,000个条目的树中比标准红黑树快得多。请参见：http://idlebox.net/2007/stx-btree/ - lkessler

我认为这个问题有点笼统，无法给出具体的“最佳”答案。我们还没有完整的问题需求集。 - NoMoreZealots

红黑树在O(N log N)中检索，而不是O(n)。红黑树的优点是删除更便宜...但这不是原始问题所担心的成本。 - SPWorley

@Arno，通过进行中序遍历，读取所有项目的时间复杂度为Θ(n)。@Pete，通过在边缘上注释下方节点数量，可以使提取特定第n个元素的时间复杂度为Θ(lg n)。 - bdonlan

是的，你说得对。但如果你忽略了那个细节，其他所有内容都可以在维基百科上找到。关键是，那是一个相关的细节，需要使答案与教科书答案有所不同。 - NoMoreZealots

Answer 2

用于数据库程序索引的结构是B+树。它是一个平衡的桶式n叉树。

来自维基百科：

对于一个具有h级索引的b阶B+树：

• 存储的最大记录数为n = b^h
• 最小键数为2(b/2)^(h−1)
• 存储树所需的空间为O(n)
• 在最坏情况下，插入一条记录需要O(log-b(n))个操作
• 在最坏情况下，查找一条记录需要O(log-b(n))个操作
• 在最坏情况下，删除（先前定位的）记录需要O(log-b(n))个操作
• 执行范围查询并且范围内有k个元素时，需要进行O(log-b(n+k))个操作。

我在我的程序中使用这个。你可以随着数据的到来将其添加到结构中，然后始终按顺序遍历它，从前往后或从后往前，或者快速搜索任何值。如果您找不到该值，您将拥有插入点，在那里可以添加该值。

您可以通过调整桶的大小b来优化程序的结构。

一个关于B+树的有趣演示： Tree-Structured Indexes 您可以 获取完整的C++代码。

---

编辑：现在我看到了您的评论，您需要知道“集合中第i个排序元素”的要求是非常重要的。突然之间，许多数据结构都不再是最优的选择。

您可能最好使用SortedList，甚至更好的是SortedDictionary。请参阅文章：从SortedList中挤出更多性能。这两种结构都有一个GetKey函数，可以返回第i个元素。

- lkessler

Answer 3

可能是堆排序。堆排序只需要O(log N)的时间添加新数据，而且可以在任何时候用O(N log N)的时间弹出结果。

如果每次都需要整个列表排序，那么除了插入排序之外，没有太多其他选择。虽然它可能是O(N^2)，但是通过使用跳表，你可以将其变为O(N log N)。

- SPWorley

Answer 4

我会使用堆/优先队列。最坏情况下的运行时间与平均情况相同。下一个元素可以在O(log n)时间内找到。

这是我从这段代码中推导出来的模板化C#实现。

- hughdbrown

Answer 5

好的，您想要对数据进行排序，但需要通过索引号提取数据。

从基本的树结构开始，例如前面提到的红黑树。

修改树算法，使得在将元素插入树中时，所有遇到的节点都会在插入和删除过程中保持每个分支下元素数量的计数。

然后，在从树中提取数据时，您可以在计算索引号时实时计算，并根据索引号是大于还是小于正在提取的索引号来确定应该选择哪个分支。

还有一点需要考虑。在使用动态内存分配的树中，10M个以上的元素会吸收大量的内存开销。也就是说，指针可能占用比实际数据更多的空间，再加上用于实现数据结构的其他成员。这将导致严重的内存碎片化，并在最坏的情况下降低系统的整体性能（在虚拟内存中来回传输数据）。您可以考虑实现块和动态内存分配的组合。将树结构按数据块进行排序，从而减少内存开销。

- NoMoreZealots

Answer 6

如果您只需要像评论中所说的那样知道第i个最小元素，请使用BFPRT算法，该算法以作者的姓氏命名：Blum，Floyd，Pratt，Rivest和Tarjan，并且通常被认为是同一篇论文中最大的计算机科学大脑集中体现。 O(n)最坏情况。

- Rui Ferreira

---

如果维基百科上的内容是正确的，它的最坏情况是O(n^2)。通过修改，似乎可以将其优化为O(nlogn)，与使用树相同。但说实话，维基百科在描述该算法方面做得不太好。你有更好的信息来源吗？ - Wilhelm

该算法的目标是在某一点上获取第i小的元素，时间复杂度为O(n)。使用排序和树的替代方案的时间复杂度为O(nlogn)。基本上，您可以对其进行排序并获取第i个元素。如果您想在每个时刻都这样做，则认为最好的选择已经在上面提出。 - Rui Ferreira

如果您查看维基百科，BFPRT算法包括“中位数算法”部分。我猜前面的部分只是该算法及其与快速排序的关系的介绍。 - Rui Ferreira

检查MIT公开课程。我认为他们有一个关于顺序统计的课程。 - Rui Ferreira

Answer 7

在维基百科上查看排序算法的比较。

- Kenan E. K.

Answer 8

随机跳表也很有趣。 它们需要的空间比BST和跳表少。 插入和删除的时间复杂度为O(log n)

- Luzifer42

Answer 9

“一组双数据”是指一组实数吗？其中一个更常用的算法是堆排序，建议您查看一下。它的大多数操作都是O(n*log(n))，这相当不错，但并不符合您的所有标准。堆排序的优点是它相对简单易懂，许多编程语言提供了库来管理排序堆。”

- James Thompson