Jun
21
JavaScript 中的数据结构和算法
tommyhu , 22:43 , 软件分析与设计 , Comments(0) , Trackbacks(0) , Reads(815) , Via JavaScript 中的数据结构和算法
Large | Medium | Small


各位读者好,我最近在 Github 上面发起了一个 JavaScript 算法和数据结构 的仓库,里面有经典算法的集合,还有带有解释的以及进一步阅读的文章链接和 YouTube 的链接的用 JavaScript ES6 实现的数据结构。也有 算法和数据结构 的 YouTube 的播放列表,包含了所有在仓库中提到的视频,你或许会很方便地点击链接就进入课程学习了:)
因此我猜想你已经掌握了项目的主要理念 - 帮助开发者学习和练习算法并且通过 JavaScript 实现。
为了让这个过程更顺畅,我试着为每一个算法和数据结构放了图解的插画,有助于掌握和记住那些算法背后的原理。
你或许在根 README 文件里面发现一些实践的信息,你学习的时候会很方便。一些例如这样的信息:
- 大 O 记号图 - 快速查看哪些算法是最糟的 O(n!) 或者 O(n²)
- 一些最常用的大 O 记号列表和它们的性能比较 - 理解 10! 有多大(是 3628800)
- 数据结构操作的复杂性 - 为不同的数据结构搜索,读取,插入有多快
- 排序算法复杂度的比较表 - 帮助你根据实际情况选择更合适的排序算法。
所有的代码都有 100% 的测试覆盖率。这样做不仅保障了代码能够正确的运行,也给了一个每一个算法和数据结构是如何工作的说明,它们都有哪些基础的操作(假设轮询堆)和边界情况是什么(如果图是有向做什么)。
仓库也有一个训练场(playground)。这仅仅是一个带有空测试案例的小函数模板,在你克隆这个仓库后帮助你开始测试或者运行算法。
当前涵盖有以下数据结构:
- 链表(Linked List)
- 队列(Queue)
- 栈(Stack)
- 哈希表(Hash Table)
- 堆(Heap)
- 优先队列(Priority Queue)
- 前缀树/字典树(Trie)
- 树(二叉查找树,平衡二叉树)(Tree Binary Search Tree,AVL Tree)
- 图(有向和无向)(Graph both dirented and undirected)
- 分离集(Disjoint Set)
最重要的是数据结构有超过 50 个流行算法实现。有 排序,查找算法,图/树/集合/字符串/数学 相关的算法。所有的算法也会按照他们的模式归类:
- 暴力破解算法(Brute Force Algorithms) - 查看所有的可能性和选择最好的方案。
- 贪婪算法(Greedy Algorithms) - 在当前时间做最好的选择,不用为未来考虑。
- 分而治之算法(Divide and Conquer Algorithms) - 将问题分为更小的部分,然后解决它们。
- 动态规划算法(Dynamic Programming Algorithms) - 根据之前发现的小解决方案构建一个解决方案。
- 回溯算法(Backtracking Algorithms) - 类似于暴力破解,尝试生成所有可能的解决方案,但是每次生成一个解决方案测试是否满足所有的条件,再产生后续的解决方案。否则回溯,然后从不同的路径开始寻找解决方案。
JavaScript 算法和数据结构 仓库仍在开发状态,后面还有更多的算法和数据结构。你可以贡献你的代码为仓库的一部分,也可以是一些众所周知的算法的实现!
希望这个仓库对你有帮助!享受编程吧!