排序和拓扑排序有什么区别？
排序和拓扑排序有什么区别？
它们是相同还是不同的东西？
What is the difference between sorting and topological-sorting?
Are they same or different thing?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在抽象层面上，它们是相互联系的：正如 Saeed 和 Stefan 所说，这是全序和偏序之间的区别。这是一个非常简洁的描述，但有时在您学习时没有帮助。
全序意味着，在没有重复的情况下，当您对某些内容进行排序时，您将得到一个唯一的正确答案。如果你按升序对 3、6、2 进行排序，你最好得到一个答案：2、3、6。
部分顺序稍微宽松一些。典型的例子是你穿衣服的顺序：你可以穿短裤，然后穿裤子，然后穿袜子，最后穿鞋子。这是有效的订单。或者你可以做短裤、袜子、裤子、鞋子。但直观上来说，你不能做短裤、裤子、鞋子、袜子。先穿鞋再穿袜子是没有意义的。
为了形式化该着装示例，您通常会显示一个依赖图，其中操作（“穿鞋”）作为节点，并有向弧显示哪个节点必须先于其他节点。拓扑排序是对图中所有节点的排序，类似于尊重弧的排序。这意味着，如果从袜子到鞋子有一条弧线，那么按顺序袜子最好位于鞋子之前。
同样，在抽象层面上，它们是相互联系的。但它们绝对不是同一件事。
At an abstract level they are connected: As Saeed and Stefan say, it's the difference between a total order and a partial order. That is a fantastically concise description, but sometimes not helpful when you're learning.
A total order means that, in the absence of repeats, when you sort something, you're going to get one unique proper answer. If you sort 3, 6, 2 in ascending order, you had better get one answer: 2, 3, 6.
A partial order is a little looser. The canonical example is the order in which you put your clothes on: You could put your shorts, then your pants, then your socks, then your shoes. That's a valid order. Or you could do shorts, socks, pants, shoes. But intuitively, you can't do shorts, pants, shoes, socks. It doesn't make sense to put the socks on after the shoes.
To formalize that dressing example, you usually show a dependency graph with actions ("put on shoes") as nodes, and directed arcs showing what node must precede what other nodes. A topological sort is an ordering of all nodes in a graph like that which respects the arcs. Meaning, if there's an arc from socks to shoes, then socks better be before shoes in the order.
So again, at an abstract level, they're connected. But they are absolutely NOT the same thing.
拓扑排序通常是指找到符合某些偏序的全序，例如有向无环图中的可达关系。
Topological sort usually refers to finding a total order that complies with some partial order, for example the reachability relation in a directed acyclic graph.
在拓扑排序中，我们处理部分有序集，但在正常排序中，我们处理总有序集。
在拓扑排序中，集合的一对元素之间可能没有任何关系，就像在有向图中一样，某些节点之间没有任何关系。在正常排序中，集合中的所有元素对都具有关系。例如，在数字集中，所有对之间都有关系 <,>,=，因此它是全序的。
In the topological sort, we work on a partially ordered set but in normal sorting, we work on a total ordered set.
In a topological sort maybe there isn't any relation between a pair of elements of the set, like in the directed graphs, between some nodes there isn't any relation. In normal sorting, all pairs of elements of the set have a relation. For instance, in the set of numbers we have the relation <,>,= between all pairs, so it is total ordered.
如果总顺序可用，则每个对象都可以与每个对象进行比较。在这种情况下，您可以对 wrt 进行排序。那个订单。例子是整数。 > （或 <，或 <=，...）或字符串。字典顺序。如果你有总订单排序是可能的。
如果只有部分顺序可用，则并非每个对象都可以与其他每个对象进行比较。仅某些对象之间的关系可用。一个例子是编译单元之间的依赖关系。拓扑排序是找到对象的排序以便尊重部分顺序的任务（例如，通过编译依赖于这些单元之后的某些其他单元的单元）。这里有几种可能的解决方案（即顺序）： 如果A依赖于B并且存在一些其他单元C，则可能的编译顺序是B，A，C和C，A，B（A在B之前编译的每个顺序）。
If a total order is available every object can be compared with every object. In this case you can sort wrt. that order. Examples are the integers wrt. > (or <, or <=, ...) or string wrt. the lexicographical ordering. If you have a total order sorting is possible.
If only a partial order is available, not every object can be compared with every other object. Only a relation between certain objects is available. An example are dependencies between compilation units. Topological sorting is the task to find an ordering of the objects such that the partial order is respected (e.g. by compiling units which depend on some other unit after these units). Here several solutions (i.e. orderings) are possible: If A depends on B and there is some other unit C, possible compilation sequences are B,A,C and C,A,B (every sequence where A is compiled before B).