部分算法图解

转自 https://mp.weixin.qq.com/s?__biz=MjM5MDE0Mjc4MA==&mid=2651006795&idx=1&sn=256e244ff8ab67795af6d896d19c06cb&chksm=bdbedf188ac9560e5949170d04cdff45d4835f2e5f0b2894671827777e1ba783c6bace21305e&mpshare=1&scene=1&srcid=04121I3dNgVIXMwSKMq3ceKI#rd

IDEA 是由 SándorP. Fekete、Sebastian Morr 和 Sebastian Stiller 共同推出的图解算法系列。 它们最初是为 Sándor 在德国不伦瑞克工业大学开设的算法和数据结构讲座而设计的，作者希望它们能够有更广的用途，因此在网上发布了这个项目，希望能够帮助到教师、学生和有好奇心的人们。算法将会不断更新，可以访问页面了解更多信息：

https://idea-instructions.com/。

这些图片使用 Inkscape 绘制，可以使用任意一款向量图编辑软件来编辑它们。每个算法下面都有相应的图片下载地址。

快速排序

快速排序是一种“分而治之”的排序算法，通过随机选择“分区点”来避免出现最坏的情况。

image

1. 随机选择“分区点”。

2. 按照“分区点”的高度划条线。

3. 高出“分局点”的元素需要向右移动。

4. 低于“分区点”的元素需要向左移动。

5. 移动元素。

6. 重复上述的步骤分别对位于“分区点”两边的元素进行排序。

下载地址：https://idea-instructions.com/quick-sort/

Bogo 排序

Bogo 排序也被称为“愚蠢的排序”，是一种非常简单但低效的排序算法，就是不断打乱元素的顺序，直到达到有序为止。

image

1. 查看元素是否有序。

2. 元素无序，那么就打乱顺序。

3. 再次检查元素是否有序。

4. 如果有序，排序成功，否则继续重复上述步骤。

下载地址：https://idea-instructions.com/bogo-sort/

二分查找

二分查找是一种快速从一个有序数组中找到某个元素位置的查找算法。这有点类似于猜数字游戏，通过不断问“目标数字是大于还是小于某个数”这样的问题，最终猜出目标数字。

image

1. 限定元素区间。

2. 待查找元素在区间的某个位置吗？

3. 不在。

4. 那么看看待查找元素是不是在当前位置的左边或者右边。

下载地址：https://idea-instructions.com/binary-search/

归并排序

归并排序也是一种“分而治之”的递归排序算法。

image

1. 把元素分成两部分，对每一个部分采用递归的归并排序。

2. 比较已经排好序的元素。

3. 合并已经排好序的元素。

4. 排序完毕。

下载地址：https://idea-instructions.com/merge-sort/

平衡二叉树

平衡二叉树是自平衡的二叉树变种，可以保证快速的查找、插入和删除操作。

image image

以图中的平衡二叉树为例：

• 左子节点比父节点小，而父节点比右子节点小。如果根节点左右子树的高度差超过 1，就变得不平衡。

• 想知道树中是否包含了元素 11？11 比 10 大，那么就查找 10 的右子节点 12。11 比 12 小，所以就查找 12 的左子节点，12 的左子节点刚好是要查找的 11。同样的，树中是否包含了元素 8？8 比 10 小，那么就查找 10 的左子节点 6。8 比 6 大，那么就查找 6 的右子节点。6 的右子节点不存在，说明树中不存在元素 8。

• 如何找到树中最小的元素？从根节点开始，一直顺着左子节点，找到最后一个叶子节点就是树中最小的元素。

• 如何找到 10 的下一个元素？如果根节点刚好是 10，那么就从 10 的右子树中找到最小的那个元素。如果根节点不是 10，那么先找到 10，如果 10 没有右子节点，那么就一直往父节点找，直到找到比 10 大的元素为止。

• 在树种加入 17 或删除 10，破坏了树的平衡，这个时候需要通过旋转恢复树的平衡。

下载地址：https://idea-instructions.com/avl-tree/

图遍历

图遍历算法会遍历图中所有可达的顶点，可以通过辅助数据结构来实现各种遍历，比如使用无序集合实现随机遍历，使用堆栈实现深度优先遍历，使用队列实现广度优先遍历。

image

• 随机查找：选定一个顶点，把它放入一个无序集合中。从集合中取出一个顶点，访问该顶点，把该顶点的相邻顶点放入集合中，并把该顶点移出集合。重复这一过程，直到集合中的元素全部被遍历完毕。

• 深度优先遍历：选定一个顶点压入栈中，把该顶点其中的一个相邻顶点也压入栈中。访问栈顶的顶点，如果该顶点没有其他相邻的顶点，就出栈。如果有其他相邻顶点，就把其中的一个相邻顶点压入栈中。重复这一过程，直到栈中的元素全部被遍历完毕。

• 广度优先遍历：选定一个顶点，把该顶点的相邻顶点放进队列尾部。访问队列头部的顶点，把该顶点移出队列，如果该顶点有相邻顶点，就把相邻顶点放进队列尾部。重复这一过程，直到队列中的元素全部遍历完毕。

下载地址：https://idea-instructions.com/graph-scan/

一笔画

一笔画是一种 Fleury 算法，旨在优雅地找出图中的欧拉（Eulerian）路径。欧拉路径是图中的一条路径，刚好经过每条边，并且每条边只被访问一次。

image

1. 顶点度数表示该顶点有几条边。

2. 如果图中有且仅有两个顶点的度数为奇数，其他为偶数，或者不存在奇数度数的顶点，则存在欧拉路径。

3. 选定一个顶点开始画路径。

4. 如果存在两个以上的桥，那么可以走桥。如果只剩下一个桥，就不能走桥，除非只剩下桥可以走。

5. 如果还有没有走过的边，重复步骤 4。

6. 成功画出欧拉路径。

下载地址：https://idea-instructions.com/euler-path/

原文链接：https://idea-instructions.com/