最好的连续排序算法？

Question

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

最好的意思是数据计数中最小的Big-O,数据计数中的Small-O(最坏情况),以及所需空间中的最小Small-O,如果可能的话,按顺序排列.

设置的大小确实可变,从少量(30)到大量数据(+ 10M).

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的服务器中检索到.