乐趣区

关于javascript:趣味算法图解

jiezi

IDEA 是由 SándorP. Fekete、Sebastian Morr 和 Sebastian Stiller 独特推出的图解算法系列。它们最后是为 Sándor 在德国不伦瑞克工业大学开设的算法和数据结构讲座而设计的，作者心愿它们可能有更广的用处，因而在网上公布了这个我的项目，心愿可能帮忙到老师、学生和有好奇心的人们。算法将会不断更新，能够拜访页面理解更多信息：

https://idea-instructions.com/

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

疾速排序

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

  1. 随机抉择“分区点”。
  2. 依照“分区点”的高度划条线。
  3. 高出“分局点”的元素须要向右挪动。
  4. 低于“分区点”的元素须要向左挪动。
  5. 挪动元素。
  6. 反复上述的步骤别离对位于“分区点”两边的元素进行排序。

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

Bogo 排序

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

  1. 查看元素是否有序。
  2. 元素无序，那么就打乱程序。
  3. 再次查看元素是否有序。
  4. 如果有序，排序胜利，否则持续反复上述步骤。

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

二分查找

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

  1. 限定元素区间。
  2. 待查找元素在区间的某个地位吗？
  3. 不在。
  4. 那么看看待查找元素是不是在以后地位的右边或者左边。

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

归并排序

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

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

  1. 比拟曾经排好序的元素。
  2. 合并曾经排好序的元素。
  3. 排序结束。

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

均衡二叉树

均衡二叉树是自均衡的二叉树变种，能够保障疾速的查找、插入和删除操作。

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

  • 左子节点比父节点小，而父节点比右子节点小。如果根节点左右子树的高度差超过 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…

图遍历

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

  • 随机查找：选定一个顶点，把它放入一个无序汇合中。从汇合中取出一个顶点，拜访该顶点，把该顶点的相邻顶点放入汇合中，并把该顶点移出汇合。反复这一过程，直到汇合中的元素全副被遍历结束。
  • 深度优先遍历：选定一个顶点压入栈中，把该顶点其中的一个相邻顶点也压入栈中。拜访栈顶的顶点，如果该顶点没有其余相邻的顶点，就出栈。如果有其余相邻顶点，就把其中的一个相邻顶点压入栈中。反复这一过程，直到栈中的元素全副被遍历结束。
  • 广度优先遍历：选定一个顶点，把该顶点的相邻顶点放进队列尾部。拜访队列头部的顶点，把该顶点移出队列，如果该顶点有相邻顶点，就把相邻顶点放进队列尾部。反复这一过程，直到队列中的元素全副遍历结束。

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

一笔画

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

  1. 顶点度数示意该顶点有几条边。
  2. 如果图中有且仅有两个顶点的度数为奇数，其余为偶数，或者不存在奇数度数的顶点，则存在欧拉门路。
  3. 选定一个顶点开始画门路。
  4. 如果存在两个以上的桥，那么能够走桥。如果只剩下一个桥，就不能走桥，除非只剩下桥能够走。
  5. 如果还有没有走过的边，反复步骤 4。
  6. 胜利画出欧拉门路。

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

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

退出移动版