前端基础算法

踏浪

发布于 2019-11-28 18:10:49

4250

发布于 2019-11-28 18:10:49

对于前端初学者而言，这样的一个功能你做出来了那就很好，慢慢的，我们的工作年限越来越长，如果我们还继续那样做，这样，迟早会淘汰。这个时候，就需要对你的项目进行优化。之前讲到过对于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
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-09-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法