最佳连续排序算法？

Question

我有一组双精度的数据，我需要他们的列表总是排序的。在添加数据时，排序数据的最佳算法是什么？

我最好的意思是数据计数中的最小大O，数据计数中的小O(最坏的情况)，以及所需空间中的最小O，如果可能的话。

集合的大小确实是可变的，从少量(30)到大量数据(+10M)。

Answer 1

构建像red-black tree或AVL tree这样的自平衡二叉树将允许Θ(lg )插入和删除，以及Θ(n)按排序顺序(通过执行深度优先遍历)检索所有元素，并使用Θ(n)内存。实现有点复杂，但它们是高效的，而且大多数语言都会有库实现，所以它们在大多数情况下都是很好的首选。

此外，检索第i个元素可以通过注解树中的每条边(或者，等效地，节点)以及它下面的节点总数来完成。然后可以找到Θ(lg )时间和Θ(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's servers检索到它。

Answer 2

used for indexes of database programs的结构是一棵B+树。它是一个平衡的桶n-ary树。

From Wikipedia

对于具有h级索引的b-order B+树：

• 存储的最大记录数为n= b^h
• 最小键数为2(b/2)^(H Log 1)
• 存储树所需的空间为O(n)
• 插入记录在最坏的情况下需要O(log-b(n))操作

<−>H111查找记录在最坏的情况下需要O(log-b(n))操作H212

• 删除(先前定位的)记录需要O(log-b(n))操作最坏情况下，使用k个元素执行范围查询需要O(

-b(n+k))个操作。

我在我的程序中使用了这个。您可以在数据到来时将其添加到结构中，并且始终可以按顺序遍历它，从前到后或从后到前，或者快速搜索任何值。如果找不到值，则会有一个插入点，您可以在该插入点中添加值。

你可以通过使用b，存储桶的大小来优化程序结构。

关于B+树的有趣演示文稿：Tree-Structured Indexes

你可以使用get the entire code in C++。

编辑:现在我看到您的评论，您需要知道“集合中的第i个排序元素”是一个重要的要求。突然之间，这使得许多数据结构变得不是最优的。

你最好是用一个SortedList，或者更好的，一个SortedDictionary。请参阅文章：Squeezing more performance from SortedList。这两个结构都有一个返回第i个元素的GetKey函数。

Answer 3

可能一个log堆只需要O( heap sort. N)来添加新数据，并且您可以在O(N log N)时间内随时弹出净结果。

如果你每次都需要对整个列表进行排序，那么除了一个对数之外，没有太多的其他选择，它可能是O(N^2)，尽管有很大的linked skip lists麻烦，你可以把它变成O(N insertion sort. N)。