如何有效地排序具有下一个和上一个节点引用的节点列表

本文关键字：节点 上一个 引用 列表 下一个 有效地 排序 | 更新日期: 2023-09-27 18:03:15

我在随机中有一个项目集合，每个项目都有以下数据结构:

// 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(n2)的解是可能的。然而，我希望在小于0 (n2)的时间内以正确的顺序对这些进行排序。这可能吗?

如何有效地排序具有下一个和上一个节点引用的节点列表

看着它…假设你不使用循环列表，你不能只是通过你的随机顺序数组迭代，直到你找到开始节点(一个与.Previous == null)，然后返回节点?我的意思是，链表的一个优点是你不需要在一个单独的数据结构中存储对所有节点的引用，只需要让它们彼此连接。(嗯，这取决于你使用的语言实现是否有引用计数和垃圾收集，如果有的话。)

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

根据你更新的问题，它可能是一个好主意，你实现一组临时链表。当您最初遍历列表时，您将检查每个节点的Next和Previous元素，然后将Next s和Previous es存储在Dictionary-esque对象中(我不确定什么。net对象最适合于此)作为键，链接列表节点围绕现有的Node s，引用Item s作为值。这样，您就可以在不进行任何实际排序的情况下构建链接，并且最终只需遍历临时列表，将由listnodes包装的Node赋值给要返回的新数组。

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

我认为归并排序可以工作。类似…

  merge_sort_list(list, chain_length)
  1. if chain_length > 1 then
  2.    merge_sort_list(list, chain_length/2)
  3.    middle_node = step_into_by(list, chain_length)
  4.    merge_sort_list(middle, chain_length - chain_length/2)
  5.    merge_list_halves(list, middle, chain_length)
  merge_list_halves(list, middle, chain_length)
  1. ... you get the idea

我想到了合并排序…我认为这应该适用于这里，它在O(n log n)内执行(最坏情况)。

归并排序通常是对链表排序的最佳选择在这种情况下，实现归并排序相对容易方式，它只需要Θ(1)额外的空间，和缓慢的随机访问链表的性能使得其他一些算法(如快速排序)的性能很差，而其他(如堆排序)则完全不可能。

编辑:重读你的问题后，它不再有多大意义了。基本上，您希望排序，以便项按照列表给出的顺序排列?这在线性O(n)时间内是可行的:首先你向后移动到列表中的第一个项目(通过引用)，然后向前生成每个项目。或者你的Next/Previous不是参考?

相关文章：