如何让前端代码速度提高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，提高小明觉得还不错，放到项目中后，第一次操作还好，连续操作了几次后，页面明显卡顿。。。(求此时小明心里的源码下载阴影面积)。

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 < 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相当满意，老板也对他刮目想看。

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 < 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，也想当优秀。还有没有更快的方法呢?答案是有的，但是会涉及到比较高僧的数学知识，放弃吧，孩子......

云南idc服务商