🇺🇦 乌克兰正在被俄罗斯军队攻击。平民正在遭到杀害。民用区域正在被轰炸。
- 通过以下方式帮助乌克兰：
- 更多信息请访问 war.ukraine.ua 和 乌克兰外交部
本仓库包含了许多基于 JavaScript 的流行算法和数据结构的示例实现。
每种算法和数据结构都有自己的 README，其中包含相关说明和进一步阅读的链接（包括 YouTube 视频链接）。
其他语言版本： English
☝ 请注意，本项目仅用于学习和研究目的，不适用于生产环境。
数据结构是一种在计算机中组织和存储数据的特定方式，以便能够高效地访问和修改数据。更确切地说，数据结构是数据值的集合，以及这些值之间的关系，以及可以应用于数据的函数或操作。
请记住，每种数据结构都有其权衡。在选择某种数据结构时，你应该更关注为什么选择它，而不是如何实现它。
B - 初级, A - 高级
B链表B双向链表B队列B栈B哈希表B堆 - 最大堆和最小堆B优先队列A字典树A树A图 (有向图和无向图)A并查集 - 一种用于管理一组不相交集合的数据结构A布隆过滤器ALRU 缓存 - 最近最少使用（LRU）缓存
算法是解决一类问题的明确规范。算法是一组精确定义操作序列的规则。
B - 初级, A - 高级
- 数学
B位运算 - 设置/获取/更新/清除位，乘/除以二，使负数等B二进制浮点数 - 浮点数的二进制表示B阶乘B斐波那契数 - 经典版本和闭合形式版本B素因子 - 使用 Hardy-Ramanujan 定理查找和计算素因子B素性测试 (试除法)B欧几里得算法 - 计算最大公约数 (GCD)B最小公倍数 (LCM)B埃拉托斯特尼筛法 - 查找给定限制内的所有质数B判断 2 的幂 - 检查数字是否为 2 的幂（朴素和按位算法）B杨辉三角形B复数 - 复数及其基本运算B弧度和角度 - 弧度与角度互相转换B快速幂B霍纳法则 - 多项式求值B矩阵 - 矩阵和基本矩阵操作（乘法、转置等）B欧几里得距离 - 点/向量/矩阵之间的距离A整数拆分A平方根 - 牛顿法A刘徽 π 算法 - 基于 N-gons 的近似 π 计算A离散傅里叶变换 - 把时间信号分解成构成它的频率
- 集合
- 字符串
B汉明距离 - 符号不同的位置数B回文 - 检查字符串是否与其反转形式相同A莱温斯坦距离 - 两个序列之间的最小编辑距离AKnuth–Morris–Pratt 算法 (KMP) - 子串搜索（模式匹配）AZ 算法 - 子串搜索（模式匹配）ARabin Karp 算法 - 子串搜索A最长公共子串A正则表达式匹配
- 搜索
- 排序
- 链表
- 树
- 图
B深度优先搜索 (DFS)B广度优先搜索 (BFS)B克鲁斯克尔算法 - 寻找加权无向图的最小生成树 (MST)A戴克斯特拉算法 - 找到图中所有顶点的最短路径A贝尔曼-福特算法 - 找到图中所有顶点的最短路径A弗洛伊德-沃舍尔算法 - 找到所有顶点对之间的最短路径A检测环 - 对有向图和无向图都适用（基于 DFS 和并查集）A普里姆算法 - 寻找加权无向图的最小生成树 (MST)A拓扑排序 - DFS 方法A关节点 - Tarjan 算法（基于 DFS）A桥 - 基于 DFS 的算法A欧拉路径与欧拉回路 - Fleury 算法 - 恰好访问每条边一次A哈密顿回路 - 恰好访问每个顶点一次A强连通分量 - Kosaraju 算法A旅行推销员问题 - 尽可能以最短的路径访问每个城市并返回出发城市
- 密码学
- 机器学习
BNanoNeuron - 7 个简单的 JS 函数，说明机器如何学习（正向/反向传播）Bk-NN - k-近邻分类算法Bk-均值 - k-均值聚类算法
- 图像处理
BSeam Carving - 内容感知图像缩放算法
- 统计
B加权随机 - 根据项目权重从列表中随机选择项目
- 演化算法
A遗传算法 - 遗传算法应用于自动泊车汽车训练的示例
- 未分类
算法范式是一种通用方法或解决问题的方法。这是一种比算法更高层次的抽象，就像算法是比计算机程序更高层次的抽象一样。
- 暴力法 - 遍历所有可能性并选择最佳解决方案
- 贪心法 - 在当前选择最优解，不考虑未来后果
- 分治法 - 将问题分成较小的部分，然后解决这些部分
- 动态规划 - 使用先前找到的子解决方案来构建解决方案
- 回溯法 - 与暴力法类似，尝试产生所有可能的解决方案，但每次生成解决方案测试如果它满足所有条件，那么只继续生成后续解决方案。否则回溯并继续寻找不同路径的解决方案。通常使用深度优先搜索（DFS）遍历状态空间。
- 分支限界法 - 记住在回溯搜索的每个阶段找到的成本最低的解，并使用到目前为止找到的成本最低解的成本作为下限，以丢弃代价更高的解决方案，通常与状态空间树的 BFS 遍历结合使用。
安装所有依赖
npm install
运行 ESLint
你可能希望运行它来检查代码质量。
npm run lint
运行所有测试
npm test
按名称运行测试
npm test -- 'LinkedList'
调试
如果 linting 或测试失败，请尝试删除 node_modules 文件夹并重新安装 npm 包：
rm -rf ./node_modules
npm i
另外，确保你使用的是正确的 Node 版本（>=16）。如果你使用 nvm 进行 Node 版本管理，可以从项目根文件夹运行 nvm use，系统会采用正确的版本。
案例演练
你可以在 ./src/playground/playground.js 文件中使用数据结构和算法，并在 ./src/playground/__test__/playground.test.js 中为其编写测试。
然后，只需运行以下命令来测试你的游乐场代码是否按预期工作：
npm test -- 'playground'
大 O 表示法用于对算法的运行时间或空间需求增长的分类，随着输入规模的增长而变化。 在下面的图表中，您可以找到按大 O 表示法指定的最常见增长阶。
以下是一些最常用的大 O 符号及其针对不同大小输入数据的性能比较列表。
| 大 O 表示法 | 类型 | 10 个元素的计算次数 | 100 个元素的计算次数 | 1000 个元素的计算次数 |
|---|---|---|---|---|
| O(1) | 常数 | 1 | 1 | 1 |
| O(log N) | 对数 | 3 | 6 | 9 |
| O(N) | 线性 | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | 平方 | 100 | 10000 | 1000000 |
| O(2^N) | 指数 | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 阶乘 | 3628800 | 9.3e+157 | 4.02e+2567 |
| 数据结构 | 访问 | 查找 | 插入 | 删除 | 备注 |
|---|---|---|---|---|---|
| 数组 | 1 | n | n | n | |
| 栈 | n | n | 1 | 1 | |
| 队列 | n | n | 1 | 1 | |
| 链表 | n | n | 1 | n | |
| 哈希表 | - | n | n | n | 在完美哈希函数情况下，成本为 O(1) |
| 二叉查找树 | n | n | n | n | 在平衡树的情况下，成本为 O(log(n)) |
| B 树 | log(n) | log(n) | log(n) | log(n) | |
| 红黑树 | log(n) | log(n) | log(n) | log(n) | |
| AVL 树 | log(n) | log(n) | log(n) | log(n) | |
| 布隆过滤器 | - | 1 | 1 | - | 查找过程中可能出现假阳性 |
| 名称 | 最佳情况 | 平均情况 | 最坏情况 | 内存 | 稳定 | 备注 |
|---|---|---|---|---|---|---|
| 冒泡排序 | n | n2 | n2 | 1 | 是 | |
| 插入排序 | n | n2 | n2 | 1 | 是 | |
| 选择排序 | n2 | n2 | n2 | 1 | 否 | |
| 堆排序 | n log(n) | n log(n) | n log(n) | 1 | 否 | |
| 归并排序 | n log(n) | n log(n) | n log(n) | n | 是 | |
| 快速排序 | n log(n) | n log(n) | n2 | log(n) | 否 | 快速排序通常是原地排序，使用 O(log(n))的栈空间 |
| 希尔排序 | n log(n) | 取决于间隙序列 | n (log(n))2 | 1 | 否 | |
| 计数排序 | n + r | n + r | n + r | n + r | 是 | r - 数组中最大的数 |
| 基数排序 | n * k | n * k | n * k | n + k | 是 | k - 最长键的长度 |
支持该项目的人们 ∑ = 1
在 trekhleb.dev 上还有更多关于 JavaScript 和算法的项目和文章