列表、集、图、树和图的排序算法

Question

大多数排序算法(插入排序、气泡排序、快速排序、合并排序等)都用list解释过。我们不是有地图，图表，树的具体排序算法吗？

Answer 1

这是可能的，但不常见。

如果您想要一棵排序的树，通常按排序顺序构建它。在树中重新排列节点/分支是相当常见的。如果您正在构建二进制搜索树，则可能会重新排列节点以保持其平衡。如果在编译器中使用抽象语法树，则可能会重新排列节点以优化计算。

映射是一种更抽象的结构，可以用二进制搜索树、跳过列表、B树、哈希表等来实现。

图基本上是一棵树的推广。当然，对图应用某些类型的排序是可能的(例如，图上的拓扑排序是非常例行的)。通常，如果数据有自己的结构，则通常使用图，并且将其简化为有序序列将丢失图形中的大量数据。

例如，图形的一种典型用法可能是将火车站表示为节点，而将这些站点之间的连接表示为图形中的弧。然后你可以通过这些铁路连接从一个城市走到另一个城市。

从图表(例如城市名称)中提取数据子集，并将数据排序为一个序列可能是有意义的，例如，按出发时间排序，从某一特定站点获取一份离开名单，并列出每一站的目的地。您还可能希望生成(主要)目的地的排序列表，以及每个目的地的起飞时间。

这实际上是提取数据，然后对提取的数据进行排序，而不是对图形本身进行排序。图的全部原因(或者说是大部分原因)首先是作为一个图构建的，因为它包含的数据不会以一个特定的顺序很容易地简化为一个列表。