前端基礎演算法

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  }