前端算法知识脉络(进阶必备知识)

这是我参与8月更文挑战的第18天，活动详情查看：8月更文挑战

前言

所谓“算法”，指的是解题方案的准确而完整的描述。算法的范畴是比较广泛的，它并不仅仅局限与 LeetCode 上面的一问一答。就前端而言，算法的考察整体上三个大的方向：

1. 通用算法能力

2. 关键 API 的实现

3. 框架底层原理所涉及的算法（重在理解）

排序

如何将一个乱序数组变得有序（有序在不经特别说明的情况下，指的都是从小到大排列）？

冒泡排序

冒泡排序的过程，就是循环对比相邻的两个数据项。如果发现第一个比第二个大，则交换两个数据项的位置。较大的数据项不断向上移动到正确的位置，就好像是气泡浮出水面一样，因此这种排序方法被称为“冒泡排序”

function bubbleSort(arr) {
    // 缓存数组长度
    const len = arr.length
    // 外层循环，n个元素就要循环n次，每次确定的是索引为 len-1-i 这个坑位上的正确元素值
    for(let i = 0; i < len; i++) {
        // 内层循环，逐个对比相邻两个数的大小
        for(let j=0; j<len-1-i; j++) {
            // 如果靠前的数字大于靠后的数字，则交换两者的位置
            if(arr[j] > arr[j+1]) { 
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    return arr
}

选择排序

选择排序的思路是：首先定位到数组的最小值，把它放在第一个坑位；接着排查第二个到最后一个元素，找出第二小的值，把它放在第二个坑位；循环这个过程，直至数组的所有坑位被重新填满为止。

function selectSort(arr)  {
    //  缓存数组长度
    const len =  arr.length
    // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
    let  minIndex
    // 遍历数组中的前 n-1  个元素
    for(let i=0; i<len-1; i++)  {
        // 初始化 minIndex  为当前区间第一个元素
        minIndex =  i
        // i、j分别定义当前区间的上下界， i是左边界，j是右边界
        for(let j=i; j< len; j++)  {
            // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为   j
            if(arr[j] < arr[minIndex])  {
                minIndex =  j
            }
        }
        // 如果 minIndex 发生过更新，则将 minIndex  置于当前排序区间的头部
        if(minIndex !== i)  {
            [arr[i], arr[minIndex]] = [arr[minIndex],  arr[i]]
        }
    }
    return  arr
}

插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

一般来说，插入排序都采用 in-place 在数组上实现：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

function insertSort(arr)  {
    //  缓存数组长度
    const len =  arr.length
    // temp  用来保存当前插入的新元素
    let  temp
    // i用于标识每次被插入的元素的索引
    for(let i=1;i<len;i++)  {
        // j用于帮助 temp  寻找自己应该有的定位
        let  j=i
        temp =  arr[i]
        // 判断 j 前面一个元素是否比 temp  大
        while(j>0 && arr[j-1]>temp)  {
            // 如果是，则将 j 前面的一个元素后移一位，为  temp  让出位置
            arr[j] =  arr[j-1]
            j--
        }
        // 循环让位，最后得到的 j 就是 temp  的正确索引
        arr[j] =  temp
    }
    return  arr
}

以上三种排序算法，相对来说思路都比较简单，对应的整体时间复杂度也比较高（O(n^2）。让我们看一种性能更好，也更常用的排序算法——快速排序。

快速排序的核心思想是“分而治之”，具体操作办法是把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

动态规划

我们现在可以回味一下快速排序的过程，它是“分治”思想的典型应用：把一个问题分解为相互独立的子问题，逐个解决子问题后，再给组合子问题的答案，就得到了问题的最终解。

动态规划的思想和“分治”有点相似。不同之处在于，“分治”思想中，各个子问题之间是独立的：子数组之间的排序并不互相影响。而动态规划划分出的子问题，往往是相互影响的。

来看一个非常经典的动态规划的题目，

我们可以用 f(n) 表示爬到第 n 层楼梯的方法数，那么爬到第 n-1 层楼梯的方法数对应的表示就是 f(n-1)，爬到第 n-2 层楼梯的方法数对应的表示就是 f(n-2)。f(n)、f(n-1) 和 f(n-2) 之间有着如下的关系：

f(n) = f(n-1) +  f(n-2)

如果我此刻就站在第 n 层楼梯上，我要往后退，有几种退法？

按照题目的要求，我每次只能后退一步或者两步。假如我后退一步，那么就来到了第 n-1 层楼梯；假如我后退了两步，那么就来到了第 n-2 层楼梯。这就意味着，如果我要抵达第 n 层楼梯，那么我只有两个可能的来路：

• 从第 n-1 层楼梯爬一步上来

• 从第 n-2 层楼梯爬两步上来

因此，爬到第 n 层楼梯的办法数，就是 f(n-1) 和 f(n-2) 相加的结果。

因此这道题的解法就是将 f(n) 转化为 f(n-1) + f(n-2)  两个子问题，然后再对子问题进行拆解：比如将 f(n-1) 转化为f(n-1 -1) + f(n-1 -2)。这样依次递归，直到 n=1 或者 n=2 为止——这两种情况是特殊的，分别只有一种抵达方法。

function climbStairs(n) {
    //使用裴波那契法（可以使用递归，但是可能超时）
    if(n === 1 || n === 2){
        return n;
    }
    let result;  //用来保存结果
    let preTwo = 1;  //需要记忆两个数
    let preOne = 2;
    for(let i = 3; i < n + 1; i++){
        result = preOne + preTwo;
        preTwo = preOne;
        preOne = result;
    }
    return result;
}