Js常用的算法教程 深度广度、冒泡选择、防抖、节流、二分查找

如果觉得还有点用，请您给我一个赞！您的赞是我坚持下去的动力！

深度遍历

拿DOM作为遍历对象，实现2种遍历方法案例

/**
原理：节点的子节点先遍历，再遍历同级节点
node:一个节点
fn:每个节点需要执行的操作
**/
async deep(node,fn){
  await fn(node);
  if(node.children){
    for(let i=0;i<node.children.length;i++){
      await this.deep(node.children[i],fn);
    }
  }
}

广度遍历

/**
原理：节点的同级节点先遍历，再遍历子节点
node:一个节点
fn:每个节点需要执行的操作
**/
async wide(node,fn){
  let queue = [];
  queue.push(node);
  while (queue.length != 0) {
    let item = queue.shift();
    await fn(item);
    for (let j = 0; j < item.children.length; j++) {
      queue.push(item.children[j])
    }
  }
}

防抖

• 原理：函数在调用倒计时n时间内没有重复调用，则执行函数，不然重新倒计时
• 应用场景：常用在鼠标滚动等一些超高频操作下需要执行函数刷新时

function run(fn,ms){
  let tm=null;
  return function(){
    clearTimeout(tm);
    tm=setTimeout(()=>{
      fn.apply(this, arguments);
    },ms)
  }
}

节流

• 原理：当函数未执行完前重复调用将无效
• 应用场景：常用在定时刷新

function run(fn,ms){
  let canrun=true;
  return function(){
    if(!canrun)return;
    canrun=false;
    tm=setTimeout(()=>{
      fn.apply(this, arguments);
      canrun=true;
    },ms)
  }
}

优化版冒泡排序

/**
 特点:优化后遍历次数可以较小，基本满足前端常见排序要求了
 **/
function bubbleSort(arr) {
  let len = arr.length;
  let k = len - 1;
  let isSwap = false;//是否交换标记
  let pos = 0;//最后一次交换位置
  let temp = null;
  for (let i = 0; i < len; i++) {
    isSwap = false;
    pos = 0;
    for (let j = 0; j < k; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        pos = j;
        isSwap = true;
      }
    }
    if (!isSwap) { return arr; }
    k = pos;
  }
  return arr;
}

选择排序

/**
特点：最大数据交换次数是固定的数组长度相等，遍历次数永远固定
 **/
function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {   //寻找最小的数
        minIndex = j;         //将最小数的索引保存
      }
    }
    if(i!=minIndex){
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

快速排序

function quickSort(arr){  
  if (arr.length <= 1) {  
    return arr;  
  }  

  //取出数组中间的一位作为比较对象 如 [5,0,6,3,8] 则取出6，数组变为[5,0,3,8]
  var povitIndex = arr.length>>>1;  
  var povit = arr.splice(povitIndex, 1)[0];  

  //接下来就是遍历[5,0,3,8]将比6小的数放入到leftArr,相反放入rightArr
  var leftArr = [], rightArr = [];  
  for (var i = arr.length - 1; i >= 0; i--) {  
    if (arr[i] < povit) {  
        leftArr.push(arr[i]);  
    } else {  
        rightArr.push(arr[i]);  
    }  
  }  
  //遍历下来后生成了 leftArr[5,0,3],rightArr[8]

  //接下来递归调用，继续将leftArr和rightArr这2个数组重复以上的操作
  //最终将leftArr+povit+rightArr 合并为一个数组即得最终排序后结果
  return quickSort(leftArr).concat([povit], quickSort(rightArr));  
}  

二分查找 - 适用于对排序后的数组,时间复杂度O(logn)

/**
* arr:[1,2,3,4]排序后的数组
* target:目标寻找的值
* type:left|right|''  查询方式，left:查询最左值，right:查询最右值
*/
function bsearch(arr, target, type){
    let begin = 0;
    let end = arr.length;
    let idx =-1;
    
    while(begin < end ) {
        let mid = (begin + end) >>> 1;
        if(arr[mid] == target) {
            if(type === 'right'){
                begin =  mid+1;
            }
            else if(type === 'left'){
                end =  mid;
            }else{
                return mid;
            }
            
        }
        else if(arr[mid] > target) {
            end = mid;
        }
        else if(arr[mid] < target) {
            begin = mid + 1; 
        }
    }
    
    if(type === 'right'){
        idx = arr[begin-1]===target?begin-1:-1;
    }
    else if(type === 'left'){
        idx =  arr[begin]===target?begin:-1;
    }
    console.log(`${idx}位`)
    return idx;
    
}
bsearch([1,4,5,7,11],5); //2
bsearch([1,3,3,3,5],3,'left')；//1
bsearch([1,3,3,3,5],3,'right'); //3