《前端算法系列》如何让前端程式码速度提高60倍
来源： https://juejin.im/post/5d034e83e51d45773e418a69
今天的问题从排序算法入手，来讲解如何根据业务需求，结合金典的算法，来实现js高效能开发。情景
老板让小明给公司的20000+条资料排个序，但是由于排序的操作会频繁发生，如果操作执行的时间很慢，则会严重降低使用者体验，听到这条噩耗后小明开始了程式码。
1.毫无违和感的排序算法 小明根据需求，思考了一会，写下了如下算法：
/**
* max排序
* @param {*} arr
* 耗时：760ms
*/
function maxSort(arr) {
let result = [...arr];
for(let i=0,len=result.length; 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，小明觉得还不错，放到专案中后，第一次操作还好，连续操作了几次后，页面明显卡顿。。。（求此时小明心里的阴影面积）
2.气泡排序
小明不甘心，在网上查询相关资料后，写下了如下气泡排序程式码：
/**
* 置换函式
* @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 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 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 let endPos = 0;
let startPos = 0;
for (let i = start; 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 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 const m = Math.floor((min + max) / 2);
if (arr[m] min = m + 1;
} else {
max = m - 1;
}
}
return min;
}
/**
* 使用二分法来优化插入排序
* @param {*} arr
* 耗时：86ms
*/
function insertionSort1(arr) {
for (let i = 1, len = arr.length; 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相当满意，老板也对他刮目想看。4.希尔排序
难道就没有提升的余地了么？进过调查研究表明，是有更优的方案的：
/**
* 希尔排序
* 核心：通过动态定义的 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 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 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] }
return result.concat(left, right);
}
复制程式码
耗时30ms，也想当优秀。还有没有更快的方法呢？答案是有的，但是会涉及到比较高僧的数学知识，放弃吧，孩子。。。
