面向程序员的Python算法编程中的常见问题及算法
一些著名的问题和算法如果你的船破洞了，我只能深表同情。 因为在我解决的99个问题中只有这个问题。
—— Anonymous 1本文提到的所有问题和算法都是因为有的算法只是试图解释某种原理，而有的问题只是为了某种算法而制作的。
但是，作为索引，这里列举了学习中最重要的问题和算法。
在本文的许多记述中，n表示一个序列内的要素数等问题的规模。
在图论问题中，n表示节点的数量，m表示边的数量。
问题部分分团问题和独立集合：分团图是各对顶点之间有边相连的图结构。
我们对这个问题感兴趣的主要是在大图中如何找到那个分组图。 也就是说，分组图实际上是种子图。
独立集合是指边互不相连的图结构的点。
也就是说，寻找独立集合的过程与逆转图的各两点之间的连接关系，找到该图的分组图几乎相同。
找到k-聚类图(包含k个节点的聚类图)或找到某个图的结构中的最大聚类图是NP的课题。
(详情请参考第11章。
）
最近的点配对问题：在几何平面上给出几个点，找出其中最近的两个点。
它可以在线性对数水平的时间内，使用分治策略来解决。
(见第六章)
压缩问题与最优决策树：哈夫曼树是叶节点有权重的树结构。
权重和节点深度的乘积和越小越好。
该树结构对压缩编码的构建非常有效，权重可能是节点的已知概率分布。
哈夫曼树可以用第七章中描述的哈夫曼算法(见清单7-1 )来构建。
连通问题和强连通分量：如果无向图的各节点能找到通向其他任意节点的路径，这种图结构称为连通图。
如果基于有向图的有向图是相连的，那么这个有向图也是相连的。
连通分量是图结构中最大的连通子图。
连通成分例如可以使用DFS (参照列表5-5 )、BFS (参照列表5-9 )等扫描算法获取。
另外，在有向图中，只要各节点到其他任何节点都能找到有向路径，该图就被称为强连通图。
强连通组件( SCC )是连通图中最大的强连通子图。
可以通过Kosaraju算法(见清单5-10 )找到SCC。
凸包问题：在几何平面中，凸包是指包含所有点的最小凸多边形区域。
采用分治法可以在线性对数级时间内解决凸包问题(见第6章)。
查找最小值/最大值/中间值：通过一次扫描可以找到序列中的最小值和最大值。
通过使用三叉堆和准备线性级时间，可以在常数时间内重复提取最大值和最小值。
通过随机选择算法，还可以在线性级别时间(或预计线性级别时间)内找到序列中第k个最小的元素。
(详情请参考第6章。
）
通信量和断开问题：如果图的结构中每边都有通信量，则其配置的网络总通信量应该是多少？ 这是最大流量的问题。
与之等效的一个问题是找到一组可以最大化流量的边缘。
这是最小切断问题。
在类似的问题中存在几种不同的版本。
例如，在边上填写通行费，寻找最不花钱的路径。
或者，标记每条边的最小通信量，然后查找可行路径。
节点也可以标记通过该节点的消费或请求。
第十章讨论了这一系列问题。
图表着色问题：首先，尝试给图表结构中的点着色。 尝试为每对直接连接的节点涂上不同的颜色。 然后，为了尽量减少用于着色的颜色，尝试对颜色进行分类。
基本上，这是NP的难题。
但是，如果判断某个图表结构是否可以只用2种颜色着色，以及图表是否为二叉树的话，在线性水平的时间内进行1次扫描就可以解决这个问题。
另外，寻找分团覆盖的问题与寻找独立集团覆盖的问题相同，都与图的着色问题非常相似。
(有关图着色问题的详细信息，请参阅第11章。
）
停机问题：确定特定算法是否会因特定输入而终止。
这通常是一个无法判定(无法解决)的问题(见第7章)。
哈密顿圈/路径、TSP……和欧拉路径：在路径问题和子图问题中，确实存在一些特定问题的有效解决方法。
但是，存在可以访问所有节点的方法，这并不意味着每个节点只能访问一次。
存在这样限制的问题是，汉密尔顿循环(从某个节点出发，只访问一次各节点并返回到出发节点)、汉密尔顿路径)从某个节点出发，每次访问各节点，但不需要返回到出发节点)
无论是对有向图还是无向图来说(参照第11章)，这些问题都是NP的难题，但是寻找欧拉路径(从某个节点出发，只访问各边一次，不需要返回出发节点)可以用多项式水平的时间来解决)
此外，TSP问题仍然是NP的课题，但在特定情况下，例如想计算平面上的几何距离时，可以将因子规定在1.5以内，用其他矩阵距离解决。
但是，这并不影响许多其他类似的TSP问题是NP的费解性。
(详情请参考第11章。
）
背包问题与整数规划：背包问题是在某些限制条件下，基于某些边界值摘录某个集合的子集的问题。
在分数有限的情况下，我们有一些物品。 各自有不同的质量，每单位质量的价值也不同。 把这些物品放进背包里。
这时，我们采用的“贪婪”解决方案，就是从价值最高的东西开始，尽可能多放就可以了。
在整数背包的问题上，我们必须把一件物品全部装进去，不能只装这个物品的几分之一。
每个物品都有质量和价值，如果有限制(所谓的0-1背包问题)，每个物品都有一定的数量。
)另一个同类问题是有几个固定项目的集合，可以选择这些集合，但不能分割其中的一个集合。
)但是，如果行李数量没有限制的话，你可以随心所欲地取行李(当然也要考虑背包的容量)。
例如，子集和问题是这种情况的特例。
它显示了如何从数据集中检索子集，以便子集中的元素之和等于指定的数量。
这些问题都是NP的难题(参照第11章)，如果使用动态计划的话，可以在伪多项式顺序的时间内得到解(参照第8章)。
背包问题也可以通过贪婪算法在多项式级时间内解决(见第7章) 。
整数规划是在某种程度上一般化的背包问题(因此显然是NP难题)。
只有变量为整数的线性规划问题。
最长增加部分序列问题：在给定的序列中寻找最长的增加序列。 这个问题可以在动态规划(见第8章)线性对数级时间内解决。
匹配问题：匹配问题有很多种，其中最典型的是对象相互链接的问题。
本书讨论的问题主要有两点匹配问题、成本最小化的两点匹配问题[见第10章]、稳定婚姻问题[见第7章]。
二分法匹配问题(或最大化的二分法匹配问题)主要涉及在二分法图中寻找边的最大子集，该子集中两条边的任意两个端点不能一致。
这个问题还有别的版本。 对该图中的所有边进行加权，找到权重最大且满足此条件的子集。
稳定婚姻的问题与此略有不同。
在这个问题上，每个人都会给所有异性打分，并根据分数分配配偶。 这样，即使所有的异性都很孤独长寿，也不会不想和对方结婚。
最小生成树问题：生成树实际上是一个种子图，其子图是包含原始图的所有节点的树。
最小生成树是当边缘具有权重时，权重的总和最小的生成树。
要查找最小生成树，请使用Kruskal算法(参见清单7-4 )或Prim算法(参见清单7-5 )。
例如，由于边的数量是固定的，因此可以通过取消边的权重来找到最大生成树。
分割问题和装箱问题：分割问题是指将一个数的集合分为两部分，使两个部分集合之和相等。
另一方面，装箱问题是指将一个集合中的数放入几个“箱子”，在使各箱子内的总数不超过某个值的同时，尽量减少使用的箱子数量。
这两个问题都是NP的难题。
(见第十一章)
SAT、Circuit-SAT、k-CNF-SAT :这些都是满足性问题( SAT )的变体，是判定真值的逻辑)布尔)被要求给出表达式。
当然，前提是我们可以按照自己的意愿设定真值变量。
但是，Circuit-SAT问题通常直接应用于逻辑循环，而不是表达式。
k-CNF-SAT问题主要涉及公平交易范式中的公式。
如果k=2，后者可以在多项式级别的时间内解决。
另一方面，在k 2的情况下，这是NP的完全问题(参照第11章)。
搜索问题：这是一个非常普遍、非常重要的问题。 用某个键找到对应的值。
这本身就是像Python这样的动态语言变量的结构。
即使在当今的网络世界里，这也是一种查找几乎所有信息的方法。
对此，现在大致分为两种解决方案。 即，散列表(参照第2章)和二叉树(参照第6章)。
如果数据集中的元素具有概率分布，还可以使用动态语言创建最佳搜索树来优化查询。
数组匹配问题：比较两个数组，找到它们之间相同(或不同)的元素。
解决这些问题的一个方法是查找两个序列中最长的公共子序列，或者查找从一个序列转换到另一个序列所需的最小基本编辑数( Levenshtein distance算法)。
这两个问题是等效的。
详见第八章。
重新排序问题：在链表中插入元素的时间非常复杂(常数级别的时间)，但查找给定元素的时间非常复杂(线性级别的时间)。
数组的情况相反。 搜索时间为常数级别，插入时间为线性级别。 这是因为您必须移动元素插入位置之后的所有元素。
但在两者末端插入元素的时间非常小(见第2章相关黑匣子专栏)。
集合和顶点复盖问题：顶点复盖集是指可以复盖图中所有边的顶点的集合(每边至少有一个顶点在顶点复盖集中)。
如果将这个概念中的顶点置换为部分集合，就可以引申出集合所复盖的概念。
此问题的重点是限制或最小化顶点和子集的数量。
这两个问题都是NP的难题。
(见第十一章)
最短路径问题：该问题的具体形式是从一个节点到另一个节点的最短路径、从一个节点到所有其他节点的最短路径(可以是反向的)和从图中的每个节点到其他节点的最短路径。
其中，一对一、一对多或多对一的解决方法基本相同。
通常使用基于未加权图的BFS算法。
如果是DAG图，则采用DAG最短路径算法，如果权重为非负，则采用Dijkstra算法，一般采用bellmanFord算法。
此外，在实践中，为了加速算法(虽然不能提高最坏情况的执行时间)，也能够采用双向Dijkstra算法，即A*算法。
在问题的最后一种情况下，主要可以选择Floydwar shall算法、Johnson算法(应用于稀疏图)。
如果边的权重不是负的，则Johnson算法与按点使用Dijkstra算法相同。 后者更有效率。
有关最短路径算法的详细信息，请参见第五章和第九章。
另外值得注意的是，(一般图的)最长路径问题通常用于寻找哈密顿路径。
也就是说，这是NP的难题。
实际上，这意味着一般来说最短路径问题也很难NP。
但是，如果删除图中的负循环，我们的算法就可以在多项式水平的时间内解决问题。
重复排序问题和元素：排序是一项非常重要的操作，是许多其他算法的基础。
Python使用list.sort (方法或sorted )函数执行排序操作。 两者都使用了time排序算法的有效实现。
其他算法包括插入排序法、选择排序法和gnome排序法。 这些都是平方时间的算法。
此外还有堆积排序、合并排序和快速排序。 这些是线性对数级算法，但这是快速排序算法在平均级的表示。
关于平方运行时的排名算法，请参考第5章的相关内容。
另一方面，关于线性对数级(使用分治法)算法，可以参考第6章的相关内容。
实数集是否具有重复值还直接决定了排序时间是否好于(最坏情况下)线性对数级别。
这里需要的不仅仅是排序，还有一些简单的操作。
拓扑问题：根据规则对DAG地图中的节点进行排序，使所有边都指向同一个方向。
如果边表示依存关系的话，拓扑的顺序表示根据该依存关系为节点制作的顺序。
引用次数(见第4章)或DFS (见第5章)可以解决此问题。
遍历问题：此问题主要涉及如何在一个连通结构中访问所有对象。
此问题通常表示为图或树结构中的节点遍历。
您可能需要访问每个节点，也可能只需要访问某些节点。
后者，即关于忽视图和树结构的某一部分的策略，通常被称为修剪，多用于探索树和枝的边界策略。
详情请参照第五章。
算法和数据结构部分2-3树：平衡树结构，支持插入、删除、检索操作。
这些操作最差时所需的时间为[LGn]。
其内部节点可以有2~3个子节点。
另外，该树结构在节点分割插入的过程中需要始终保持平衡(参照第6章)。
*算法：启发式单源最短路径算法。
适合大的搜索空间。
因此，我们并不像[戴克斯特拉法]那样，基于最短距离的值来选择节点，而是使用与实际距离值加上剩余距离的推测值相等的节点的最低启发值。
该算法最坏情况下的运行时间与Dijkstra算法相同。
(见清单9-10 )
AA树：该结构是一棵多层二叉树中2-3树节点反演的结果。
该算法在最坏的情况下，插入、删除、搜索的执行时间为[LGn]。
(见清单6-6 )
bellmanFord算法：用于查找从加权图的一个节点到所有其他节点的最短路径。
其探索之路是沿着每条边走n次。
除非这是一个负循环，否则其正确答案在n-1次迭代后应该可以确认。
如果最后一次迭代仍有改善的空间，则必须将其作为负循环删除，并丢弃运行时间[lnm]的算法。
(见清单9-2 )
双源Dijkstra算法：在起点和终点同时运行Dijkstra算法，并在两个算法实例之间交叉迭代。
当它们在中间相遇时(虽然这个中间点有些地方值得讨论)，找到了最短的路径。
该算法最坏情况下的运行时间与Dijkstra算法相同。
(见清单9-8和清单9-9 )
二叉树：二叉树的每个节点都有一个键。 通常，也有对应的值。
通过这些节点的密钥，我们可以区分其子节点的密钥。
小关键点通常位于左边的子树中，而大关键点位于右边的子树中。
平均来说，由于所有节点都位于与其对数相等的深度，因此其插入、搜索操作的时间复杂度为[LGn]。
如果“如AA树那样”解除其中的平衡成本，则树结构有可能失去平衡，但能够得到线性级别的运行时间。
(见清单6-2 )
二分法与二分探索：一种源于探索树的探索方式。
它在序列化序列中，根据自己的兴趣将序列依次减半。
在减半过程中，算法通过检测序列的中间元素来确定偏左半部分还是偏右半部分。
该算法的执行时间为[LGn]。
Python程序员可以在bisect模块中找到非常高效的实现。
(见第六章)
分支定界法：这是一种常用的算法设计方法。
主要构建局部评估方案，并将其作为方案空间，通过深度优先或最优优先策略进行搜索。
在此过程中，保守评估值将作为最佳方案保留，乐观评估值将作为局部方案计算。
如果这个乐观评价值比保守评价值差，我们就不扩展这个局部方案，同时追溯算法。
该算法设计通常用于解决NP难题。
(请参见清单11-2。 那是用分支边界法解决0-1背包问题的例子。
）
宽度优先搜索( BFS )分层遍历图表结构(或树结构)，找到其(无权重)最短路径的搜索方式。
实现在FIFO队列中记录发现的节点。
算法的执行时间为(nm )。
(见清单5-9 )
桶排序法：按此算法排序的数值均匀分布在一组区间中，其中用于存储相关值的桶大小相同。
因为预计这些桶的大小是一定的，所以它们本身也可以用插入排序法之类的算法进行排序。
整个算法的执行时间为(n )。
(见第四章)
bus ackergo Wen算法：该算法寻找网络中在最低成本条件下可以达到的最大通信量，或者网络在给定通信量值下可以达到的最低成本。 Ford采用来自fulker son方法的最低成本扩展路径。
这些路径的搜索可以通过Bellman-Ford算法或Dijkstra算法(经过了一些加权处理)来解决。
一般来说，算法的执行时间取决于最大流量值，是伪多项式级别的时间。
如果最大流量值为k，假设采用Dijkstra算法，其运行时间应该为o(kmlgn )。
(见清单10-5 )
Christofides算法：主要针对度量型TSP问题的近似算法。 近似比绑定到约1.5。 寻找某最小生成树结构和该树的奇数节点的最小一致2，在对应的图表结构中构筑有效的短循环。
(见第十一章)
计数排序算法(该算法可以完成(n )个时间间隔内的小整数区间(最大)可以有n个连续的值)的排序。
其结构是对出现的数字进行计数，根据其累计值直接配置结果的数字并持续更新。
(见第四章)
DAG的最短路径：寻找从某个DAG内的某个节点到其他所有节点的最短路径。
其工作方式是先对节点进行拓扑排序，然后从左到右松弛每个节点的所有有向边。 或者，也可以将其更改为所有有向边。
如果没有循环，该算法也可用于查找最长路径。
运转时间为(nm )。
(见清单8-4 )
深度优先搜索( DFS )是一种不断挖掘图结构或树结构的遍历方法。
实现在LIFO队列中记录发现的节点。
由于可以记录搜索和完成时间，DFS还可以用作拓扑排序、Kosaraju算法等其他算法的子程序。
算法的执行时间为(nm )。
(见清单5-4、清单5-5和清单5-6 )
戴克斯特拉方法：可用于找到从加权图中的一个节点到所有其他节点的最短路径。 但是，前提是图形中没有具有负值的边。
遍历图表时，继续在“首选队列”( heap )中选择以下节点：
优先级基于节点当前距离的评估，这些评估的更新基于在当前访问的节点上找到的短路径。
算法的执行时间为((mn ) lg n )。
但是，如果这是连通图，时间复杂度可以简化到(mlgn )。
双向队列： FIFO队列通常使用链表(或数组链表)实现，因此插入和提取任何段的对象都可以在一段时间内完成。
Python程序员可以在collections.deque类中获得非常高效的实现。
(请参考第5章中相关的黑匣子专栏话题。
）
动态数组、矢量：这是使数组具有额外容量的想法，有助于提高添加元素的操作的效率。
当满足这个结构时，可以通过某个常数因子扩展到更大的数组。
因此，在平均水平上，可以在一定时间内完成添加操作。
(见第二章)
edmondsKarp算法：使用BFS遍历的Floydwar shall方法的实例。
该算法可在(nm2 )时间内找到相关网络的最低成本流。
(见清单10-4 )
Floydwar shall方法：此方法用于查找从图中的每个节点到所有其他节点的最短路径。
该算法在第k次迭代中，沿道路只能通过前k个中间节点。
从第k-1个节点的延伸取决于能否通过最短路径检查，以检查当前从k节点到第一个k-1个节点的路径是否比直接通向这些节点的路径短。
这意味着k节点是否可用于最短路径。
)算法的执行时间为(n3 )。
(见清单9-6 )
Fordfulker son方法：解决最大问题的常见解决方案。
该方法通过图的重复扫描来找到所谓的放大路径。 这是根据通信量而增加(扩大)的路径。
如果每个边都有额外的容量，并且只要通过它们就会发生通信，则通信量会根据通过或回滚的边的数量(取消访问)而增加。
因此，我们的扫描既包括向边缘前进，也包括向边缘后退，取决于它们共同产生的流量。
具体算法的执行时间取决于我们采用的遍历策略。
(见清单10-4 )
galeShapley算法：该算法致力于对男女群体进行优先级划分，并从中找到稳定的婚姻组合。
没有结婚的男人，都会被女性推荐为最好的结婚对象，所有的女性都可以从现在的追求者中选择。 其中可能有未婚夫。
算法的实现应该在平方级的时间内完成这些事情。
(请参阅第7章“求婚者与稳定婚姻”专栏的内容。
）
侏儒症排序法：一种简单的平方级排序算法。
实际上可能不会使用此算法。
(见清单3-1 )
哈希操作和哈希表：哈希与搜索树一样，是使用键值查找相应值的操作。
相关元素项通常存储在依赖于特定(伪随机或规则)计算的散列键值的数组中。
只要有散列函数和足够的数组空间，哈希表的插入、删除和查询操作就可以在(1小时内完成。
(见第二章)
堆和堆排序：堆是高效的优先级队列。
某些线性级别预处理可以使用最小/最大堆在常量级别的时间内找到结构中的最小/最大元素，并在对数级别的时间内完成元素提取或替换。
另外，元素的添加也可以在对数水平的时间内进行。
在概念上，堆实际上是完整的二叉树结构，树中的每个节点小于(或大于)其子节点。
如果该结构被修改，则修复其属性是[LGn]时间的操作。
但实际上，堆通常是通过数组实现的。 节点的概念通过数组元素的某种组织来表示。
相比之下，Python程序员可以在heapq模块中找到非常高效的实现。
Heapsort的运行过程与选择排序法非常相似，但由于排序的是堆结构，该算法的n次最大元素搜索总运行时间为[nLGn]。
(请参考第6章的黑匣子列“堆结构和头，头”。
）
哈夫曼算法：该算法用于构造哈夫曼树，以构造最佳前缀码。
在初期，算法将字母字符等各个元素组成一个节点的树结构。 此时，权重与出现频率相同。
然后，在每次迭代中，选择权重最轻的两个树，合并为一个新的树结构。
这棵树的权重等于前面两棵树的权重之和。
这都可以在线性对数级别的时间内完成。 或者，如果出现频率已完成预排序，则实际上可以在线性级别的时间内进行。
(见清单7-1 )
插入排序法：一种简单的平方运行时排序算法。
其工作方式是在数组中的已排序段落中重复插入下一个未排序的元素。
对于小型数据集，这可能比合并排序或快速排序方法更好或更理想。
(但是，在Python中，必须尽可能地调用list.sort (或sorted ) )。
(见清单4-3 )。
插值搜索法：该算法与普通的二分搜索法非常相似，但用于推测当前位置的是内部端点之间的内部插值，而不是简单地寻找中间要素。
该算法最坏情况下的执行时间依然为[LGn]，但在平均水平上，面对分布均匀的数据时的执行时间为[LGLGn]。
(请参阅第6章“如果您感兴趣……”一节所述内容。
）
迭代DFS :此算法重复DFS，但遍历多远有一定限制。
在某些扇出结构中，算法的执行时间与DFS或BFS大致相同((nm ) )。
重要的是，在发挥BFS的优势(在最短路径的探索和大型固有状态空间的探索上很出色)的同时，具有像DFS那样占有内存少的特点。
(见清单5-8 )
Johnson算法：该算法致力于寻找图中每个节点到所有其他节点的最短路径，其基本工作原理是基于每个节点运行Dijkstra算法。
但是，该算法在这中间使用了技巧，以便能够处理负权重的边缘。
首先，在到达布线图中所有节点的新起点处运行Bellman-Ford算法，然后使用生成的距离值更改布线图中每条边的权重。
修改后，所有边的权重均为非负值，但原始图的最短路径为修改图的最短路径。
算法的执行时间为(mnlgn )。
(见清单9-4 )
Kosaraju算法：该算法致力于通过DFS寻找强连通分量。
首先，节点必须根据它们的完成时间来确定顺序。
然后反转这些边，单独运行DFS，并按第一个顺序选择起点。
算法的执行时间为(nm )。
(见清单5-11 )
Kruskal算法：该算法致力于通过重复添加不引起循环的最小剩余来寻找最小的生成树。
由于其循环检查可以非常高效地执行(当然，这需要一点聪明)，因此算法的执行时间取决于边的顺序。
总体上，大致为(mlgn )。
(见清单7-4 )
链表：代替数组的序列表示结构。
如果在链表中找到元素，则修改操作的成本较低(只需要常数级别的时间)，但搜索本身是线性级别的操作。
链表的实现就像一条路径，每个节点指向下一个节点。 另外，请注意，Python的list类型是在数组中实现的，不是链表。
(见第二章)
合并法：典型的分布式算法。
排序时总是将序列从中间分开，继续递归其中的一半，最后合并线性时间内排序的一半。
算法的总执行时间必须为(nLGn )。
(见清单6-5 )
Ore算法：人们通过标记通道的入口和出口来穿越实体迷宫的算法。
在许多情况下，它类似于基于深度迭代的DFS或BFS。
(见第五章) )。
Prim算法：该算法致力于通过重复添加与树最近的节点，使其成长为最小生成树。
其核心部分与Dijkstra算法相似，是遍历算法和优先级队列相结合的产物。
(见清单7-5 )
基数排序法：该算法从最低有效位开始，以(元素的)位为单位对数字列)或其他类型的列进行排序。
只要数字数量是固定的，并且数字可以按线性时间排序，算法的总执行时间就必须处于线性级别。
该排序算法的侧重点基于数字稳定性。
(见第四章)
随机选择法：该算法致力于寻找中间数或通常情况下有第k位次的个数(第k小要素)。
其结构类似于“半快速排序法”。
它可以随机或任意选择分割点的要素，将剩下的要素分割为左(更小的要素)或右(比其左)大的要素)。
然后在各个部分继续检索。 整个过程或多或少都与二叉树搜索有点相似。
虽然不能保证完美的等分，但预期的运行时间仍然是线性水平。
(见清单6-3 )
选择法：虽然相当不现实，但该算法确实保证在线性级时间内随机选择兄弟节点。
其机制是首先将目标序列分为五组，然后用插入排序法找到各自的中间值，然后用选择法递归找到这五个中间值中的中间值，以其中间值的中间值为分割点对要素进行分割。
现在，您可以选择合适的一半元素。
也就是说，与随机选择非常相似的——不同，它保证了分割点两侧有一定的比例关系，避免了完全的不平衡。
虽然这不是我们实践的真正会的算法，但了解它仍然具有重要意义。
(见第六章)
选择排序方法：一种简单的平方级排序算法。
这与插入排序的方式很相似，但这次不是在已排序的节中插入以下元素，而是在未排序的节中找到并选择最大的元素，与最后一个未排序的元素交换位置。
(见清单4-4 )
Tim排序法：这是一种非常棒的基于合并排序法的就地排序算法。
除了条件已明确声明的未处理特殊情况外，还可以处理包含顺序相反的序列段的已排序序列。
因此，在某些真实世界序列中，排序速度可能比正常情况下快。
这在list.sort (和sorted )的实现中也非常快，所以需要使用它们。
(请参阅第6章黑匣子专栏“Tim排序法”的相关内容。
）
基于引用计数的拓扑排序：该算法用于对DAG中的节点进行排序，使所有边均为从左到右的形状。
整个过程是通过计数每个节点的输入边来完成的。
输入边数为0的节点将保存在队列中。 与顺序无关，可以只是一个收藏。
这些节点将从队列中取出，并按拓扑排序顺序排列。
通过这种方式，我们减少了对相关节点边缘的计数。
它们减少到0后，就可以列入列了。
(见第四章)
基于DFS的拓扑排序法：按DAG拓扑排序的另一种算法。
该算法思路简单，运行DFS，完成时翻转节点顺序。
如果希望更轻松地获取线性级别的执行时间，也可以在DFS过程中，在每个节点完成遍历时按结果顺序添加。
(见清单5-7 )
Tremaux算法：与Ore算法类似，是一种旨在帮助人们步行穿过迷宫的算法。
在该算法的运行中，人们使用的跟踪模式实际上与DFS基本相同。
(见第五章) )。
绕树两圈的算法：一种公制TSP问题的近似算法，可实现成本高达最佳解决方案两倍的解决。
首先，构建成本小于最佳方案的最小生成树，然后“绕过”该树，并快捷方式避免重复访问同一条边。
由于采用了公制，所以可以将运营成本降低到比每个边缘访问两次的成本更低。
关于最后的遍历，用现成的DFS实现就可以了。
(见清单11-1 )
