|
| 1 | +#JavaScript 算法与数据结构 |
| 2 | + |
| 3 | +[](https://travis-ci.org/trekhleb/javascript-algorithms) |
| 4 | +[](https://codecov.io/gh/trekhleb/javascript-algorithms) |
| 5 | + |
| 6 | +本仓库包含了多种基于 JavaScript 的算法与数据结构。 |
| 7 | + |
| 8 | +每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 |
| 9 | + |
| 10 | +##数据结构 |
| 11 | + |
| 12 | +数据结构是在计算机中组织和存储数据的一种特殊方式，它可以高效地访问和修改数据。更确切地说，数据结构是数据值的集合，它们之间的关系、函数或操作可以应用于数据。 |
| 13 | + |
| 14 | +*[链表](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/linked-list) |
| 15 | +*[队列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/queue) |
| 16 | +*[栈](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack) |
| 17 | +*[哈希表](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/hash-table) |
| 18 | +*[堆](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/heap) |
| 19 | +*[优先队列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/priority-queue) |
| 20 | +*[字典树](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/trie) |
| 21 | +*[树](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree) |
| 22 | +*[二分查找](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/binary-search-tree) |
| 23 | +*[AVL 树](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree) |
| 24 | +* 红黑树 |
| 25 | +* 后缀树 |
| 26 | +* 线段树 或 间隔树 |
| 27 | +* 二叉索引树 |
| 28 | +*[图](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/graph) (有向图与无向图) |
| 29 | +*[并查集](https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/disjoint-set) |
| 30 | + |
| 31 | +##算法 |
| 32 | + |
| 33 | +算法是如何解决一类问题的明确规范。 算法是一组精确定义操作序列的规则。 |
| 34 | + |
| 35 | +###算法主题 |
| 36 | + |
| 37 | +***数学** |
| 38 | +*[阶乘](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial) |
| 39 | +*[斐波那契数](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci) |
| 40 | +*[素数检测](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/primality-test) (排除法) |
| 41 | +*[欧几里得算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - 计算最大公约数（GCD） |
| 42 | +*[最小公倍数](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM) |
| 43 | +*[整数拆分](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition) |
| 44 | +***集合** |
| 45 | +*[笛卡尔积](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/cartesian-product) - 多集合结果 |
| 46 | +*[幂集](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - 该集合的所有子集 |
| 47 | +*[排列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (有/无重复) |
| 48 | +*[组合](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (有/无重复) |
| 49 | +*[洗牌算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/fisher-yates) - 随机置换有限序列 |
| 50 | +*[最长公共子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) |
| 51 | +*[最长递增子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence) |
| 52 | +*[Shortest Common Supersequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence) (SCS) |
| 53 | +*[背包问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) - "0/1" and "Unbound" ones |
| 54 | +*[最大子数列问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) - BF算法 与 动态编程 |
| 55 | +***字符串** |
| 56 | +*[莱温斯坦距离](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - 两个序列之间的最小编辑距离 |
| 57 | +*[汉明距离](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - 符号不同的位置数 |
| 58 | +*[克努斯-莫里斯-普拉特算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) - 子串搜索 |
| 59 | +*[字符串快速查找](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - 子串搜索 |
| 60 | +*[最长公共子串](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) |
| 61 | +***搜索** |
| 62 | +*[二分查找](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search) |
| 63 | +***排序** |
| 64 | +*[冒泡排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/bubble-sort) |
| 65 | +*[选择排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/selection-sort) |
| 66 | +*[插入排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort) |
| 67 | +*[堆排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort) |
| 68 | +*[归并排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort) |
| 69 | +*[快速排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) |
| 70 | +*[希尔排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort) |
| 71 | +***树** |
| 72 | +*[深度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS) |
| 73 | +*[广度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search) (BFS) |
| 74 | +***图** |
| 75 | +*[深度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS) |
| 76 | +*[广度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search) (BFS) |
| 77 | +*[戴克斯特拉算法m](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - 找到所有图顶点的最短路径 |
| 78 | +*[贝尔曼-福特算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - 找到所有图顶点的最短路径 |
| 79 | +*[判圈算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/detect-cycle) - 对于有向图和无向图（基于DFS和不相交集的版本） |
| 80 | +*[普林演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - 寻找加权无向图的最小生成树（MST） |
| 81 | +*[克鲁斯克尔演算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - 寻找加权无向图的最小生成树（MST） |
| 82 | +*[拓撲排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS 方法 |
| 83 | +*[关节点](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/articulation-points) - Tarjan算法（基于DFS） |
| 84 | +*[桥](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bridges) - 基于DFS的算法 |
| 85 | +*[欧拉路径与一笔画问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury的算法 - 一次访问每个边缘 |
| 86 | +*[哈密顿图](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - 恰好访问每个顶点一次 |
| 87 | +*[强连通分量](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju算法 |
| 88 | +*[旅行推销员问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman) - 尽可能以最短的路线访问每个城市并返回原始城市 |
| 89 | +***未分类** |
| 90 | +*[汉诺塔](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower) |
| 91 | +*[八皇后问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens) |
| 92 | +*[骑士巡逻](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour) |
| 93 | + |
| 94 | +###算法范式 |
| 95 | + |
| 96 | +算法范式是基于类的设计的通用方法或方法的算法。 这是一个比算法概念更高的抽象，就像一个 |
| 97 | +算法是比计算机程序更高的抽象。 |
| 98 | + |
| 99 | +***BF算法** - 查找所有可能性并选择最佳解决方案 |
| 100 | +*[最大子数列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) |
| 101 | +*[旅行推销员问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman) - 尽可能以最短的路线访问每个城市并返回原始城市 |
| 102 | + |
| 103 | +***贪心法** - 在当前选择最佳选项，不考虑以后情况 |
| 104 | +*[背包问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) |
| 105 | +*[戴克斯特拉算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - 找到所有图顶点的最短路径 |
| 106 | +*[普里姆算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - 寻找加权无向图的最小生成树（MST） |
| 107 | +*[克鲁斯卡尔算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - 寻找加权无向图的最小生成树（MST） |
| 108 | +***分治法** - 将问题分成较小的部分，然后解决这些部分 |
| 109 | +*[二分查找](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search) |
| 110 | +*[汉诺塔](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower) |
| 111 | +*[欧几里得算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - 计算最大公约数（GCD） |
| 112 | +*[排列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (有/无重复) |
| 113 | +*[组合](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/combinations) (有/无重复) |
| 114 | +*[归并排序](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort) |
| 115 | +*[Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) |
| 116 | +*[树深度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS) |
| 117 | +*[图深度优先搜索](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS) |
| 118 | +***动态编程** - 使用以前找到的子解决方案构建解决方案 |
| 119 | +*[斐波那契数](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci) |
| 120 | +*[莱温斯坦距离](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - 两个序列之间的最小编辑距离 |
| 121 | +*[最长公共子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-common-subsequnce) (LCS) |
| 122 | +*[最长公共子串](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-substring) |
| 123 | +*[最长递增子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/longest-increasing-subsequence) |
| 124 | +*[最短公共子序列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/shortest-common-supersequence) |
| 125 | +*[0-1背包问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem) |
| 126 | +*[整数拆分](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition) |
| 127 | +*[最大子数列](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray) |
| 128 | +*[贝尔曼-福特算法](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/bellman-ford) - 找到所有图顶点的最短路径 |
| 129 | +***回溯法** - 类似于 BF算法 试图产生所有可能的解决方案，但每次生成解决方案测试如果它满足所有条件，那么只有继续生成后续解决方案。 否则回溯并继续寻找不同路径的解决方案。 |
| 130 | +*[哈密顿图](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - 恰好访问每个顶点一次 |
| 131 | +*[八皇后问题](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens) |
| 132 | +*[骑士巡逻](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour) |
| 133 | +***B & B** |
| 134 | + |
| 135 | +##如何使用本仓库 |
| 136 | + |
| 137 | +**安装依赖** |
| 138 | +``` |
| 139 | +npm install |
| 140 | +``` |
| 141 | + |
| 142 | +**执行测试** |
| 143 | +``` |
| 144 | +npm test |
| 145 | +``` |
| 146 | + |
| 147 | +**按照名称执行测试** |
| 148 | +``` |
| 149 | +npm test -- -t 'LinkedList' |
| 150 | +``` |
| 151 | + |
| 152 | +**Playground** |
| 153 | + |
| 154 | +你可以在`./src/playground/playground.js`文件中操作数据结构与算法，并在`./src/playground/__test__/playground.test.js`中编写测试。 |
| 155 | + |
| 156 | +然后，只需运行以下命令来测试你的 Playground 是否按无误: |
| 157 | + |
| 158 | +``` |
| 159 | +npm test -- -t 'playground' |
| 160 | +``` |
| 161 | + |
| 162 | +##有用的信息 |
| 163 | + |
| 164 | +###引用 |
| 165 | + |
| 166 | +[▶ YouTube](https://www.youtube.com/playlist?list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8) |
| 167 | + |
| 168 | +###大O符号 |
| 169 | + |
| 170 | +大O符号中指定的算法的增长顺序。 |
| 171 | + |
| 172 | + |
| 173 | + |
| 174 | +源:[Big O Cheat Sheet](http://bigocheatsheet.com/). |
| 175 | + |
| 176 | +以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。 |
| 177 | + |
| 178 | +| 大O标记法| 计算10个元素| 计算100个元素| 计算1000个元素| |
| 179 | +| --------------| ----------------------------| -----------------------------| -------------------------------| |
| 180 | +|**O(1)**| 1| 1| 1| |
| 181 | +|**O(log N)**| 3| 6| 9| |
| 182 | +|**O(N)**| 10| 100| 1000| |
| 183 | +|**O(N log N)**| 30| 60| 9000| |
| 184 | +|**O(N^2)**| 100| 10000| 1000000| |
| 185 | +|**O(2^N)**| 1024| 1.26e+29| 1.07e+301| |
| 186 | +|**O(N!)**| 3628800| 9.3e+157| 4.02e+2567| |
| 187 | + |
| 188 | +###数据结构操作的复杂性 |
| 189 | + |
| 190 | +| 数据结构| 连接| 查找| 插入| 删除| |
| 191 | +| -----------------------| :-------:| :-------:| :-------:| :-------:| |
| 192 | +|**数组**| 1| n| n| n| |
| 193 | +|**栈**| n| n| 1| 1| |
| 194 | +|**队列**| n| n| 1| 1| |
| 195 | +|**链表**| n| n| 1| 1| |
| 196 | +|**哈希表**| -| n| n| n| |
| 197 | +|**二分查找树**| n| n| n| n| |
| 198 | +|**B树**| log(n)| log(n)| log(n)| log(n)| |
| 199 | +|**红黑树**| log(n)| log(n)| log(n)| log(n)| |
| 200 | +|**AVL树**| log(n)| log(n)| log(n)| log(n)| |
| 201 | + |
| 202 | +###数组排序算法的复杂性 |
| 203 | + |
| 204 | +| 名称| 最优| 平均| 最坏| 内存| 稳定| |
| 205 | +| ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:| |
| 206 | +|**冒泡排序**| n| n^2| n^2| 1| Yes| |
| 207 | +|**插入排序**| n| n^2| n^2| 1| Yes| |
| 208 | +|**选择排序**| n^2| n^2| n^2| 1| No| |
| 209 | +|**堆排序**| n log(n)| n log(n)| n log(n)| 1| No| |
| 210 | +|**归并排序**| n log(n)| n log(n)| n log(n)| n| Yes| |
| 211 | +|**快速排序**| n log(n)| n log(n)| n^2| log(n)| No| |
| 212 | +|**希尔排序**| n log(n)| 取决于差距序列| n (log(n))^2| 1| No| |