algorithm - 最好的连续排序算法？

Question

我有一组 double 据，我需要始终对它们的列表进行排序。在添加数据时对数据进行排序的最佳算法是什么？

我的意思是，最好的情况下，Big-O 的数据计数最少，Small-O 的数据计数(最坏情况)，所需空间的 Small-O 最少，如果可能的话，按此顺序。

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

Answer 1

构建一个像 red-black tree 这样的自平衡二叉树或 AVL tree将允许 Θ(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's servers 检索到它.