c# - 如何使用下一个和上一个节点引用有效地对节点列表进行排序？

Question

我有一组随机的项目，每个项目都具有以下数据结构:

// NOTE: Was "Vertex" in the comments...
public class Item
{
    public string Data { get; set; }
}

public class Node
{
    public Item Next { get; set; }
    public Item Previous { get; set; }
}

例子:

var a = new Item();
var b = new Item();
var c = new Item();
var d = new Item();

var nodeA = new Node() { Previous = null };
var nodeB = new Node() { Previous = a };
nodeA.Next = b;
var nodeC = new Node() { Previous = b };
nodeB.Next = c;
var nodeD = new Node() { Previous = c, Next = null };
nodeC.Next = d;

// This would be input to the sort method (completely random order).
var items = new []{ nodeC, nodeA, nodeD, nodeB };

// Execute sort

// Result: nodeA, nodeB, nodeC, nodeD.

显然 O(n²) 的解决方案是可能的。但是，我想以小于 O(n²) 的正确顺序对它们进行排序。这可能吗？

Answer 1

看看它...假设您没有使用循环列表，难道您不能只遍历随机顺序数组直到找到起始节点(带有 .Previous == null 的节点)然后返回该节点吗？我的意思是，链表的优点之一是您不必将对所有节点的引用存储在单独的数据结构中，只需将它们彼此连接即可。 (好吧，取决于您使用的语言实现如何进行引用计数和垃圾收集，如果它确实进行的话。)

但基本上，除非您在操作后立即需要访问距起始节点一定距离的元素，否则我建议在遇到时立即返回起始节点，然后懒惰地分配给适当大小的数组当您使用每个连续的节点时。事实上，即使你创建一个新数组并赋值给它，最坏的情况不仍然只是 O(n)，n 是节点数吗？ O(n) 找到起始节点，然后另一个 O(n) n 遍历列表，将每个节点分配给与输入数组大小相同的数组中的相应索引。

---

根据您更新的问题，实现一组临时链表对您来说可能是个好主意。当您最初遍历列表时，您会检查 Next和 Previous每个节点的元素，然后存储 Next s 和 Previous es 在字典式对象中(我不确定哪个 .NET 对象最适合那个)作为键，链表节点环绕现有的 Node s 引用 Item这是值(value)观。这样你就可以在没有任何实际排序的情况下建立链接，最终只会遍历你的临时列表，分配 Node s 由列表节点包装到一个新数组以返回。

我相信，这应该比 O(n^2) 更好，因为字典访问通常平均为常数时间(尽管最坏情况下的渐近行为仍然是 O(n))。