是否可以在不使用树的情况下进行部分排序？

Question

背景：

所以我有几百个元素（图像是一个简单的情况下），我需要不断地重新排序因为它们的排序值发生变化时的元素X或Y值的变化。正常（绝对）排序是不可能的，因为许多元素彼此之间存在未定义关系（如紫色和橙色块），只会破坏合并/快速/冒泡排序。然而，改变单个元素可能会改变许多订购关系，如果该元素对其他许多人有优势（比如，如果绿色块被删除）

我理解构建树和做拓扑排序背后的想法，但这似乎由于单个元素的变化，所以无时无刻都在做低效率的工作。

如果以上内容仍不清楚，请查看http://shaunlebron.com/IsometricBlocks，因为这与我正在尝试做的非常相似。

我的问题： 我不禁想，一棵树是没有必要的（至少对我而言），但链表就可以了，因为我的情况下，保证绝不会有一个周期。 仅仅在元素大于后的最后一个元素之后，但在第一个元素之前，它总是不足以满足（以升序排列）？这不会有效地允许排序一个部分有序集合吗？

是否有阻止人们刚刚跳过树步骤，直接去到一个列表中的一些情况？我在纸上做的每一个模拟似乎都表明这会起作用。

Answer 1

简而言之，是的，可以在不使用树的情况下进行部分排序的排序。

如果你有你的（原始的）未排序列表“U”和（空的，目的地）排序列表“S”，你需要遍历列表“U”并将没有依赖者的条目移动到结束列表“S”。

如果列表“U”中没有其他条目依赖于其他条目，则条目没有依赖者。如果您使用{-1,0,1}来衡量相等性，那么您将需要选择“-1”或“1”来暗示相关性。而“0”意味着这两个元素没有有效的排序。