前端基础算法

2019 年 11 月 28 日
筆記

对于前端初学者而言，这样的一个功能你做出来了那就很好，慢慢的，我们的工作年限越来越长，如果我们还继续那样做，这样，迟早会淘汰。这个时候，就需要对你的项目进行优化。之前讲到过对于react项目的优化。这更多是针对于单页应用的优化，避免首页时间加载过长，打包文件加载过大，是针对于打包后文件来说的。这篇文章主要是针对于算法相关的代码进行优化，从而是程序的运行速度更快，已达到程序的优化。

算法更多的是针对于数据的增删改查，或许你认为前端涉及不到，如果这样想，那你就错了。前端可能用的不多，但不会涉及不到，同时，了解算法，那么对于以后的职业道路也会有所帮助。

二分查找法

二分查找在进行查找有序数组中某一项数据的时候非常有用，可以加快程序的运行速度，尤其是在具有大量数据的时候。

二分查找的原理是从数组的中间开始查找，如果被查找对象刚好就是中间这一项，那直接退出查找。如果被查找对象大于中间，那么所需要的对象是在中间-最后这一区间，所以有针对于这一区间再次进行二分。如此下去，找到所需要的即可。

/**   * 二分查找   * @param {Array} list  待查找的有序数组   * @param {Number} item 待查找的数据   */  function binarySearch(list, item){      // 如果list不是数组返回list      if (!Array.isArray(list)) return list      // 定义查找的起始位置      let low = 0;      let high = list.length - 1;        while (low <= high) {          // 定义中间的位置          let mid = Math.floor((low + high) / 2)          let midValue = list[mid]            if ( midValue == item ) return mid            if (midValue < item){              low = mid + 1          }            if (midValue > item){              high = mid - 1          }      }        return -1  }

最后来看看一个具体的效果

const arr = []  for (let i = 0; i < 10000; i++) {      arr.push(i)  }  const need = 6734  let res;    console.time("for")  for (let i = 0; i < arr.length; i++) {    const ele = arr[i];    if( ele === need ) {      res = i      break    }  }  console.log(res);  console.timeEnd("for")    console.time("binarySearch")  res = binarySearch(arr, need)  console.log(res)  console.timeEnd("binarySearch")

可以看到很明显二分查找比普通的循环遍历快了许多。

可视化链接

https://algorithm-visualizer.org/branch-and-bound/binary-search

时间复杂度 O(log n)

选择排序

上面讲到的二分查找虽然性能很好，当时有一个必要的条件就是这个list需要是一个有序数组，否则使用二分查找则是不成立的。所以，对于一个无序的数组，我们首先就是需要把它重新排序。选择排序就是其中一种。

选择排序的原理是从数组中选出一个最大（小）的数，放在另一个数组的开始，然后从剩余数组中继续选择最大（小）的数进行操作，如此重复，直到数组重组。

// 选择排序  function selectSort(list){    if (!Array.isArray(list)) return list      // 定义一个数组存放排序后的数组    const arr = [];      for (let i = list.length - 1; i >= 0; i--) {      const smallestIndex = findSmallest(list)      arr.push(list.splice(smallestIndex, 1)[0])    }      return arr  }    // 寻找最小的数  function findSmallest(list){    let smallest = list[0]    let smallestIndex = 0      for (let i = 0; i < list.length; i++) {      const ele = list[i];      if (ele < smallest) {        smallest = ele        smallestIndex = i      }    }    return smallestIndex  }