A-sort如何工作？

Question

難道有人請澄清A-sort（不是asort（））的運行方式，它使用（a，b）樹來對部分排序的序列進行排序？

Answer 1

算法本身非常簡單 - 基本上你可以在樹中插入所有元素，然後遍歷樹來按順序讀取元素。

要獲得幾乎已經排序序列更好的性能，它採用了以下修改：

1. 樹必須與的（A，B）樹，有O(1)攤銷插入再平衡時間。
2. 在樹中對同一級別的節點的兄弟姐妹鏈接（在整個樹）

要利用O(1)插入的時候，你就必須迅速找到下一個元素所屬的地方，假設序列幾乎是排序的（所以它不會遠離前一個元素插入的位置）。這是如下大致完成：

• 你開始在插入
• 你檢查下一個元素不屬於此節點或該節點的任何樹的一個元素;如果沒有，你看兄弟姐妹（假設新元素是小，因此這將是左兄弟）
• 如果兄弟姐妹的值仍然過大，你去了一個水平，如果新的元素重複
• 屬於兄弟姐妹的子樹，你從那裏做一個正常的搜索
• 如果新的元素屬於兄弟姐妹和這個節點之間，你去到最左邊的孩子並重復搜索直到找到適當的子樹

這樣，你可以遍歷a^k這棵樹的元素在k的步驟，因此，它會花費你可以在O(log(distance(current, previous))時間找到適合新元素的位置。給定攤銷O(1)重新平衡，你幾乎排序序列的時間比O(n log n)好，同時保持O(n log n)最壞的情況。