今天的问题从排序算法入手，来讲解如何根据业务需求，结合金典的算法，来实现js高性能开发。
情景
老板让小明给公司的20000+条数据排个序，但是由于排序的操作会频繁发生，如果操作执行的时间很慢，则会严重降低用户体验，听到这条噩耗后小明开始了代码。
1.毫无违和感的排序算法 小明根据需求，思考了一会，写下了如下算法：
1/** 2 * max排序 3 * @param {*} arr 4 * 耗时：760ms 5 */ 6 function maxSort(arr) { 7 let result = [...arr]; 8 for(let i=0,len=result.length; i< len; i++) { 9 let minV = Math.min(...result.slice(i)) 10 let pos = result.indexOf(minV,i) 11 result.splice(pos, 1) 12 result.unshift(minV) 13 } 14 return result.reverse() 15 }
自信的小明陶醉在自己的算法中，准备测试一下性能，
1/* 2 * @Author: Mr Jiang.Xu 3 * @Date: 2019-06-11 10:25:23 4 * @Last Modified by: Mr Jiang.Xu 5 * @Last Modified time: 2019-06-13 21:03:59 6 * @desc 测试函数执行的时间 7 */ 8 9const testArr = require('./testArr'); 10module.exports = async function getFnRunTime(fn) { 11 let len = testArr.length; 12 let startTime = Date.now(), endTime; 13 let result = await fn(testArr); 14 endTime = Date.now(); 15 console.log(result); 16 console.log(`total time:${endTime-startTime}ms`, 17 'test array\'length:' + len, 18 result.length 19 ); 20}
运行该测试函数后，耗时760ms，小明觉得还不错，放到项目中后，第一次操作还好，连续操作了几次后，页面明显卡顿。。。（求此时小明心里的阴影面积）
2.冒泡排序
小明不甘心，在网上查找相关资料后，写下了如下冒泡排序代码：
1/** 2 * 置换函数 3 * @param {源数组} arr 4 * @param {原数组的A项} indexA 5 * @param {原数组的B项} indexB 6 */ 7 function swap(arr, indexA, indexB) { 8 [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]]; 9 } 10 11/** 12 * 原始冒泡排序 13 * @param {数组} arr 14 * 耗时：377ms 15 */ 16 function bubbleSort1(arr) { 17 for (let i = arr.length - 1; i > 0; i--) { 18 for (let j = 0; j < i; j++) { 19 if (arr[j] > arr[j + 1]) { 20 swap(arr, j, j + 1); 21 } 22 } 23 } 24 25 return arr; 26 }
测试后耗时377ms，完美，小明放到项目中测试，频繁排序还是会有点卡顿，能不能再优化一下呢？ 思考许久之后，小明完善了冒泡排序：
1/** 2 * 利用索引优化后的冒泡排序 3 * @param {数组} arr 4 * 耗时：350ms 5 */ 6function bubbleSort2(arr) { 7 let i = arr.length - 1; 8 9 while (i > 0) { 10 let pos = 0; 11 12 for (let j = 0; j < i; j++) { 13 if (arr[j] > arr[j + 1]) { 14 pos = j; 15 swap(arr, j, j + 1); 16 } 17 } 18 i = pos; 19 } 20 21 return arr; 22}
根据缓存索引位置来提高排序性能，时间节约了20ms，但收益很小。小明开始和自己过不去了，在维基百科上继续查找，最后发现了一个方法：
1/** 2 * 在每趟排序中进行正向和反向两遍冒泡 , 3 * 一次可以得到两个最终值（最大和最小）, 4 * 从而使外排序趟数大概减少了一半 5 * @param {*} arr 6 * 耗时：312ms 7 */ 8function bubbleSort3(arr) { 9 let start = 0; 10 let end = arr.length - 1; 11 12 while (start < end) { 13 let endPos = 0; 14 let startPos = 0; 15 for (let i = start; i < end; i++) { 16 if (arr[i] > arr[i + 1]) { 17 endPos = i; 18 swap(arr, i, i + 1); 19 } 20 } 21 end = endPos; 22 for (let i = end; i > start; i--) { 23 if (arr[i - 1] > arr[i]) { 24 startPos = i; 25 swap(arr, i - 1, i); 26 } 27 } 28 start = startPos; 29 } 30 31 return arr; 32 }
通过在每趟排序中进行正向和反向两遍冒泡，小明把时间又降低了38ms，不错～
再次推荐大家有事多上上维基百科，总有一款适合你。
####3.插入排序
在收入小规模胜利后，小明膨胀了，狂言要把排序时间降低到100ms一下，于是后又安利了如下算法：
1/** 2 * 插入排序 -- 基础版 3 * @param {*} arr 4 * 耗时：897ms 5 */ 6 function insertionSort(arr) { 7 for (let i = 1, len = arr.length; i < len; i++) { 8 const temp = arr[i]; 9 let preIndex = i - 1; 10 11 while (arr[preIndex] > temp) { 12 arr[preIndex + 1] = arr[preIndex]; 13 preIndex -= 1; 14 } 15 arr[preIndex + 1] = temp; 16 } 17 18 return arr; 19 }
897ms,小明留下了没技术的泪水。
最后小明拿出了这个看家本领，查到了二分搜索，最后改造后代码入下：
1/** 2 * 改造二分查找,查找小于value且离value最近的值的索引 3 * @param {*} arr 4 * @param {*} maxIndex 5 * @param {*} value 6 */ 7 function binarySearch1(arr, maxIndex, value) { 8 let min = 0; 9 let max = maxIndex; 10 11 while (min <= max) { 12 const m = Math.floor((min + max) / 2); 13 14 if (arr[m] <= value) { 15 min = m + 1; 16 } else { 17 max = m - 1; 18 } 19 } 20 21 return min; 22 } 23 24/** 25 * 使用二分法来优化插入排序 26 * @param {*} arr 27 * 耗时：86ms 28 */ 29function insertionSort1(arr) { 30 for (let i = 1, len = arr.length; i < len; i++) { 31 const temp = arr[i]; 32 const insertIndex = binarySearch1(arr, i - 1, arr[i]); 33 34 for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) { 35 arr[preIndex + 1] = arr[preIndex]; 36 } 37 arr[insertIndex] = temp; 38 } 39 40 return arr; 41}
完美，只用了86ms！小明激动的站了起来，还拍了下桌子，全然无视观众的眼光。
小明已经满足的不要不要的了，对86ms相当满意，老板也对他刮目想看。
4.希尔排序
难道就没有提升的余地了么？进过调查研究表明，是有更优的方案的：
1/** 2 * 希尔排序 3 * 核心：通过动态定义的 gap 来排序，先排序距离较远的元素，再逐渐递进 4 * @param {*} arr 5 * 耗时：15ms 6 */ 7function shellSort(arr) { 8 const len = arr.length; 9 let gap = Math.floor(len / 2); 10 11 while (gap > 0) { 12 // gap距离 13 for (let i = gap; i < len; i++) { 14 const temp = arr[i]; 15 let preIndex = i - gap; 16 17 while (arr[preIndex] > temp) { 18 arr[preIndex + gap] = arr[preIndex]; 19 preIndex -= gap; 20 } 21 arr[preIndex + gap] = temp; 22 } 23 gap = Math.floor(gap / 2); 24 } 25 26 return arr; 27 }
耗时15ms，膜拜。 ####5.归并排序
1/** 2 * 归并排序 3 * @param {*} arr 4 * 耗时 30ms 5 */ 6function concatSort(arr) { 7 const len = arr.length; 8 9 if (len < 2) { return arr; } 10 11 const mid = Math.floor(len / 2); 12 const left = arr.slice(0, mid); 13 const right = arr.slice(mid); 14 15 return concat(concatSort(left), concatSort(right)); 16} 17 18function concat(left, right) { 19 const result = []; 20 21 while (left.length > 0 && right.length > 0) { 22 result.push(left[0] <= right[0] ? left.shift() : right.shift()); 23 } 24 25 return result.concat(left, right); 26}
耗时30ms，也想当优秀。还有没有更快的方法呢？答案是有的，但是会涉及到比较高僧的数学知识，放弃吧，孩子。。。
接下来会推出更多优秀的算法，敬请期待哦～ 最后，欢迎加入前端技术群，一起探讨前端的魅力