前言

面试准备中需要手写的代码

promise

class MyPromise {
  constructor(fn) {
    this.callbacks = [];
    this.state = "PENDING";
    this.value = null;

    fn(this._resolve.bind(this), this._reject.bind(this));
  }

  then(onFulfilled, onRejected) {
    return new MyPromise((resolve, reject) =>
      this._handle({
        onFulfilled: onFulfilled || null,
        onRejected: onRejected || null,
        resolve,
        reject,
      })
    );
  }

  catch(onRejected) {
    return this.then(null, onRejected);
  }

  _handle(callback) {
    if (this.state === "PENDING") {
      this.callbacks.push(callback);

      return;
    }

    let cb =
      this.state === "FULFILLED" ? callback.onFulfilled : callback.onRejected;
    if (!cb) {
      cb = this.state === "FULFILLED" ? callback.resolve : callback.reject;
      cb(this.value);

      return;
    }

    let ret;

    try {
      ret = cb(this.value);
      cb = this.state === "FULFILLED" ? callback.resolve : callback.reject;
    } catch (error) {
      ret = error;
      cb = callback.reject;
    } finally {
      cb(ret);
    }
  }

  _resolve(value) {
    if (value && (typeof value === "object" || typeof value === "function")) {
      let then = value.then;

      if (typeof then === "function") {
        then.call(value, this._resolve.bind(this), this._reject.bind(this));
        return;
      }
    }

    this.state === "FULFILLED";
    this.value = value;
    this.callbacks.forEach((fn) => this._handle(fn));
  }

  _reject(error) {
    this.state === "REJECTED";
    this.value = error;
    this.callbacks.forEach((fn) => this._handle(fn));
  }
}

const p1 = new Promise(function (resolve, reject) {
  setTimeout(() => reject(new Error("fail")), 3000);
});

const p2 = new Promise(function (resolve, reject) {
  setTimeout(() => resolve(p1), 1000);
});

p2.then((result) => console.log(result)).catch((error) => console.log(error));

浅克隆

function shallowClone(obj) {
  let cloneObj = {};
  for (let i in obj) {
    cloneObj[i] = obj[i];
  }
  return cloneObj;
}

深克隆

• 考虑基础类型
• 引用类型
  • RegExp、Date、函数 不是 JSON 安全的
  • 会丢失 constructor，所有的构造函数都指向 Object
  • 破解循环引用

function deepCopy(obj) {
  let result = Object.create(null)
  if (typeof obj === 'object') {
    result = obj.constructor === Array ? [] : {};
    for (var i in obj) {
      result[i] = typeof obj[i] === 'object' ? deepCopy(obj[i]) : obj[i];
    }
  } else {
    result = obj;
  }
  return result;
}

curry

function createCurry(func, beforeRoundArg = []) {
  return function () {
    let args = [...beforeRoundArg, ...arguments]
    if (args.length < func.length) {
      return createCurry.call(this, func, args);
    }
    return func.apply(this, args);
  }
}

四种排序

选择排序

平均时间复杂度O（n2）

空间复杂度O（1）（用于交换时作为临时变量）

算法描述：

第一次遍历所有的元素，找出最小的那个放在一号位上

第二次遍历n-1次，找出剩余元素中最小的那个放在二号位上

以此类推。。。。。。

function selectSort(arr){
    if(!Array.isArray(arr)) return;
    //临时变量
    let temp;
    for(let i=0, len=arr.length; i<len-1; i++){
        for(let j=i+1; j<len; j++){
            if(arr[i]>arr[j]){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

冒泡排序：

平均时间复杂度O（n2）

空间复杂度O（1）（用于交换时作为临时变量）

算法描述：

选择相邻的两个数两两进行比较，小的那个数一直往前冒，这样就可以在第一轮找到最小的那个数

接着在剩下的数中重复上述操作。。。。。。

function bubbleSort(arr){
    if(Object.prototype.toString.call(arr).slice(8,-1) != "Array") return;
    // 临时变量
    let temp;
    for(let i=0, len=arr.length; i<len-2; i++){
        for(let j=len-1; j>i; j--){
            if(arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp; 
            }
        }
    }
    return arr;
}

快速排序

平均时间复杂度：O(n*logn2n)

空间复杂度：O(log2n)~O(n)

算法描述：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

start和end分别指向数组的第一个元素后最后一个元素

首先让数组的第一个元素作为基准数，这样一号位就空出来了，首先从后往前找一个小于基准数的元素，然后填入一号为

接着从前往后找一个大于基准数的元素填入刚才填入一号位的那个元素的位置

以此类推直到start等于end为止，最后把基准数存入数组的start或者end位置

第一轮过后比第一个数大的元素都在他的右边比他小的都在左边，接着就是分别对所有的数组进行递归操作

 function quickSort(arr, start, end) {
        if(start >= end) return;
        let i = start, j = end, k = arr[start];
        while (i < j) {
            //从后往前找
            while (i < j && k < arr[j]) {
                j--;
            }
            //排除i==j跳出循环的情况
            if (i<j) {
                arr[i++] = arr[j];
            }
            // 从前往后找
           while(i<j && k >=arr[i]){
               i++;
           }
           //排除i==j跳出循环的情况
           if(i < j){
               arr[j--] = arr[i]; 
           }
        }
        arr[i] = k;
        quickSort(arr, start, i-1);
        quickSort(arr, i+1, end);
        return arr;
    }

插入排序

平均时间复杂度：O(n2)

空间复杂度：O(n2)

算法描述：

插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。

例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；

第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；

第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中

......

第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

  function insertSort(arr){
        //从一号位开始执行插入排序，因为0号位元素可以直接当成有序数
        for(let i=1,len=arr.length; i<len; i++){
            // 用于遍历已经有序的数组
            let j=0;
            while(j<i && arr[j] < arr[i]){
                    j++;
            }
            //排除j==i跳出循环的情况
            if(j<i){
                //插入a[i]
                arr.splice(j,0,arr[i]);
                //删除a[i],注意插入arr[i]后数组多了一个元素
                arr.splice(i+1,1);
            }
        }
        return arr;
    }

二分查找

思想是找到中间值下标，如果输入值未中间值则输出中间值索引，如果输入值小于中间值则将当前中间值变为末尾下标继续二分查找，如果输入值大于中间值则将当前中间值变为初始下标继续二分查找。可以循环，可以递归。

//循环
function binarySearch(arr, sel) {
  //首先确定首、尾下标
  var low = 0;
  var high = arr.length - 1;
  while (low <= high) { //只要查找区间起始点和结束点中间还有值(要包括两值相同的情况)，我们就继续进行查找
    var mid = (low + high) / 2; //确定中间值下标
    if (sel == arr[mid]) { //如果查找值等于中间值
      return mid  //则这个mid值，就是查找到的数组下标
    } else if (sel < arr[mid]) { //如果查找值小于中间值
      high = mid - 1; //则在左半部分查找，需要重新确认区间high的位置
    } else { //否则查找值大于中间值
      low = mid + 1 //则在右半部分查找，需要重新确认区间low的位置
    }
  }
  return -1//查找完都没有查找到，就退出
}
var arr = [1, 3, 5, 6, 7, 8, 9];
var sel = 7;
var index = binarySearch(arr, sel)
console.log("查找下标为：" + index)

//递归
function binary_search2(arr, low, high, key) {
	if(low > high) {
		return -1;
	}
	var mid = parseInt((high + low) / 2);
	if(arr[mid] == key) {
		return mid;
	} else if(arr[mid] > key) {
		high =mid -1;
		return binary_search2(arr, low, high, key);
	} else if(arr[mid] < key) {
		low = mid +1;
		return binary_search2(arr, low, high, key);
	}
}

节流

节流的意思是让函数有节制地执行，而不是毫无节制的触发一次就执行一次。什么叫有节制呢？就是在一段时间内，只执行一次。

规定在一个单位时间内，只能触发一次函数。如果这个单位时间内触发多次函数，只有一次生效。

function throttle(fn, delay) {
  let flag = true
  let timer = null
  return function (...args) {
    if (!flag) return
    flag = false
    clearTimeout(timer)
    timer = setTimeout(() => {
      fn.apply(this, args)
      flag = true
    }, delay)
  }
}

防抖

在事件被触发n秒后再执行回调，如果在这n秒内又被触发，则重新计时。

function debounce(fn, delay) {
  let timer = null
  return function (...args) {
    if (timer) clearTimeout(timer)
    timer = setTimeout(() => {
      fn.apply(this, args)
    }, delay);
  }
}

call

Function.prototype.myCall = function (obj, ...args) {
  if (obj == undefined || obj == null) {
    obj = globalThis
  }
  obj.fn = this
  let res = obj.fn(...args)
  delete obj.fn
  return res
}

apply

Function.prototype.myAplly = function (obj, arr) {
  if (obj == undefined || obj == null) {
    obj = globalThis
  }
  obj.fn = this
  let res = obj.fn(...arr)
  delete obj.fn
  return res
}

bind

Function.prototype.myBind = function (obj, ...args) {
  let that = this
  let fn = function () {
    if (this instanceof fn) {
      return new that(...args)
    } else {
      return that.call(obj, ...args)
    }
  }
  return fn
}

new

function newInstance (Fn, ...args) {
  const obj = {}
  obj.__proto__ = Fn.prototype
  const result = Fn.call(obj, ...args)
  // 如果Fn返回的是一个对象类型, 那返回的就不再是obj, 而是Fn返回的对象否则返回obj
  return result instanceof Object ? result : obj
}

eventBus实现

 class Bus {
  constructor() {
    this.callbacks = {}
  }
  $on(name, fn) {
    this.callbacks[name] = this.callbacks[name] || []
    this.callbacks[name].push(fn)
  }
  $emit(name, args) {
    if (this.callbacks[name]) {
      //存在遍历所有callback
      this.callbacks[name].forEach(cb => cb(args))
    }
  }
  $off(name) {
    if (this.callbacks[name]) {
      delete (this.callbacks[name])
    }
  }
  $once(name, fn) {
    const fns = (args) => {
      fn(args)
      this.$off(name)
    }
    this.$on(name, fns)
  }
}