带有可视化示例的 JavaScript 算法。

各位程序员大家好，

我们大多数人害怕算法，甚至从未开始学习它。但我们不应该害怕它。算法只是解决问题的步骤。

今天，让我们以简单、直观的方式介绍主要算法。

别试图死记硬背，算法更多的是解决问题。所以，准备好纸和笔。

目录中的术语可能看起来非常可怕，但请听我说，我保证以最简单的方式解释一切。

理解大 O 符号

大 O 符号是一种表示算法的时间和空间复杂度的方法。

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

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

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

你应该尝试用前三种符号来表示你的算法。后两种符号应尽量避免使用。

您希望保持复杂性尽可能低且直接，理想情况下避免任何高于 O(n) 的情况。

在本文的后续章节中，您将看到每种符号的示例。目前，您需要了解的就这些。

算法

什么是算法以及为什么要关心？

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

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

作为一名程序员，你会遇到许多需要用这些算法来解决的问题。所以，如果你已经了解这些算法就更好了。

递归

函数调用自身就是递归。可以把它看作是循环的另一种形式。

function recursiveFn() {
    console.log("This is a recursive function");
    recursiveFn();
}

recursiveFn();

在上面的代码片段中，第 3 行 recursiveFn 被 recursiveFn 本身调用。正如我之前提到的，递归是循环的另一种选择。

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

嗯，这将创建一个无限循环，因为在任何时候都没有什么可以阻止它。

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

let count = 1;
function recursiveFn() {
    console.log(`Recursive ${count}`);
    if (count === 10) return;
    count++;
    recursiveFn();
}

recursiveFn();

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

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

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

function oddArray(arr) {
    let result = [];
    function helperRecursiveFn(arr) {
        if(arr.length === 0) {
            return; // 1
        } else if(arr[0] % 2 !== 0) {
            result.push(arr[0]); // 2
        }
        helperRecursiveFn(arr.slice(1)); // 3
    }
    helperRecursiveFn(arr);
    return result;
}

oddArray([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
// OutPut -> [1, 3, 5, 7, 9]

这里的递归函数是helperRecursiveFn。

如果数组长度为 0，则返回。
如果元素为奇数，则将元素推送到结果数组。
调用 helperRecursiveFn 函数，将数组的第一个元素切片。每次切片时，数组的第一个元素都会被切片，因为我们已经检查过它是奇数还是偶数。

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

线性搜索算法

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

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

const array = [3, 8, 12, 6, 10, 2];

// Find 10 in the given array.
function checkForN(arr, n) {
    for(let i = 0; i < array.length; i++) {
        if (n === array[i]) {
            return `${true} ${n} exists at index ${i}`;
        }
    }

  return `${false} ${n} does not exist in the given array.`;
}

checkForN(array, 10);

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

线性搜索算法的时间复杂度

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

因此线性搜索算法的时间复杂度是线性时间复杂度：O（n）。

二分搜索算法

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

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

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

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

const array = [2, 3, 6, 8, 10, 12];
let firstIndex = 0;
let lastIndex = array.length - 1;
let middleIndex = Math.floor((firstIndex + lastIndex) / 2); // middleIndex -> 2

步骤 2：
检查 middleIndex 元素是否大于 8。如果是，则表示 8 位于 middleIndex 的左侧。因此，将 lastIndex 更改为 (middleIndex - 1)。

步骤3：
否则，如果 middleIndex 元素 < 8，即 8 位于 middleIndex 的右侧。因此，将 firstIndex 更改为 (middleIndex + 1)；

if (array[middleIndex] > 8) {
    lastIndex = middleIndex - 1;
} else {
    firstIndex = middleIndex + 1;
}

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

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

function binarySearch(array, element) {
    let firstIndex = 0;
    let lastIndex = array.length - 1;
    let middleIndex = Math.floor((firstIndex + lastIndex) / 2);

    while (array[middleIndex] !== element && firstIndex <= lastIndex) {
        if(array[middleIndex] > element) {
                lastIndex = middleIndex - 1;
        }else {
                firstIndex = middleIndex + 1;
        }
        middleIndex = Math.floor((firstIndex + lastIndex) / 2);
    }
    return array[middleIndex] === element ? middleIndex : -1;
}

const array = [2, 3, 6, 8, 10, 12];
binarySearch(array, 8); // OutPut -> 3

这是上述代码的直观表示。

步骤：1

firstIndex = middleIndex + 1;

步骤：2

lastIndex = middleIndex - 1;

步骤：3

array[middleIndex] === 8 // Found It

二分查找的时间复杂度

只有一个 while 循环，它将运行 n 次。但这里的迭代次数与输入（数组长度）无关。

因此，二分查找算法的时间复杂度是对数时间复杂度：O(log n)。你可以查看 O 符号图。O(log n) 比 O(n) 更快。

朴素搜索算法

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

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

这是一个直观的表示。

以下是代码的实现。

function naiveSearch(mainStr, subStr) {
    if (subStr.length > mainStr.length) return false;

    for(let i = 0; i < mainStr.length; i++) {
       for(let j = 0; j < subStr.length; j++) {
            if(mainStr[i + j] !== subStr[j]) break;
            if(j === subStr.length - 1) return true; 
        }
    }
    return false;
}

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

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

朴素搜索的时间复杂度

循环内套循环（嵌套循环）。两个循环都运行 n 次。因此，朴素搜索算法的时间复杂度为 (n * n)，二次时间复杂度为 O(n^2)。

正如上文所讨论的，任何时间复杂度高于 O(n) 的算法都应该尽可能避免。我们将在下一个算法中看到一种时间复杂度更低的更好方法。

KMP算法

KMP 算法是一种模式识别算法，理解起来有点困难。好吧，我们来试试判断字符串“abcabcabspl”是否包含子字符串“abcabs”。

如果我们尝试使用朴素搜索算法来解决这个问题，它会匹配前 5 个字符，但不会匹配第 6 个字符。我们将不得不在下一次迭代中重新开始，并且会丢失上一次迭代中的所有进展。

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

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

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

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

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

以下是计算 LPS 表的方法。

function calculateLpsTable(subStr) {
    let i = 1;
    let j = 0;
    let lps = new Array(subStr.length).fill(0);

    while(i < subStr.length) {
        if(subStr[i] === subStr[j]) {
            lps[i] = j + 1;
            i += 1;
            j += 1;
        } else {
            if(j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }
    return lps;
}

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

function searchSubString(string, subString) {
    let strLength = string.length;
    let subStrLength = subString.length;
    const lps = calculateLpsTable(subString);

    let i = 0;
    let j = 0;

    while(i < strLength) {
        if (string[i] === subString[j]) {
            i += 1;
            j += 1;
        } else {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
        if (j === subStrLength) return true;
    }

    return false;
}

KMP算法的时间复杂度

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

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

冒泡排序算法

排序是指按升序或降序重新排列数据。冒泡排序是众多排序算法之一。

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

冒泡排序代码实现。

function bubbleSort(array) {
    let isSwapped;

    for(let i = array.length; i > 0; i--) {
        isSwapped = false;

        for(let j = 0; j < i - 1; j++) {
            if(array[j] > array[j + 1]) {
                [array[j], array[j+1]] = [array[j+1], array[j]];
                isSwapped = true;
            }
        }

        if(!isSwapped) {
            break;
        }
    }
    return array;
}

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

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

冒泡排序算法的时间复杂度

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

合并排序算法

归并排序算法遵循分而治之的原则。它是合并和排序的结合。

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

然后我们将各个排序好的元素合并到最终的数组中。

我们来看一下代码中的实现。

合并排序数组

function mergeSortedArray(array1, array2) {
    let result = [];
    let i = 0;
    let j = 0;

    while(i < array1.length && j < array2.length) {
        if(array1[i] < array2[j]) {
            result.push(array1[i]);
            i++;
        } else {
            result.push(array2[j]);
            j++;
        }
    }

    while (i < array1.length) {
        result.push(array1[i]);
        i++;
    }

    while (j < array2.length) {
        result.push(array2[j]);
        j++;
    }

    return result;
}

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

合并排序算法

function mergeSortedAlgo(array) {
    if(array.length <= 1) return array;

    let midPoint = Math.floor(array.length / 2);
    let leftArray = mergeSortedAlgo(array.slice(0, midPoint));
    let rightArray = mergeSortedAlgo(array.slice(midPoint));

    return mergeSortedArray(leftArray, rightArray);
}

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

归并排序算法的时间复杂度

让我们尝试计算一下归并排序算法的时间复杂度。以之前的例子 ([6, 3, 5, 2]) 为例，将其拆分成多个单元素数组需要 2 步。

**

It took 2 steps to divide an array of length 4 - (2^2)

**。

现在，如果我们将数组的长度加倍（8），则需要 3 步才能除以 - (2^3)。这意味着数组长度加倍并没有使步骤加倍。

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

快速排序算法

快速排序是最快的排序算法之一。在快速排序中，我们选择一个元素作为基准，并将所有小于基准的元素移动到基准的左侧。

视觉表现。

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

代码实现

枢轴实用程序

function pivotUtility(array, start=0, end=array.length - 1) {
    let pivotIndex = start;
    let pivot = array[start];

    for(let i = start + 1; i < array.length; i++) {
        if(pivot > array[i]) {
            pivotIndex++;
            [array[pivotIndex], array[i]] = [array[i], array[pivotIndex]];
        }   
    }

    [array[pivotIndex], array[start]] = [array[start], array[pivotIndex]];
    return pivotIndex;
}

上述代码识别了枢轴的正确位置并返回该位置索引。

function quickSort(array, left=0, right=array.length-1) {
    if (left < right) {
        let pivotIndex = pivotUtility(array, left, right);
        quickSort(array, left, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, right);
    }

    return array;
}

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

快速排序算法的时间复杂度

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

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

最坏情况：O(n^2)

基数排序算法

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

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

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

代码实现。

// 计数位数：下面的代码计算给定元素的位数。

function countDigits(number) {
    if(number === 0) return 1;

    return Math.floor(Math.log10(Math.abs(number))) + 1;
}

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

function getDigit(number, index) {
    const stringNumber = Math.abs(number).toString();
    const currentIndex = stringNumber.length - 1 - index;

    return stringNumber[currentIndex] ? parseInt(stringNumber[currentIndex]) : 0;
}

// MaxDigit：下面的代码片段查找具有最大位数的数字。

function maxDigit(array) {
    let maxNumber = 0;

    for(let i = 0; i < array.length; i++) {
        maxNumber = Math.max(maxNumber, countDigits(array[i]));
    }

    return maxNumber;
}

// Radix Algo：利用以上所有代码片段对数组进行排序。

function radixSort(array) {
    let maxDigitCount = maxDigits(array);

    for(let i = 0; i < maxDigitCount; i++) {
        let digitBucket = Array.from({length: 10}, () => []);

        for(let j = 0; j < array.length; j++) {
            let lastDigit = getDigit(array[j], i);
            digitBucket[lastDigit].push(array[j]);
        }

        array = [].concat(...digitBucket);
    }

    return array;
}

基数排序算法的时间复杂度

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

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

好了，这篇文章到此结束。如果有些算法没有立即生效，可以多看几遍。

我就是这样理解他们的。

此外，我每周都会发布一份新闻简报，分享关于 Web 开发和编程的精彩内容。订阅它，提升你的技能。

谢谢阅读。

文章来源：https://dev.to/swastikyadav/algorithms-in-javascript-with-visual-examples-gh3

带有可视化示例的 JavaScript 算法。

带有可视化示例的 JavaScript 算法。

目录：

算法

线性搜索算法的时间复杂度

二分查找的时间复杂度

朴素搜索的时间复杂度

KMP算法的时间复杂度

冒泡排序算法的时间复杂度

归并排序算法的时间复杂度

快速排序算法的时间复杂度

基数排序算法的时间复杂度