js案例100讲解,jsa案例分析 收藏 0

图解实例讲解JavaScript算法，让你彻底搞懂

你好程序员，我们大多数人都害怕算法，并且从未开始学习它。但我们不应该害怕它。算法只是解决问题的步骤。

今天让我们以简单和说明性的方式介绍主要算法。

不要试图记住它们，算法更多的是解决问题。所以，坐下来用纸和笔。目录中的术语可能看起来很吓人，但只要和我在一起，我保证会以尽可能简单的方式解释所有内容。

目 录

• 大 O 表示法
• 理解大 O 符号
• 算法
• 什么是算法，为什么要关心？
• 递归
• 线性搜索算法
• 二进制搜索算法
• 朴素搜索算法
• KMP算法
• 冒泡排序
• 合并排序
• 快速排序
• 基数排序

Big O Notation 是一种表示算法时间和空间复杂度的方法。

• 时间复杂度：算法完成执行所花费的时间。
• 空间复杂度：算法占用的内存。

表示算法时间复杂度的表达式（符号）很少。

• O(1)：常数时间复杂度。这是理想情况。
• O(log n)：对数时间复杂度。如果`log(n) = x`那么它与`10^x`
• O(n)：线性时间复杂度。时间随着输入的数量呈线性增加。例如，如果一个输入需要 1 毫秒，则 4 个输入将花费 4 毫秒来执行算法。
• O(n^2)：二次时间复杂度。这主要发生在嵌套循环的情况下。
• O(n!)：阶乘时间复杂度。这是最坏的情况，应该避免。

您应该尝试编写您的算法，使其可以用前 3 个符号表示。最后两个应尽可能避免。

您希望尽可能地降低复杂性，最好避免超过 O(n) 的复杂性。

在本文的后续部分中，您将看到每种表示法的示例。现在，这就是您需要知道的全部内容。

解决问题的方法，或者我们可以说解决问题的步骤、过程或规则集被称为算法。

例如：用于查找与搜索字符串相关的数据的搜索引擎算法。

作为一名程序员，您会遇到许多需要使用这些算法解决的问题。因此，如果您已经了解它们会更好。

调用自身的函数是递归的。将其视为循环的替代方案。

在上面的代码片段中，请看第 3 行recursiveFn 在 recursiveFn 本身中被调用。正如我之前提到的，递归是循环的替代方法。

那么，这个函数到底要运行多少次呢？

好吧，这将创建一个无限循环，因为在任何时候都无法阻止它。

假设我们只需要运行循环 10 次。在第 11 次迭代函数应该返回。这将停止循环。

在上面的代码片段中，第 4 行返回并在计数为 10 时停止循环。

现在让我们看一个更现实的例子。我们的任务是从给定的数组中返回奇数数组。这可以通过多种方式实现，包括 for-loop、Array.filter 方法等

但是为了展示递归的使用，我将使用 helperRecursive 函数。

这里的递归函数是helperRecursiveFn。

例如：第一次 helperRecursiveFn 将被调用[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。下次它将被调用，[2, 3, 4, 5, 6, 7, 8, 9, 10]依此类推，直到数组长度为 0。

线性搜索算法非常简单。假设您需要查找给定数组中是否存在某个数字。

您将运行一个简单的 for 循环并检查每个元素，直到找到您要查找的元素。

这就是线性搜索算法。您以线性方式逐一搜索数组中的每个元素。

只有一个 for 循环会运行 n 次。其中 n（在最坏的情况下）是给定数组的长度。这里的迭代次数（在最坏的情况下）与输入（长度数组）成正比。

因此，线性搜索算法的时间复杂度是线性时间复杂度：O(n)。

在线性搜索中，您一次可以消除一个元素。但是使用二进制搜索算法，您可以一次消除多个元素。这就是二分查找比线性查找快的原因。

这里要注意的一点是，二分查找只对排序好的数组有效。

该算法遵循分而治之的方法。让我们在 [2, 3, 6, 8, 10, 12] 中找到 8 的索引。

第 1 步：找到数组的中间索引。

第 2 步：检查middleIndex元素是否 > 8。如果是，则说明 8 在middleIndex的左侧。因此，将lastIndex更改为 (middleIndex – 1)。

第 3 步：否则如果 middleIndex元素 < 8。这意味着 8 在middleIndex的右边。因此，将firstIndex更改为 (middleIndex+ 1)；

第 4 步：每次迭代都会根据新的firstIndex或lastIndex 再次设置middleIndex。

让我们以代码格式一起查看所有这些步骤。

这是上述代码的可视化表示。

步骤1

第2步

步骤：3

只有一个 while 循环会运行 n 次。但是这里的迭代次数不依赖于输入（数组长度）。

因此，二进制搜索算法的时间复杂度是对数时间复杂度：O(log n)。你可以检查 O 符号图。O(log n) 比 O(n) 快。

朴素搜索算法用于查找字符串是否包含给定的子字符串。例如，检查“helloworld”是否包含子字符串“owo”。

1. 首先循环主字符串（“helloworld”）。
2. 在子字符串 (\”owo\”) 上运行嵌套循环。
3. 如果字符不匹配，则中断内部循环，否则继续循环。
4. 如果内循环完成并匹配，则返回 true 否则继续外循环。

这是一个视觉表示。

这是代码中的实现。

现在，让我们试着理解上面的代码。

• 在第 2 行，如果 subString长度大于 mainString长度，则返回false。
• 在第 4 行，开始在mainString 上循环。
• 在第 5 行，在subString上开始嵌套循环。
• 在第 6 行，如果没有找到匹配项，则中断内循环，并继续进行外循环的下一次迭代。
• 在第 7 行，在内循环的最后一次迭代中返回true。

朴素搜索的时间复杂度

循环中有循环（嵌套循环）。两个循环都运行 n 次。因此，朴素搜索算法的时间复杂度是 (n * n) Quadratic Time Complexity: O(n^2)。

如上文所述，如果可能，应避免超过 O(n) 的任何时间复杂度。在下一个算法中，我们将看到一种时间复杂度更低的更好方法。

KMP算法是一种模式识别算法，理解起来有点费劲。好的，让我们尝试查找字符串“abcabcabspl”是否包含子字符串“abcabs”。

如果我们尝试使用Naive Search Algo来解决这个问题，它将匹配前 5 个字符但不匹配第 6 个字符。我们将不得不从下一次迭代重新开始，我们将失去上一次迭代的所有进展。

所以，为了保存我们的进度并使用它，我们必须使用一个叫做 LPS 表的东西。现在在我们匹配的字符串“abcab”中，我们将找到最长的相同前缀和后缀。

在这里，在我们的字符串“abcab”中，“ab”是最长的相同前缀和后缀。

现在，我们将从索引 5（对于主字符串）开始下一次搜索迭代。我们从之前的迭代中保存了两个字符。

为了找出前缀、后缀以及从哪里开始下一次迭代，我们使用 LPS 表。

我们的子串（“abcabs”）的 LPS 是“0 0 0 1 2 0”。

下面是如何计算 LPS 表。

下面是使用 LPS 表的代码实现。

只有一个循环运行 n 次。因此，KMP 算法的时间复杂度是线性时间复杂度：O(n)。

请注意，与 Naive 搜索算法相比，时间复杂度是如何提高的。

排序意味着按升序或降序重新排列数据。冒泡排序是众多排序算法中的一种。

在冒泡排序算法中，我们通过将每个数字与前一个数字进行比较，将较大的数字交换到末尾。这是一个视觉表示。

冒泡排序代码实现。

让我们试着理解上面的代码。

• 从带有变量 i 的数组末尾开始循环。
• 以变量 j 开始内循环，直到 (i – 1)。
• 如果 array[j] > array[j + 1] 交换它们。
• 返回排序数组。

有一个嵌套循环，两个循环都运行 n 次，因此该算法的时间复杂度为 (n * n) 即二次时间复杂度 O(n^2)。

合并排序算法遵循分而治之的方法。它是两件事的结合——合并和排序。

在这个算法中，我们首先将主数组分成多个单独的排序数组。

然后我们将单独排序的元素合并到最终数组中。

让我们看看代码中的实现。

合并排序数组

上面的代码将两个排序数组合并为一个新的排序数组。

合并排序算法

上述算法使用递归将数组划分为多个单元素数组。

让我们尝试计算归并排序算法的时间复杂度。因此，以我们之前的示例（[6, 3, 5, 2]）为例，将其划分为多个单元素数组需要 2 个步骤。

现在，如果我们将数组 (8) 的长度加倍，则需要 3 个步骤来划分 – (2^3)。意味着将数组长度加倍并没有使步骤加倍。

因此合并排序算法的时间复杂度是对数时间复杂度 O(log n)。

快速排序是最快的排序算法之一。在快速排序中，我们选择一个称为 pivot 的元素，我们会将所有元素（小于 pivot）移动到 pivot 的左侧。

视觉表示。

我们将对枢轴左侧和右侧的数组重复此过程，直到对数组进行排序。

代码实现：枢轴效用

上面的代码标识了 pivot 的正确位置并返回该位置索引。

上面的代码使用递归将枢轴移动到左右枢轴数组的正确位置。

最佳情况：对数时间复杂度 – O(n log n)

平均情况：对数时间复杂度 – O(n log n)

最坏情况：O(n^2)

基数排序也称为桶排序算法。

这里首先我们构建 10 个索引桶，从 0 到 9。然后我们取每个数字中的最后一个字符，并将该数字推送到相应的桶中。检索新顺序并重复每个数字的倒数第二个字符。

不断重复上述过程，直到数组排序完毕。

在代码中实现。

// Count Digits: 下面的代码计算给定元素的位数。

// 获取数字：下面的代码从右边给出索引 i 处的数字。

// MaxDigit：下面的代码片段找到了最大位数的数字。

// Radix 算法：利用上述所有代码段对数组进行排序。

有一个嵌套的for循环，我们知道嵌套的for循环的时间复杂度是O(n^2)。但是在这种情况下，for 循环都不会运行 n 次。

外循环运行 k (maxDigitCount) 次，内循环运行 m (数组长度) 次。因此，基数排序的时间复杂度为 O(kxm) – （其中 kxm = n）线性时间复杂度 O(n)

算法和计算机原理是如今在企业面试和进入互联网大厂必要的技能，如果你正在学前端，你也可以来咨询我们，我们的JavaScript系统课程中针对算法和基础原理也有详细的视频简介！！

HTML+JavaScript案例分享： 打造经典俄罗斯方块，详解实现全过程

大家好，我是魏大帅，今天教大家一个装[啤酒]的方法。你说你不懂前端，没关系我教你。打开你的电脑，新建一个txt文档，把我文章最后面的完整代码复制到文档里面，然后把txt文档的后缀名改成.html 就ok啦，你可以直接把这个html文件发给你朋友，说这是哥们我做的，[给力]不！

哈哈，前面这段纯属开玩笑的，主要还是给各位前端开发，或者想从事前端开发的帅哥美女们，一个可以借鉴的案例。有大神觉得自己有更厉害的案例，也可以告诉我，我也学习学习，咱们互相学习互相进步。话不多说，上干货！

这是俄罗斯方块的效果图：

我们最先借助 HTML 和 CSS 来打造游戏的界面。这页面主要涵盖了一个游戏区域，也就是 （<canvas>元素），还有一个包含“开始游戏”按钮以及得分展示的区域。

我们先把各种各样可能会出现的方块形状和相对应的颜色给定义好了。

设置了一连串的游戏状态变量，用来追踪游戏板的状况、当下正在下落的方块、所在位置、得分情况，还有游戏是不是结束了之类的信息。

用一个函数来把游戏板初始化，把每个格子都初始化成 0 ，意思就是都为空。

这个函数负责在<canvas>上面画游戏板和当下正在掉落的方块。要是格子里有方块，那就依据方块的颜色把对应的区域填满。

随便挑一个方块的形状和颜色，把它的初始位置定在游戏板中央靠上的地方。

判断一下当前的方块能不能在给定的那个方向上移动，如果移动后的位置超过了游戏板的边界，或者已经有别的方块占着了，那就不能移动。

要是能移动，那就把方块的位置更新一下。

用转换矩阵的办法来让方块旋转。先弄出一个新的形状的数组，然后看看旋转后的形状能不能放在游戏板上，如果能，就把当前的形状更新成旋转后的形状。

判断一下方块是不是该停止往下落了，如果是，那就把方块固定在游戏板上，再检查检查有没有完整的行能消除掉。要是有，就把这些行删掉，得分也增加，然后生成新的方块。要是方块还能往下落，那就接着往下落。

把游戏板的每一行都走一遍，检查检查有没有完整的行。要是有，就把那行删掉，在顶部加上一行空的，同时得分也增加。

检查游戏板的第一行有没有方块，要是有，那游戏就结束啦

游戏循环的那个函数不停地查看方块能不能下落，要是不能下落或者游戏已经结束了，那就调用 fixShape 函数把方块给定住；要是能下落，就让方块接着往下落，并且把游戏板给画出来。

要是点击“开始游戏”这个按钮，就调用这个函数。要是已经有游戏正在进行当中，那就先把旧游戏停下，接着把游戏状态重置了，创建一个新的游戏板，生成新的方块，启动游戏循环，然后把得分显示也更新一下。

咱们监听键盘事件，要是按了左、右、下、上箭头键，那就分别对应着方块的左移、右移、下落和旋转这些操作。要是游戏已经结束了，那就不响应按键事件。

凭借上面这些代码，咱们顺利做成了一个挺简单的俄罗斯方块游戏。

希望这篇文章能对你有所帮助！[赞][比心]

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com