是否可以在不使用樹的情況下進行部分排序？

Question

背景：

所以我有幾百個元素（圖像是一個簡單的情況下），我需要不斷地重新排序因爲它們的排序值發生變化時的元素X或Y值的變化。正常（絕對）排序是不可能的，因爲許多元素彼此之間存在未定義關係（如紫色和橙色塊），只會破壞合併/快速/冒泡排序。然而，改變單個元素可能會改變許多訂購關係，如果該元素對其他許多人有優勢（比如，如果綠色塊被刪除）

我理解構建樹和做拓撲排序背後的想法，但這似乎由於單個元素的變化，所以無時無刻都在做低效率的工作。

如果以上內容仍不清楚，請查看http://shaunlebron.com/IsometricBlocks，因爲這與我正在嘗試做的非常相似。

我的問題： 我不禁想，一棵樹是沒有必要的（至少對我而言），但鏈表就可以了，因爲我的情況下，保證絕不會有一個週期。 僅僅在元素大於後的最後一個元素之後，但在第一個元素之前，它總是不足以滿足（以升序排列）？這不會有效地允許排序一個部分有序集合嗎？

是否有阻止人們剛剛跳過樹步驟，直接去到一個列表中的一些情況？我在紙上做的每一個模擬似乎都表明這會起作用。

Answer 1

簡而言之，是的，可以在不使用樹的情況下進行部分排序的排序。

如果你有你的（原始的）未排序列表「U」和（空的，目的地）排序列表「S」，你需要遍歷列表「U」並將沒有依賴者的條目移動到結束列表「S」。

如果列表「U」中沒有其他條目依賴於其他條目，則條目沒有依賴者。如果您使用{-1,0,1}來衡量相等性，那麼您將需要選擇「-1」或「1」來暗示相關性。而「0」意味着這兩個元素沒有有效的排序。