排序和拓扑排序有什么区别？

Question

排序和拓扑排序有什么区别？

它们是相同的还是不同的东西？

- Samselvaprabu

---

https://en.wikipedia.org/wiki/Sorting_algorithm | https://en.wikipedia.org/wiki/Topological_sorting - Savino Sguera

Answer 1

在抽象层面上，它们是相互关联的：正如Saeed和Stefan所说，这是完全排序和部分排序之间的区别。这是一个非常简洁的描述，但有时候在学习时并不是很有帮助。

完全排序意味着，在没有重复项的情况下，当您对某些内容进行排序时，您将得到一个唯一的正确答案。如果您按升序对3、6、2进行排序，则应该得到一个答案：2、3、6。

部分排序则要宽松一些。典型的例子是穿衣服的顺序：您可以先穿短裤，然后穿长裤，再穿袜子，最后穿鞋子。这是一个有效的顺序。或者您可以先穿短裤、袜子、长裤、鞋子。但直觉上，您不能先穿短裤、长裤、鞋子、袜子。在穿鞋子后再穿袜子是不合理的。

为了形式化这个穿衣服的例子，通常会显示一个依赖图，其中动作（“穿鞋子”）作为节点，并显示指向其他节点的有向弧。拓扑排序是对这样一个图中所有节点的排序，它遵守弧线。也就是说，如果从袜子到鞋子有一条弧线，那么在顺序中袜子必须在鞋子之前。

因此，在抽象层面上，它们是相互关联的。但它们绝对不是同一件事情。

- Novak

---

如果你是Britney，你可以把你的字符串放在你的Short后面...（我已经退出了） - Kheldar

@Novak：非常简单易懂的例子。我想我永远不会忘记这个拓扑排序了。你是大学教授吗？如果是，你的学生真的很幸运。 - Samselvaprabu

你非常友好，但我只是一个博士候选人。我发现必须先在自己的脑海中理解低级直觉，这有助于我记忆和理解数学描述。对我来说，数学是抽象的力量所在，而图片和故事则是直觉所在。 - Novak

那个衣服的例子是解释部分有序集的绝佳方式 :) 当尝试理解CRDTs时，它们非常有用。 - Siddhartha

Answer 2

拓扑排序一般是指寻找符合某些偏序关系的全序，例如有向无环图中的可达性关系。

- Irit Katriel

Answer 3

在拓扑排序中，我们处理的是一个部分有序集合，但在普通排序中，我们处理的是一个全序集合。

在拓扑排序中，也许集合中某对元素之间没有任何关系，就像在有向图中，某些节点之间没有关系。而在普通排序中，集合中所有元素对之间都有关系。例如，在数字集合中，我们有<,>,=这些关系适用于所有元素对，因此它是全序的。

- Saeed Amiri

Answer 4

如果存在全序，那么每个对象都可以与其他对象进行比较。在这种情况下，您可以按照该顺序进行排序。例如，整数可以按照“>”、“<”、“<=”等进行排序，字符串可以按照词典顺序进行排序。如果有完全的顺序，则可以进行排序。

如果只有部分顺序可用，则不能将每个对象与其他对象进行比较。只能比较某些对象之间的关系。编译单元之间的依赖关系就是一个例子。拓扑排序是找到一组对象的顺序，以便遵守部分顺序（例如，编译依赖于其他单元的单元后面的单元）。在这里，可能有多个解决方案（即顺序）：如果A依赖于B，并且存在另一个单元C，则可能的编译顺序为B、A、C 和 C、A、B（其中A在B之前编译的每个顺序）。

- Stefan