Commit 262bb2c
Translate to Chinese
1 parent 3e0ac74 commit 262bb2c
1 file changed
Lines changed: 212 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,212 @@ | |||
| 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 | | ||
0 commit comments