scenario
The boss asked Xiaoming to order the 20000+ pieces of data of the company, but because the sorting operation will happen frequently, if the operation execution time is slow, it will seriously reduce the user experience. After hearing this bad news, Xiaoming started the code.
According to the needs of Xiao Ming, he thought for a while and wrote down the following algorithm:
/** * Max sort * @param {*} arr *function maxSort(arr) {
let result = [...arr];
for(let i=0,len=result.length; i< len; i++) {
letminV = Math.min(... result.slice(i))let pos = result.indexOf(minV,i)
result.splice(pos, 1)
result.unshift(minV)
}
return result.reverse()
}
Copy the codeThe confident Xiao Ming, intoxicated with his algorithm, was ready to test its performance,
/* * @Author: Mr Jiang.Xu * @Date: 2019-06-11 10:25:23 * @Last Modified by: Mr Jiang.Xu * @Last Modified time: */ 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 ); }Copy the codeAfter running the test function, it took 760ms, xiao Ming thought it was ok, put it into the project, the first operation was ok, after several consecutive operations, the page was obviously stuck… (Find the shaded area in Xiao Ming’s heart)
2. Bubble sort
Xiao Ming was not reconciled, after looking up relevant information on the Internet, he wrote the following bubble sort code:
/** * replacement function * @param {source array} arr * @param {source array} indexA * @param {source array} indexB */functionswap(arr, indexA, indexB) { [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]]; /** * Raw bubble sort * @param {array} arr * Time: 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;
}
Copy the codeAfter the test, it took 377ms, which was perfect. Xiao Ming put it into the project for testing, but there is still a bit of lag when sorting frequently. Could you optimize it again? After thinking for a long time, Xiao Ming perfected the bubble sort:
/** * Use index optimization bubble sort * @param {array} arr * time: 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;
}
Copy the codeImproving sorting performance by cache index location saves 20ms, but the benefit is small. Xiao Ming began to have a hard time with himself, and continued to search on Wikipedia. Finally, he found a way:
@param {*} arr * @param {*} arr * time: 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;
}
Copy the codeBy bubbling forward and backward twice in each sequence, Xiao Ming reduced the time by another 38ms
/** * Insert sort -- Basic * @param {*} arr * Time: 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;
}
Copy the code897ms, Xiaoming left tears of no technology.
@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; }}returnmin; } /** * Use dichotomy to optimize insertion sort * @param {*} arr * Time: 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;
}
Copy the codePerfect, only 86ms! Xiao Ming excitedly stood up and patted the table, completely ignoring the eyes of the audience.
1. 4. Smart Car
Is there no room for advancement? Studies have shown that there is a better solution:
@param {*} arr * time: 15ms */function shellSort(arr) {
const len = arr.length;
let gap = Math.floor(len / 2);
while(gap > 0) {// gap distancefor (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;
}
Copy the codeTake 15ms, worship. ####5. Merge sort
/** * merge sort * @param {*} arr *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);
}
Copy the codeTime consuming 30ms, also want to be excellent. Is there a faster way? The answer is yes, but it involves the math knowledge of a monk. Give it up, kid…
More excellent algorithms will be introduced in the coming days, so stay tuned. Finally, welcome to join the front end technology group to discuss the charm of the front end
-
Front End Algorithm series array deweighting
-
Vue Advanced Advanced series – Play with Vue and vuex in typescript
-
In the first three years, talk about the top five books worth reading
-
With a single/multiple pages webpack4.0 lu scaffolding tools (support for jquery, react, vue, typescript)