排序部分排序列表的最佳方法是什麼？

Question

可能最好的例子是一個小例子。
鑑於關係

A < B < C 
A < P < Q 

正確的輸出將

ABCPQ or APQBC or APBCQ ... etc. 

換句話說，任何排序是有效的在給定的關係成立。

我對最容易實現的解決方案最感興趣，但速度和時間上的最佳O（n）也很有趣。

Answer 1

這叫做topological sorting。

標準算法是輸出一個最小元素，然後刪除它並重復，直到完成。

Answer 2

做幾種。首先按照第一條規則排序，然後按照第二條排序等。應該工作，除非你的規則包含矛盾。很容易實施。

Answer 3

您可以在C++中重複調用make_heap，pop_heap，並使用手頭的序列。