排序算法

冒泡排序算法

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过多次遍历数组，依次比较相邻的两个元素，如果它们的顺序错误就交换它们，直到整个数组排序完成。冒泡排序的时间复杂度为 O(n^2)，属于一种比较低效的排序算法，但是由于其简单易懂的实现方式，在某些特定场景下仍然有用。

以下是 JavaScript 中冒泡排序算法的实现：

 1function bubbleSort(arr) {
 2    const len = arr.length;
 3    // 外层循环控制比较的轮数
 4    for (let i = 0; i < len - 1; i++) {
 5        // 内层循环控制每一轮比较的次数
 6        for (let j = 0; j < len - 1 - i; j++) {
 7            // 如果相邻的两个元素顺序错误，则交换它们
 8            if (arr[j] > arr[j + 1]) {
 9                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
10            }
11        }
12    }
13    return arr;
14}
15// 示例
16const arr = [5, 3, 8, 4, 2];
17console.log(bubbleSort(arr)); // 输出: [2, 3, 4, 5, 8]

在这个实现中，我们使用了两层嵌套的循环。外层循环控制比较的轮数，内层循环控制每一轮比较的次数。在每一轮比较中，我们依次比较相邻的两个元素，如果它们的顺序错误就交换它们。经过多轮的比较和交换，最终整个数组就会排序完成。

选择排序算法

选择排序（Selection Sort）是一种简单直观的排序算法，它的工作原理是每一次遍历数组，找到最小（或最大）的元素，然后将其放到数组的起始位置（或末尾位置），再从剩余未排序的元素中继续寻找最小（或最大）的元素，重复这个过程，直到整个数组排序完成。选择排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

以下是 JavaScript 中选择排序算法的实现：

 1function selectionSort(arr) {
 2    const len = arr.length;
 3    // 外层循环控制每一轮的起始位置
 4    for (let i = 0; i < len - 1; i++) {
 5        let minIndex = i; // 记录最小元素的索引
 6        // 内层循环找到未排序部分的最小元素
 7        for (let j = i + 1; j < len; j++) {
 8            if (arr[j] < arr[minIndex]) {
 9                minIndex = j; // 更新最小元素的索引
10            }
11        }
12        // 将未排序部分的最小元素与当前起始位置的元素交换
13        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
14    }
15    return arr;
16}
17
18// 示例
19const arr = [5, 3, 8, 4, 2];
20console.log(selectionSort(arr)); // 输出: [2, 3, 4, 5, 8]

在这个实现中，我们使用了两层嵌套的循环。外层循环控制每一轮的起始位置，内层循环找到未排序部分的最小元素，并记录其索引。最后，将最小元素与当前起始位置的元素进行交换。通过多次循环和交换，最终整个数组就会排序完成。

插入排序算法

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是将数组分为已排序部分和未排序部分，初始时已排序部分只有第一个元素，然后逐步将未排序部分的元素插入到已排序部分的合适位置，直到整个数组排序完成。插入排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

以下是 JavaScript 中插入排序算法的实现：

 1function insertionSort(arr) {
 2    const len = arr.length;
 3    // 外层循环从第二个元素开始，依次遍历未排序部分的元素
 4    for (let i = 1; i < len; i++) {
 5        let current = arr[i]; // 记录当前待插入的元素
 6        let j = i - 1; // 记录已排序部分的最后一个元素的索引
 7        // 内层循环将当前待插入的元素插入到已排序部分的合适位置
 8        while (j >= 0 && arr[j] > current) {
 9            arr[j + 1] = arr[j]; // 向右移动元素
10            j--; // 继续向前比较
11        }
12        arr[j + 1] = current; // 将当前元素插入到合适位置
13    }
14    return arr;
15}
16
17// 示例
18const arr = [5, 3, 8, 4, 2];
19console.log(insertionSort(arr)); // 输出: [2, 3, 4, 5, 8]

在这个实现中，我们使用了两层嵌套的循环。外层循环从第二个元素开始遍历未排序部分的元素，内层循环将当前待插入的元素插入到已排序部分的合适位置。通过不断向前比较和移动元素，最终将当前元素插入到合适的位置，完成一轮插入操作。通过多次循环，最终整个数组就会排序完成。

快速排序算法

快速排序（Quick Sort）是一种常用的排序算法，它基于分治思想，通过递归地将数组分为两部分，一部分的元素都小于另一部分的元素，然后对这两部分分别进行快速排序，直到整个数组排序完成。快速排序的平均时间复杂度为 O(n log n)，最坏情况下的时间复杂度为 O(n^2)，空间复杂度为 O(log n)。

以下是 JavaScript 中快速排序算法的实现：

 1function quickSort(arr) {
 2    if (arr.length <= 1) {
 3        return arr; // 如果数组长度小于等于 1，直接返回
 4    }
 5
 6    const pivot = arr[0]; // 选择第一个元素作为基准值
 7    const left = []; // 存放比基准值小的元素
 8    const right = []; // 存放比基准值大的元素
 9
10    // 将数组分为左右两部分
11    for (let i = 1; i < arr.length; i++) {
12        if (arr[i] < pivot) {
13            left.push(arr[i]); // 比基准值小的元素放到左边
14        } else {
15            right.push(arr[i]); // 比基准值大的元素放到右边
16        }
17    }
18
19    // 对左右两部分分别进行快速排序
20    return quickSort(left).concat(pivot, quickSort(right));
21}
22
23// 示例
24const arr = [5, 3, 8, 4, 2];
25console.log(quickSort(arr)); // 输出: [2, 3, 4, 5, 8]

在这个实现中，我们首先选择数组的第一个元素作为基准值（pivot），然后将数组分为比基准值小的元素和比基准值大的元素两部分。接着，对这两部分分别递归地进行快速排序，最后将左、基准值、右三部分拼接起来。通过递归地进行快速排序，最终整个数组就会排序完成。

归并排序算法

归并排序（Merge Sort）是一种分治算法，它的基本思想是将待排序的数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

以下是 JavaScript 中归并排序算法的实现：

 1function mergeSort(arr) {
 2    if (arr.length <= 1) {
 3        return arr; // 如果数组长度小于等于 1，直接返回
 4    }
 5
 6    // 将数组分为两部分
 7    const middle = Math.floor(arr.length / 2);
 8    const left = arr.slice(0, middle);
 9    const right = arr.slice(middle);
10
11    // 分别对左右两部分进行归并排序
12    return merge(mergeSort(left), mergeSort(right));
13}
14
15function merge(left, right) {
16    let result = [];
17    let leftIndex = 0;
18    let rightIndex = 0;
19
20    // 合并两个有序数组
21    while (leftIndex < left.length && rightIndex < right.length) {
22        if (left[leftIndex] < right[rightIndex]) {
23            result.push(left[leftIndex]);
24            leftIndex++;
25        } else {
26            result.push(right[rightIndex]);
27            rightIndex++;
28        }
29    }
30
31    // 将剩余的元素添加到结果数组中
32    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
33}
34
35// 示例
36const arr = [5, 3, 8, 4, 2];
37console.log(mergeSort(arr)); // 输出: [2, 3, 4, 5, 8]

在这个实现中，我们首先将数组分为左右两部分，然后对左右两部分分别进行归并排序。最后，利用 merge 函数将排好序的左右两部分合并成一个有序的数组。通过递归地进行归并排序，最终整个数组就会排序完成。

查找算法

线性查找算法

线性查找（Linear Search）是一种简单直观的查找算法，它的基本思想是逐个检查数组中的每个元素，直到找到目标元素或者遍历完整个数组。线性查找的时间复杂度为 O(n)，其中 n 是数组的长度。

以下是 JavaScript 中线性查找算法的实现：

 1function linearSearch(arr, target) {
 2    for (let i = 0; i < arr.length; i++) {
 3        if (arr[i] === target) {
 4            return i; // 找到目标元素，返回索引
 5        }
 6    }
 7    return -1; // 没有找到目标元素，返回 -1
 8}
 9
10// 示例
11const arr = [5, 3, 8, 4, 2];
12const target = 8;
13console.log(linearSearch(arr, target)); // 输出: 2（目标元素 8 在数组中的索引为 2）

二分查找算法

二分查找（Binary Search）是一种高效的查找算法，它要求被查找的数组是有序的。二分查找的基本思想是通过不断地将查找范围缩小一半，来快速定位目标元素的位置。具体实现是在每一步查找中，将待查找范围的中间元素与目标元素进行比较，如果相等则找到了目标元素，如果目标元素小于中间元素，则继续在左半边进行查找，否则在右半边进行查找。二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。

以下是 JavaScript 中二分查找算法的实现：

 1function binarySearch(arr, target) {
 2    let left = 0; // 查找范围的左边界
 3    let right = arr.length - 1; // 查找范围的右边界
 4
 5    while (left <= right) {
 6        let mid = Math.floor((left + right) / 2); // 中间元素的索引
 7        if (arr[mid] === target) {
 8            return mid; // 找到目标元素，返回索引
 9        } else if (arr[mid] < target) {
10            left = mid + 1; // 在右半边进行查找
11        } else {
12            right = mid - 1; // 在左半边进行查找
13        }
14    }
15
16    return -1; // 没有找到目标元素，返回 -1
17}
18
19// 示例
20const arr = [2, 3, 4, 5, 8];
21const target = 8;
22console.log(binarySearch(arr, target)); // 输出: 4（目标元素 8 在数组中的索引为 4）

在这个实现中，我们使用一个 while 循环在查找范围内不断缩小查找范围，直到找到目标元素或者查找范围为空。在每一步查找中，我们通过计算中间元素的索引，并与目标元素进行比较，然后根据比较结果更新查找范围的边界。通过二分查找算法，可以在有序数组中快速找到目标元素。

哈希查找算法

哈希查找（Hash Search）算法是一种基于哈希表的查找算法，它通过将元素的关键字（key）通过哈希函数映射到哈希表中的一个位置（索引），然后在该位置上查找目标元素。哈希表通常是一个数组，每个位置称为一个哈希桶，可以存放一个或多个元素，这些元素通常被称为哈希碰撞（collision）。哈希查找的时间复杂度在理想情况下为 O(1)，但在发生哈希碰撞时可能会退化为 O(n)，其中 n 是哈希表的大小。

以下是 JavaScript 中哈希查找算法的简单实现示例：

 1// 哈希函数：将关键字映射为哈希表的索引
 2function hash(key, size) {
 3    let hashValue = 0;
 4    for (let i = 0; i < key.length; i++) {
 5        hashValue += key.charCodeAt(i);
 6    }
 7    return hashValue % size; // 对哈希值取模，使其落在合法的范围内
 8}
 9
10// 哈希表查找函数
11function hashSearch(hashTable, key) {
12    const index = hash(key, hashTable.length);
13    const bucket = hashTable[index]; // 获取哈希桶
14    for (let i = 0; i < bucket.length; i++) {
15        if (bucket[i].key === key) {
16            return bucket[i].value; // 找到目标元素，返回对应的值
17        }
18    }
19    return null; // 没有找到目标元素，返回 null
20}
21
22// 示例：使用对象数组模拟哈希表
23const hashTable = [
24    [{ key: "abc", value: 123 }], // 哈希桶 0
25    [], // 哈希桶 1
26    [{ key: "def", value: 456 }] // 哈希桶 2
27];
28
29console.log(hashSearch(hashTable, "abc")); // 输出: 123
30console.log(hashSearch(hashTable, "def")); // 输出: 456
31console.log(hashSearch(hashTable, "xyz")); // 输出: null（未找到）

在这个示例中，我们使用了一个简单的哈希函数 hash，它将关键字的 ASCII 码值相加，并对哈希表的大小取模，得到哈希表的索引。然后，我们通过哈希函数计算出关键字对应的索引，并在该索引上查找目标元素。由于哈希表中的每个位置存放的是一个哈希桶（数组），所以需要遍历该哈希桶来查找目标元素。

动态规划算法

用于解决具有最优子结构性质的问题，如背包问题、最长递增子序列等。

动态规划（Dynamic Programming，简称 DP）是一种解决多阶段决策过程最优化问题的数学方法。它将原问题分解为若干个子问题，通过保存子问题的解，避免重复计算，从而提高效率。动态规划通常适用于具有最优子结构性质的问题，即原问题的最优解可以由子问题的最优解推导得到。

动态规划算法通常采用自底向上或自顶向下的方法，其中自底向上的方法一般通过迭代方式求解，自顶向下的方法一般通过递归方式求解。

以下是动态规划算法的一般步骤：

1. 定义状态：确定问题的状态，即原问题和子问题的解空间。
2. 确定状态转移方程：根据问题的最优子结构性质，建立状态之间的递推关系。
3. 初始化状态：确定初始状态的值。
4. 计算状态：按照状态转移方程，从初始状态开始逐步计算出所有状态的值。
5. 解决原问题：根据计算得到的状态值，求出原问题的解。

以下是一个经典的动态规划问题示例：斐波那契数列。

斐波那契数列问题

斐波那契数列是一个经典的动态规划问题，其定义如下：

• 若第 1 和第 2 个数为 1，则第 n 个数为前两个数的和。
• 即 F(n) = F(n-1) + F(n-2)，其中 n > 2。

以下是 JavaScript 中斐波那契数列的动态规划算法实现：

 1function fibonacci(n) {
 2    const dp = [0, 1]; // 初始化状态
 3    for (let i = 2; i <= n; i++) {
 4        dp[i] = dp[i - 1] + dp[i - 2]; // 计算状态
 5    }
 6    return dp[n]; // 解决原问题
 7}
 8
 9// 示例
10console.log(fibonacci(5)); // 输出: 5

在这个实现中，我们使用数组 dp 来保存斐波那契数列的状态值，其中 dp[i] 表示第 i 个斐波那契数的值。通过迭代计算每个状态的值，最终求解出原问题的解。

贪心算法

贪心算法（Greedy Algorithm）是一种解决问题的算法思想，它每一步都选择当前状态下的最优解，而不考虑后续可能带来的影响，从而希望最终得到全局最优解。贪心算法通常适用于那些具有最优子结构性质的问题，并且每一步的最优解可以推导出全局最优解。

贪心算法的基本思路是通过局部最优解来构造全局最优解，它不会回溯已经做出的选择，因此具有高效性和简单性。然而，并非所有问题都适合使用贪心算法，因为贪心算法所得到的解不一定是最优解，有些问题可能需要使用动态规划等其他算法来求解。

以下是贪心算法的一般步骤：

1. 定义问题：明确问题的输入、输出和限制条件。
2. 确定贪心策略：根据问题的特点选择合适的贪心策略，即每一步的最优选择。
3. 验证可行性：验证贪心策略是否可以得到正确的解。
4. 实现算法：根据贪心策略实现算法。
5. 分析复杂性：分析算法的时间复杂度和空间复杂度。

以下是一个经典的贪心算法问题示例：零钱兑换问题。

零钱兑换问题

假设有一堆面值为 1 元、5 元、10 元的硬币，现需要找零 N 元，求最少需要多少个硬币。

以下是 JavaScript 中零钱兑换问题的贪心算法实现：

 1function coinChange(coins, amount) {
 2    coins.sort((a, b) => b - a); // 将硬币面值按降序排列
 3    let count = 0;
 4    for (let i = 0; i < coins.length; i++) {
 5        while (amount >= coins[i]) {
 6            amount -= coins[i];
 7            count++;
 8        }
 9    }
10    if (amount === 0) {
11        return count; // 找零成功，返回硬币数量
12    } else {
13        return -1; // 找零失败，返回 -1
14    }
15}
16
17// 示例
18const coins = [1, 5, 10];
19const amount = 20;
20console.log(coinChange(coins, amount)); // 输出: 2（需要两个 10 元硬币）

在这个实现中，我们首先将硬币面值按降序排列，然后从面值最大的硬币开始尽可能多地找零，直到无法找零为止。通过贪心策略，每次选择面值最大的硬币来找零，可以保证找零的硬币数量最少。

递归算法

递归算法（Recursion Algorithm）是一种解决问题的方法，它通过将一个大问题分解为一个或多个相似的子问题，并通过对这些子问题的解进行递归调用来解决原始问题。递归算法通常包含两个部分：基本情况（Base Case）和递归情况（Recursive Case）。基本情况是指解决问题的最简单情况，递归情况是指将原始问题转化为相似但规模更小的子问题。

递归算法在实现过程中需要注意两个重要的方面：递归调用和终止条件。递归调用是指函数在执行过程中调用自身，而终止条件是指递归调用的结束条件，用于避免无限递归。

递归算法通常用于解决树、图等数据结构的问题，也可以用于解决一些具有递归性质的数学问题。

以下是一个经典的递归算法问题示例：阶乘计算。

阶乘计算问题

阶乘是指从 1 到 n 的所有正整数相乘的结果，通常表示为 n!。阶乘计算问题是计算给定正整数 n 的阶乘值。

以下是 JavaScript 中阶乘计算问题的递归算法实现：

 1function factorial(n) {
 2    // 基本情况：当 n 等于 0 或 1 时，阶乘值为 1
 3    if (n === 0 || n === 1) {
 4        return 1;
 5    }
 6    // 递归情况：计算 n 的阶乘值
 7    return n * factorial(n - 1);
 8}
 9
10// 示例
11const n = 5;
12console.log(factorial(n)); // 输出: 120（5 的阶乘值为 5*4*3*2*1 = 120）

在这个实现中，我们使用了递归调用来计算给定正整数 n 的阶乘值。当 n 为 0 或 1 时，表示已经到达基本情况，直接返回 1；当 n 大于 1 时，表示还需要继续进行递归调用，直到达到基本情况为止。递归算法的实现需要注意终止条件，否则可能会导致无限递归的情况。

图算法

图算法是一种用于处理图结构的算法，图是由顶点（Vertex）和边（Edge）组成的数据结构，通常用于表示对象之间的关系。图算法可以解决各种与图相关的问题，例如图的遍历、最短路径、最小生成树、拓扑排序等。

以下是一些常见的图算法问题：

1. 图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS）是常用的图遍历算法，用于访问图中的所有顶点。
2. 最短路径：Dijkstra 算法和 Bellman-Ford 算法可以用于找到图中两个顶点之间的最短路径。
3. 最小生成树：Prim 算法和 Kruskal 算法可以用于找到图中的最小生成树，即包含所有顶点且边权值之和最小的树。
4. 拓扑排序：拓扑排序算法用于对有向无环图进行排序，以使得图中的所有顶点按照一定的顺序排列。
5. 图的连通性：深度优先搜索和并查集算法可以用于判断图中的顶点是否连通，以及找到连通分量。
6. 图的最大流：Ford-Fulkerson 算法和 Edmonds-Karp 算法可以用于求解图的最大流问题。

图算法的选择取决于具体的问题和图的特性，不同的算法可能适用于不同类型的图。因此，在解决图相关的问题时，需要根据具体情况选择合适的算法。

以下是一个示例，展示如何使用 JavaScript 实现深度优先搜索（DFS）和广度优先搜索（BFS）：

 1// 图的表示：邻接表
 2const graph = {
 3    0: [1, 2],
 4    1: [3],
 5    2: [4],
 6    3: [],
 7    4: []
 8};
 9
10// 深度优先搜索（DFS）
11function dfs(node, visited = new Set()) {
12    if (visited.has(node)) {
13        return;
14    }
15    visited.add(node);
16    console.log(node);
17    for (const neighbor of graph[node]) {
18        dfs(neighbor, visited);
19    }
20}
21
22// 广度优先搜索（BFS）
23function bfs(start) {
24    const visited = new Set();
25    const queue = [start];
26    visited.add(start);
27    while (queue.length > 0) {
28        const node = queue.shift();
29        console.log(node);
30        for (const neighbor of graph[node]) {
31            if (!visited.has(neighbor)) {
32                visited.add(neighbor);
33                queue.push(neighbor);
34            }
35        }
36    }
37}
38
39console.log("DFS:");
40dfs(0);
41console.log("BFS:");
42bfs(0);

在这个示例中，我们使用邻接表来表示图，然后分别使用深度优先搜索（DFS）和广度优先搜索（BFS）算法来遍历图中的顶点。

字符串匹配算法

字符串匹配算法是一种用于在一个字符串（文本）中查找一个子串（模式）的算法。它通常用于在文本中搜索特定的模式，并返回模式在文本中的位置或出现次数。

以下是一些常见的字符串匹配算法：

1. 暴力匹配算法：也称为朴素字符串匹配算法，它是一种简单直观的方法，遍历文本中的每个字符，并与模式进行比较，直到找到匹配或遍历完整个文本。
2. KMP 算法：KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它利用了模式字符串内部的信息来避免不必要的比较，从而提高了匹配效率。
3. Boyer-Moore 算法：Boyer-Moore 算法是一种经典的字符串匹配算法，它通过比较模式字符串和文本中的字符，利用坏字符规则和好后缀规则来跳过不必要的比较，从而实现快速匹配。
4. Rabin-Karp 算法：Rabin-Karp 算法是一种基于哈希的字符串匹配算法，它利用了哈希值的特性，在文本中滑动窗口进行匹配，并通过比较哈希值来快速判断是否匹配。
5. Sunday 算法：Sunday 算法是一种简单的字符串匹配算法，它利用了模式字符串中字符在文本中出现位置的规律，通过预先计算字符在模式字符串中的偏移量来加快匹配速度。

以上这些算法各有优缺点，适用于不同类型的字符串匹配问题。在实际应用中，需要根据具体情况选择合适的算法。

以下是一个示例，展示如何使用 JavaScript 实现暴力匹配算法：

 1function bruteForce(text, pattern) {
 2    const n = text.length;
 3    const m = pattern.length;
 4    for (let i = 0; i <= n - m; i++) {
 5        let j;
 6        for (j = 0; j < m; j++) {
 7            if (text[i + j] !== pattern[j]) {
 8                break;
 9            }
10        }
11        if (j === m) {
12            return i; // 匹配成功，返回匹配的起始位置
13        }
14    }
15    return -1; // 匹配失败，返回 -1
16}
17
18// 示例
19const text = "hello world";
20const pattern = "world";
21console.log(bruteForce(text, pattern)); // 输出: 6（模式 "world" 在文本 "hello world" 中的起始位置为 6）

在这个示例中，我们使用了暴力匹配算法来搜索模式字符串在文本中的位置。算法的基本思想是从文本的每个可能的位置开始，逐个字符地与模式进行比较，直到找到匹配的子串或者遍历完整个文本。

位运算算法

位运算算法是一类基于二进制位操作的算法，常用于处理整数的位级表示和操作。位运算算法通常包括位与、位或、位异或、位取反等操作，以及位移操作（左移和右移）等。

以下是一些常见的位运算算法：

1. 位与（AND）：将两个操作数的对应位进行与操作，只有当两个位都为 1 时，结果位才为 1。
2. 位或（OR）：将两个操作数的对应位进行或操作，只要两个位中至少有一个位为 1，结果位就为 1。
3. 位异或（XOR）：将两个操作数的对应位进行异或操作，只有当两个位不相同时，结果位才为 1。
4. 位取反（NOT）：将操作数的每一位取反，即将 0 变为 1，将 1 变为 0。
5. 位移操作：左移和右移操作分别将操作数的二进制表示向左或向右移动指定的位数，空出的位置用 0 填充（左移）或者用符号位填充（右移）。

位运算算法通常用于优化代码性能、节省内存空间和进行一些高级的操作，例如实现布隆过滤器、位图等数据结构，或者进行一些位级的计算和编码。

以下是一个示例，展示如何使用 JavaScript 实现一些常见的位运算操作：

 1const a = 0b1010; // 十进制为 10
 2const b = 0b1100; // 十进制为 12
 3
 4// 位与（AND）
 5console.log("位与（AND）：", a & b); // 输出: 8（二进制为 0b1000）
 6
 7// 位或（OR）
 8console.log("位或（OR）：", a | b); // 输出: 14（二进制为 0b1110）
 9
10// 位异或（XOR）
11console.log("位异或（XOR）：", a ^ b); // 输出: 6（二进制为 0b0110）
12
13// 位取反（NOT）
14console.log("位取反（NOT）：", ~a); // 输出: -11（二进制为 0b11111111111111111111111111110101）
15
16// 左移操作
17console.log("左移 2 位：", a << 2); // 输出: 40（二进制为 0b101000）
18
19// 右移操作
20console.log("右移 1 位：", b >> 1); // 输出: 6（二进制为 0b110）

数学算法

数学算法是一类用于解决数学问题的算法，涵盖了广泛的领域，包括基本的数学运算、数论、代数、几何、概率统计等方面。数学算法在计算机科学和工程中具有广泛的应用，常用于解决科学计算、数据分析、图形图像处理等问题。

以下是一些常见的数学算法：

1. 四则运算：包括加法、减法、乘法和除法等基本的算术运算。
2. 质因数分解：将一个正整数表示为若干个质数的乘积的形式。
3. 最大公约数和最小公倍数：求两个正整数的最大公约数和最小公倍数。
4. 素数判断：判断一个正整数是否为素数（只能被 1 和自身整除的正整数）。
5. 幂运算：求一个数的整数次幂。
6. 排列组合：求解从 n 个元素中选取 k 个元素的排列和组合的个数。
7. 快速幂算法：通过分治法来求解幂运算，提高了计算效率。
8. 牛顿迭代法：用于求解方程的近似根，例如求解平方根、立方根等。
9. 高斯消元法：用于求解线性方程组的解。
10. 简单线性回归和多项式回归：用于拟合数据点并得到最佳拟合曲线的参数。
11. 蒙特卡洛方法：一种随机模拟方法，用于求解数学问题的近似解。

以上这些算法涵盖了数学中的许多常见问题，它们在不同领域和场景中都具有重要的作用。在实际应用中，需要根据具体问题选择合适的数学算法进行求解。

四则运算算法

四则运算算法是指对于给定的数字和运算符（加法、减法、乘法、除法），按照一定的规则进行运算，得到最终的结果。四则运算算法是数学中最基本的运算之一，在计算机科学中也有广泛的应用。

以下是一个简单的四则运算算法实现示例，涵盖了基本的加法、减法、乘法和除法：

 1def calculate(expression):
 2    stack = []
 3    num = 0
 4    sign = '+'
 5    for i, char in enumerate(expression):
 6        if char.isdigit():
 7            num = num * 10 + int(char)
 8        if char in "+-*/" or i == len(expression) - 1:
 9            if sign == '+':
10                stack.append(num)
11            elif sign == '-':
12                stack.append(-num)
13            elif sign == '*':
14                stack[-1] *= num
15            elif sign == '/':
16                stack[-1] = int(stack[-1] / num)
17            num = 0
18            sign = char
19    return sum(stack)
20
21# 示例
22expression = "3+2*2"
23print(calculate(expression))  # 输出: 7（等价于 3 + 2 * 2）
24

在这个示例中，我们使用一个栈来存储数字，并根据运算符的优先级依次计算结果。具体来说，遍历表达式中的每个字符，如果是数字则累积构成一个数字，如果是运算符则根据前一个运算符的类型进行相应的计算，并将结果压入栈中。最后将栈中所有数字相加得到最终结果。

需要注意的是，以上示例只适用于不带括号的简单四则运算表达式。对于带有括号的复杂表达式，需要使用更复杂的算法来处理。

质因数分解算法

质因数分解算法是将一个正整数表示为若干个质数的乘积的形式。质因数分解是数论中的基本问题之一，也是计算机科学中的重要算法之一，具有广泛的应用。

以下是一个简单的质因数分解算法的实现示例：

 1def prime_factors(n):
 2    factors = []
 3    divisor = 2
 4    while n > 1:
 5        while n % divisor == 0:
 6            factors.append(divisor)
 7            n //= divisor
 8        divisor += 1
 9    return factors
10
11# 示例
12n = 60
13print(prime_factors(n))  # 输出: [2, 2, 3, 5]（60 = 2 * 2 * 3 * 5）

最大公约数和最小公倍数算法

下面是 JavaScript 中计算最大公约数（GCD）和最小公倍数（LCM）的算法实现：

 1// 计算最大公约数（Greatest Common Divisor，GCD）
 2function gcd(a, b) {
 3    while (b !== 0) {
 4        const temp = b;
 5        b = a % b;
 6        a = temp;
 7    }
 8    return a;
 9}
10
11// 计算最小公倍数（Least Common Multiple，LCM）
12function lcm(a, b) {
13    return (a * b) / gcd(a, b);
14}
15
16// 示例
17const num1 = 12;
18const num2 = 18;
19console.log("最大公约数:", gcd(num1, num2)); // 输出: 6
20console.log("最小公倍数:", lcm(num1, num2)); // 输出: 36

在这个示例中，我们使用欧几里德算法来计算最大公约数（GCD）。该算法通过连续取余操作来找到两个数的最大公约数，直到其中一个数为 0。然后，我们使用最大公约数来计算最小公倍数（LCM），通过公式 LCM = (a * b) / GCD(a, b) 来计算。

素数判断算法

下面是 JavaScript 中判断一个正整数是否为素数的算法实现：

 1// 判断一个正整数是否为素数
 2function isPrime(n) {
 3    if (n <= 1) {
 4        return false;
 5    }
 6    if (n <= 3) {
 7        return true;
 8    }
 9    if (n % 2 === 0 || n % 3 === 0) {
10        return false;
11    }
12    for (let i = 5; i * i <= n; i += 6) {
13        if (n % i === 0 || n % (i + 2) === 0) {
14            return false;
15        }
16    }
17    return true;
18}
19
20// 示例
21const num = 17;
22console.log(isPrime(num)); // 输出: true（17 是素数）

在这个示例中，我们采用了改进的素数判断算法，基于以下观察：

1. 如果一个数可以被另一个数整除，那么它必定不是素数。
2. 一个大于 1 的数，如果它除以 2 或 3 的余数为 0，那么它不是素数。
3. 除了 2 和 3 以外，所有的素数都可以写成 6n ± 1 的形式。

根据以上观察，我们只需要在范围 [5, √n] 内检查 6 的倍数前后的数，就可以判断一个数是否为素数。

幂运算算法

JavaScript 中可以使用内置的指数运算符 ** 或者 Math.pow() 方法进行幂运算。下面是两种方法的示例：

1. 使用指数运算符 **：

1// 使用指数运算符进行幂运算
2function power(base, exponent) {
3    return base ** exponent;
4}
5
6// 示例
7const base = 2;
8const exponent = 3;
9console.log(power(base, exponent)); // 输出: 8（2 的 3 次幂）

2. 使用 Math.pow() 方法：

1// 使用 Math.pow() 方法进行幂运算
2function power(base, exponent) {
3    return Math.pow(base, exponent);
4}
5
6// 示例
7const base = 2;
8const exponent = 3;
9console.log(power(base, exponent)); // 输出: 8（2 的 3 次幂）

这两种方法都可以用于计算幂运算，具体选择哪种方法取决于个人偏好和需求。

排列组合算法

下面是 JavaScript 中计算排列组合的算法实现示例：

 1// 计算阶乘
 2function factorial(n) {
 3    if (n === 0 || n === 1) {
 4        return 1;
 5    }
 6    return n * factorial(n - 1);
 7}
 8
 9// 计算排列数
10function permutation(n, k) {
11    return factorial(n) / factorial(n - k);
12}
13
14// 计算组合数
15function combination(n, k) {
16    return factorial(n) / (factorial(k) * factorial(n - k));
17}
18
19// 示例
20const n = 5;
21const k = 3;
22console.log("排列数:", permutation(n, k)); // 输出: 60
23console.log("组合数:", combination(n, k)); // 输出: 10

在这个示例中，我们分别实现了计算阶乘、排列数和组合数的函数。其中，阶乘函数用于计算阶乘，排列数和组合数分别利用阶乘函数来计算。排列数表示从 n 个元素中选取 k 个元素进行排列的方式的个数，组合数表示从 n 个元素中选取 k 个元素进行组合的方式的个数。

需要注意的是，计算排列数和组合数时，我们都使用了阶乘函数来进行计算。在实际应用中，可以将阶乘函数进行优化，以提高计算效率。

快速幂算法

快速幂算法（Exponentiation by squaring）是一种用于快速计算幂运算的算法，它通过分治法的思想实现了对指数的快速求解，时间复杂度为 O(log n)。

下面是 JavaScript 中的快速幂算法实现示例：

 1// 快速幂算法
 2function power(base, exponent) {
 3    if (exponent === 0) {
 4        return 1;
 5    }
 6    if (exponent % 2 === 0) {
 7        const half = power(base, exponent / 2);
 8        return half * half;
 9    } else {
10        const half = power(base, (exponent - 1) / 2);
11        return half * half * base;
12    }
13}
14
15// 示例
16const base = 2;
17const exponent = 10;
18console.log(power(base, exponent)); // 输出: 1024（2 的 10 次幂）

在这个示例中，我们定义了一个 power 函数来实现快速幂算法。该函数接受两个参数：base 表示底数，exponent 表示指数。算法首先检查指数是否为 0，若为 0 则返回 1。然后，根据指数的奇偶性，使用分治法将指数拆分为两个相等的部分，并递归计算结果。最后，根据指数的奇偶性再次合并结果，得到最终的幂运算结果。

由于快速幂算法采用了分治法的思想，使得指数的计算过程呈现出对数级别的复杂度，因此在计算大指数时具有较高的效率。

牛顿迭代法算法

牛顿迭代法（Newton's method），也称为牛顿-拉弗森方法，是一种用于寻找方程的近似根的迭代算法。它通过从初始猜测值开始，通过迭代逐步逼近方程的根。

假设我们要求解方程 f(x) = 0 的根，其中 f(x) 是一个连续可微的函数。牛顿迭代法的迭代公式如下：

\[x_n+1 = x_n - \frac{f(x_n)}{f'(x_n)} \]

其中，\(x_n + 1\) 是下一个近似根，\(x_n\)是当前的近似根，\(f(x_n)\) 是函数在 \(x_n\) 处的值，\(f'(x_n)\) 是函数在 \(x_n\)处的导数值。

下面是 JavaScript 中的牛顿迭代法实现示例：

 1// 定义函数和它的导数
 2function f(x) {
 3    return x ** 2 - 2; // 求解方程 x^2 - 2 = 0 的根
 4}
 5
 6function df(x) {
 7    return 2 * x; // f(x) 的导数为 2x
 8}
 9
10// 牛顿迭代法
11function newtonMethod(guess, tolerance) {
12    let x = guess;
13    while (Math.abs(f(x)) > tolerance) {
14        x = x - f(x) / df(x);
15    }
16    return x;
17}
18
19// 示例
20const initialGuess = 1.5; // 初始猜测值
21const tolerance = 0.0001; // 容差
22console.log("根的近似值:", newtonMethod(initialGuess, tolerance));

在这个示例中，我们使用牛顿迭代法来求解方程 \(x^2 - 2 = 0\) 的根。我们首先定义了函数\(f(x)\) 和它的导数 \(f'(x)\) ，然后编写了牛顿迭代法的实现函数 newtonMethod。该函数接受两个参数：初始猜测值和容差。在迭代过程中，我们使用给定的初始猜测值开始，并根据迭代公式逐步逼近方程的根，直到满足给定的容差为止。

高斯消元法算法

高斯消元法是一种用于求解线性方程组的方法，它通过矩阵的行变换和消元操作将方程组转化为简化的上三角形式，然后通过回代求解未知数的值。

以下是 JavaScript 中的高斯消元法实现示例：

 1// 解线性方程组的高斯消元法
 2function gaussianElimination(matrix) {
 3    const numRows = matrix.length;
 4    const numCols = matrix[0].length - 1; // 减去最后一列的常数项
 5    for (let pivot = 0; pivot < numCols; pivot++) {
 6        // 找到列主元（pivot）
 7        let maxRowIndex = pivot;
 8        for (let i = pivot + 1; i < numRows; i++) {
 9            if (Math.abs(matrix[i][pivot]) > Math.abs(matrix[maxRowIndex][pivot])) {
10                maxRowIndex = i;
11            }
12        }
13        // 交换当前行和最大值所在的行
14        [matrix[pivot], matrix[maxRowIndex]] = [matrix[maxRowIndex], matrix[pivot]];
15
16        // 消元操作
17        for (let i = pivot + 1; i < numRows; i++) {
18            const factor = matrix[i][pivot] / matrix[pivot][pivot];
19            for (let j = pivot; j <= numCols; j++) {
20                matrix[i][j] -= matrix[pivot][j] * factor;
21            }
22        }
23    }
24
25    // 回代求解未知数
26    const solution = new Array(numCols);
27    for (let i = numCols - 1; i >= 0; i--) {
28        solution[i] = matrix[i][numCols] / matrix[i][i];
29        for (let j = i - 1; j >= 0; j--) {
30            matrix[j][numCols] -= matrix[j][i] * solution[i];
31        }
32    }
33
34    return solution;
35}
36
37// 示例
38const matrix = [
39    [2, 1, -1, 8],
40    [-3, -1, 2, -11],
41    [-2, 1, 2, -3]
42];
43console.log("方程组的解:", gaussianElimination(matrix)); // 输出: [ 2, 3, -1 ]

在这个示例中，我们定义了一个名为 gaussianElimination 的函数来实现高斯消元法。该函数接受一个二维数组 matrix 作为输入，表示一个线性方程组的系数矩阵。算法首先通过行变换找到列主元，并利用消元操作将矩阵转化为上三角形式。然后，通过回代求解未知数的值，并返回方程组的解。

简单线性回归和多项式回归算法

简单线性回归和多项式回归是统计学中常用的线性回归方法，用于建立输入变量与输出变量之间的关系模型。

1. 简单线性回归：简单线性回归适用于只有一个自变量和一个因变量的情况。它假设自变量和因变量之间的关系可以用一条直线来表示。简单线性回归的模型可以表示为：

\[y= mx + b \]

其中，y 是因变量，x 是自变量，m 是直线的斜率，b 是截距。

2. 多项式回归：多项式回归适用于自变量和因变量之间不是线性关系的情况。它通过引入多项式项来建立自变量和因变量之间的关系模型。多项式回归的模型可以表示为：

\[y = β_0,β_1x + β_1x^2 + ... + β_nx^n \]

其中，y 是因变量，x 是自变量，\(β_0$,\)β_1\(,....\)β_n$ 是回归系数，n 是多项式的阶数。

下面是 JavaScript 中简单线性回归和多项式回归的示例实现，我们使用 regression 库来实现这两种回归方法：

 1const regression = require('regression');
 2
 3// 简单线性回归
 4function simpleLinearRegression(data) {
 5    const result = regression.linear(data);
 6    return {
 7        slope: result.equation[0],
 8        intercept: result.equation[1]
 9    };
10}
11
12// 多项式回归
13function polynomialRegression(data, order) {
14    const result = regression.polynomial(data, { order: order });
15    return result.equation;
16}
17
18// 示例
19const data = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]; // 样本数据，格式为 [x, y]
20console.log("简单线性回归结果:", simpleLinearRegression(data)); // 输出简单线性回归的斜率和截距
21console.log("多项式回归结果:", polynomialRegression(data, 2)); // 输出多项式回归的系数

在这个示例中，我们使用了 regression 库来实现简单线性回归和多项式回归。对于简单线性回归，我们使用 regression.linear() 函数；对于多项式回归，我们使用 regression.polynomial() 函数，并指定了多项式的阶数。

蒙特卡洛方法算法

蒙特卡洛方法（Monte Carlo method）是一种基于随机抽样的数值计算方法，通过大量的随机样本来近似求解问题，适用于求解复杂的数学问题、物理问题和工程问题等。

蒙特卡洛方法的基本思想是通过生成大量的随机样本，然后利用这些样本的统计特性来估计问题的解或者概率分布。其优点在于可以处理高维、复杂的问题，且在理论上具有较好的收敛性。

以下是一个简单的蒙特卡洛方法示例，用于估计圆周率的值：

 1// 蒙特卡洛方法估计圆周率
 2function monteCarloPi(numSamples) {
 3    let insideCircle = 0;
 4    for (let i = 0; i < numSamples; i++) {
 5        const x = Math.random(); // 在 [0, 1] 范围内生成随机数
 6        const y = Math.random();
 7        if (x * x + y * y <= 1) { // 判断点是否落在单位圆内
 8            insideCircle++;
 9        }
10    }
11    const ratio = insideCircle / numSamples;
12    return 4 * ratio; // 圆的面积与正方形的面积的比例为 π / 4
13}
14
15// 示例
16const numSamples = 1000000;
17console.log("估计的圆周率值:", monteCarloPi(numSamples));

在这个示例中，我们使用蒙特卡洛方法来估计圆周率的值。算法首先生成指定数量的随机样本，然后统计落在单位圆内的样本数量。最后，通过统计结果得到圆周率的近似值，其中圆的面积与正方形的面积的比例为 π / 4，因此最终的估计值为 4 倍的比例。