algorithm - A排序如何工作？

Question

有人可以阐明 A-sort(不是 asort())的工作原理，它使用 (a,b)-树对部分排序的序列进行排序吗？

Answer 1

算法本身非常简单 - 基本上是将所有元素插入树中，然后遍历树以按顺序读取元素。

为了对几乎已经排序的序列获得更好的性能，它使用了以下修改:

1. 树必须是 b>2a-1 的 (a,b) 树，具有 O(1) 的分摊插入重新平衡时间。
2. 树包含指向同一级别(跨整个树)节点的兄弟节点的链接

要利用 O(1) 插入时间，您只需快速找到下一个元素所属的位置，假设序列几乎已排序(因此它不会远离插入的前一个元素)。大致是这样完成的:

• 从上一个插入的元素开始
• 检查下一个元素是否不属于该节点或该节点的任何子树；如果不是，你看看 sibling (假设新元素更小，所以它将是左边的 sibling )
• 如果 sibling 的值仍然太大，则上升一级并重复
• 如果新元素属于兄弟的子树，则从那里进行正常搜索
• 如果新元素属于兄弟节点和该节点之间，则转到最左边的子节点并重复向下搜索，直到找到合适的子树

这样，您可以在 k 步中遍历树的 a^k 个元素，因此，您需要 O(log(distance( current, previous)) 时间来为新元素找到合适的位置。给定分摊的 O(1) 再平衡，你会比 O(n log n) 几乎排序序列的时间，同时保持 O(n log n) 最坏情况。