对部分排序列表进行排序的最佳方法是什么？
最好用一个小例子来说明。
给定关系，
A < B < C
A < P < Q
正确的输出将是
ABCPQ or APQBC or APBCQ ... etc.
换句话说，给定关系成立的任何排序都是有效的。
我对最容易实现的解决方案最感兴趣，但速度和时间上的最佳 O(n) 也很有趣。
Probably best illustrated with a small example.
Given the relations
A < B < C
A < P < Q
Correct outputs would be
ABCPQ or APQBC or APBCQ ... etc.
In other words, any ordering is valid in which the given relationships hold.
I am most interested in the solution that is easiest to implement, but the best O(n) in speed and time is interesting as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这称为拓扑排序。
标准算法是输出一个最小元素，然后将其删除并重复直到完成。
This is called topological sorting.
The standard algorithm is to output a minimal element, then remove it and repeat until done.
做几种。 首先根据第一条规则排序，然后根据第二条规则排序，依此类推。 应该有效，除非你的规则包含矛盾。 当然很容易实施。
Do several sorts. First sort according to the first rule, then according to the second one and so on. Should work, unless your rules contain contradictions. sure easy enough to implement.
您可以使用手头的序列在 C++ 中重复调用 make_heap、pop_heap。
You could repeatedly call make_heap, pop_heap in C++ with the sequence at hand.