《前端算法系列》如何让前端代码速度提高60倍

今天的问题从排序算法入手，来讲解如何根据业务需求，结合金典的算法，来实现js高性能开发。

情景

老板让小明给公司的20000+条数据排个序，但是由于排序的操作会频繁发生，如果操作执行的时间很慢，则会严重降低用户体验，听到这条噩耗后小明开始了代码。

1.毫无违和感的排序算法 小明根据需求，思考了一会，写下了如下算法：

/** * max排序 * @param {*} arr  * 耗时：760ms */ function maxSort(arr) {     let result = [...arr];     for(let i=0,len=result.length; i< len; i++) {        let minV = Math.min(...result.slice(i))        let pos = result.indexOf(minV,i)        result.splice(pos, 1)        result.unshift(minV)     }     return result.reverse() }

自信的小明陶醉在自己的算法中，准备测试一下性能，

/* * @Author: Mr Jiang.Xu  * @Date: 2019-06-11 10:25:23  * @Last Modified by: Mr Jiang.Xu * @Last Modified time: 2019-06-13 21:03:59 * @desc 测试函数执行的时间 */const testArr = require("./testArr");module.exports = async function getFnRunTime(fn) {    let len = testArr.length;    let startTime = Date.now(), endTime;    let result = await fn(testArr);    endTime = Date.now();    console.log(result);    console.log(`total time:${endTime-startTime}ms`,                "test array\"length:" + len,                 result.length    );}

运行该测试函数后，耗时760ms，小明觉得还不错，放到项目中后，第一次操作还好，连续操作了几次后，页面明显卡顿。。。（求此时小明心里的阴影面积）

小明不甘心，在网上查找相关资料后，写下了如下冒泡排序代码：

/**  * 置换函数  * @param {源数组} arr   * @param {原数组的A项} indexA   * @param {原数组的B项} indexB   */ function swap(arr, indexA, indexB) {    [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]]; }/** * 原始冒泡排序 * @param {数组} arr  * 耗时：377ms */ function bubbleSort1(arr) {    for (let i = arr.length - 1; i > 0; i--) {      for (let j = 0; j < i; j++) {        if (arr[j] > arr[j + 1]) {          swap(arr, j, j + 1);        }      }    }      return arr;  }

测试后耗时377ms，完美，小明放到项目中测试，频繁排序还是会有点卡顿，能不能再优化一下呢？思考许久之后，小明完善了冒泡排序：

/** * 利用索引优化后的冒泡排序 * @param {数组} arr  * 耗时：350ms */ function bubbleSort2(arr) {    let i = arr.length - 1;    while (i > 0) {        let pos = 0;        for (let j = 0; j < i; j++) {        if (arr[j] > arr[j + 1]) {            pos = j;            swap(arr, j, j + 1);        }        }        i = pos;    }    return arr;}

根据缓存索引位置来提高排序性能，时间节约了20ms，但收益很小。小明开始和自己过不去了，在维基百科上继续查找，最后发现了一个方法：

/** * 在每趟排序中进行正向和反向两遍冒泡 , * 一次可以得到两个最终值（最大和最小）,  * 从而使外排序趟数大概减少了一半 * @param {*} arr  * 耗时：312ms */function bubbleSort3(arr) {    let start = 0;    let end = arr.length - 1;      while (start < end) {      let endPos = 0;      let startPos = 0;      for (let i = start; i < end; i++) {        if (arr[i] > arr[i + 1]) {            endPos = i;            swap(arr, i, i + 1);        }      }      end = endPos;      for (let i = end; i > start; i--) {        if (arr[i - 1] > arr[i]) {          startPos = i;            swap(arr, i - 1, i);        }      }      start = startPos;    }      return arr;  }

通过在每趟排序中进行正向和反向两遍冒泡，小明把时间又降低了38ms，不错～

再次推荐大家有事多上上维基百科，总有一款适合你。####3.插入排序 在收入小规模胜利后，小明膨胀了，狂言要把排序时间降低到100ms一下，于是后又安利了如下算法：

/**   * 插入排序 -- 基础版   * @param {*} arr    * 耗时：897ms   */  function insertionSort(arr) {    for (let i = 1, len = arr.length; i < len; i++) {      const temp = arr[i];      let preIndex = i - 1;        while (arr[preIndex] > temp) {        arr[preIndex + 1] = arr[preIndex];        preIndex -= 1;      }      arr[preIndex + 1] = temp;    }      return arr;  }

897ms,小明留下了没技术的泪水。

最后小明拿出了这个看家本领，查到了二分搜索，最后改造后代码入下：

/**   * 改造二分查找,查找小于value且离value最近的值的索引   * @param {*} arr    * @param {*} maxIndex    * @param {*} value    */  function binarySearch1(arr, maxIndex, value) {    let min = 0;    let max = maxIndex;        while (min <= max) {      const m = Math.floor((min + max) / 2);        if (arr[m] <= value) {        min = m + 1;      } else {        max = m - 1;      }    }      return min;  }/** * 使用二分法来优化插入排序 * @param {*} arr  * 耗时：86ms */function insertionSort1(arr) {    for (let i = 1, len = arr.length; i < len; i++) {        const temp = arr[i];        const insertIndex = binarySearch1(arr, i - 1, arr[i]);        for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {        arr[preIndex + 1] = arr[preIndex];        }        arr[insertIndex] = temp;    }    return arr;}

完美，只用了86ms！小明激动的站了起来，还拍了下桌子，全然无视观众的眼光。

小明已经满足的不要不要的了，对86ms相当满意，老板也对他刮目想看。

难道就没有提升的余地了么？进过调查研究表明，是有更优的方案的：

/** * 希尔排序 * 核心：通过动态定义的 gap 来排序，先排序距离较远的元素，再逐渐递进 * @param {*} arr  * 耗时：15ms */function shellSort(arr) {    const len = arr.length;    let gap = Math.floor(len / 2);      while (gap > 0) {      // gap距离      for (let i = gap; i < len; i++) {        const temp = arr[i];        let preIndex = i - gap;          while (arr[preIndex] > temp) {          arr[preIndex + gap] = arr[preIndex];          preIndex -= gap;        }        arr[preIndex + gap] = temp;      }      gap = Math.floor(gap / 2);    }      return arr;  }

耗时15ms，膜拜。####5.归并排序

/** * 归并排序 * @param {*} arr  * 耗时 30ms */function concatSort(arr) {  const len = arr.length;  if (len < 2) { return arr; }  const mid = Math.floor(len / 2);  const left = arr.slice(0, mid);  const right = arr.slice(mid);  return concat(concatSort(left), concatSort(right));}function concat(left, right) {  const result = [];  while (left.length > 0 && right.length > 0) {    result.push(left[0] <= right[0] ? left.shift() : right.shift());  }  return result.concat(left, right);}

耗时30ms，也想当优秀。还有没有更快的方法呢？答案是有的，但是会涉及到比较高僧的数学知识，放弃吧，孩子。。。

原创不易，且赞且珍惜。看官至此，何不来一波mark三连。

monitor-event-emitter 源码

以上便是本次分享的全部内容，希望对你有所帮助^_^

喜欢的话别忘了分享、点赞、收藏三连哦~。

欢迎关注公众号趣谈前端收获前端一手好文章~

LowCode可视化低代码社区介绍

LowCode低代码社区(http://lowcode.dooring.cn)是由在一线互联网公司深耕技术多年的技术专家创办，意在为企业技术人员提供低代码可视化相关的技术交流和分享，并且鼓励国内拥有相关业务的企业积极推荐自身产品，为国内B端技术领域积累知识资产。同时我们还欢迎开源大牛们分享自己的开源项目和技术视频。

如需入驻请加下方小编微信:lowcode-dooring

关键词： 冒泡排序 插入排序 测试函数