An ordered array inserts a number
functionInsertNumber (arr, x) {// Find the first number greater than xlet b = newArr.find(e => e > x);
ifNewarr.push (x); (b === undefined) {// If b does not exist, prove that x is the largest number. }else{// get the index of b and insert the new number into the position of Blet bIndex = newArr.indexOf(b)
newArr.splice(bIndex, 0, x)
}
return arr;
}
Copy the codeTwo ordered arrays are merged to form a new ordered array
- Just like insertion, the first destruct, the second array is iterated over and inserted into the first array
functionInsert_some_numbers (arr1, arr2) {insert_some_numbers(arr1, arr2) {var newArr = [...arr1];for(var i = 0; i < arr2.length; I ++) {// Get every bit of the second array x = arr2[I]; // Look for the first larger array in the newly deconstructed arrayletb = newArr.find(e => e > x); // Get the index of the number and insert it before itlet bindex = newArr.indexOf(b)
newArr.splice(bindex === -1 ? newArr.length : bindex, 0, x)
}
return newArr;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
console.log(insert_some_numbers(arr1, [1, 2, 3]));
Copy the codeBinary search
- Math.ceil(math.log2 (arr.length))
functionbinarySearch(arr, x) { var left = 0; Var right = arr. Length - 1; // right margin var guess; // Cursor, intermediate index to decimal pointwhile(left < = right) {/ / on the left side of the border is less than the right side of the border to perform guess = ((left + right) / 2) | 0; // Cursor index, intermediate index to the decimal pointif (arr[guess] === x) returnGuess // Return the cursor index if the cursor index is the searched Xelse if(ARr [GUESS] > x) right = GUESS - 1 // The cursor index bit is greater than x, and the right border moves to the front of GUESS.elseLeft = GUESS + 1 // Cursor index bit less than x, right border moved after GUESS. }return- 1; } var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; console.log( binarySearch(arr, 5) )Copy the codeInserts a new number into an ordered array
- Simulate an empty position loop comparison,
- If you look at the end of the array, the first digit is greater than x, the digit greater than x is indexed by +1,
- If it is smaller than X, the p+1 bit index is taken up by X
functionInsert_number_3 (arr, x) {//p is the index of the next element to be compared. //p-1 is empty. //p cannot be less than 0let p = arr.length - 1;
while (p >= 0 && arr[p] > x) {
arr[p + 1] = arr[p];
p--;
}
arr[p + 1] = x;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
insert_number_3(arr1, 6)
console.log(arr1)
Copy the codeInsertion sort
- The performance of the worst
- N ^2 over 2 minus n over 2
- Comparisons are made from the first index of the array
- Comparison times 1 + 2 + 3 + ··· + arr. Length times
functionInsertion_sort (arr) {insertion_sort(arr) {insertion_sort(arr) {insertion_sort(arr) {insertion_sort(arr)for(var i = 1; i < arr.length; i++) { insert(arr, i, arr[i]); }}function insert(arr, i, x) {
letp = i - 1; // arr[I] is the element to be insertedwhile(p = 0 > && arr [p] > x) {/ / when the element to insert arr [p + 1) = arr [p]. p--; } arr[p + 1] = x; }Copy the codeSelection sort
// Find the first smallest and put it first // Find the second smallest and put it secondfunctionselect(array) { var len = array.length; // from zero to second to lastfor(var i = 0; i < len - 1; Var minnum = array[I]; var minnum = array[I]; // First to lastfor(var j = i + 1; j < len; J++) {// swap values if the latter is smallerif(array[j] < minnum) {// Swap [array[j], minnum = [minnum, array[j]]]}} array[I] = minnum; } } var arr = [4, 5, 8, 9, 4, 2, 15, 6] select(arr) console.log(arr)Copy the codeBubble sort
- Find the largest first, then the smallest
- The performance of the worst
- Arr. Length -> n**n/2 -n/2 times
functionBubble_sort (arr) {// The value swap functionfunctionSwap (arr, x, j) {[arr [x], arr [j]] = [arr [j], arr [I]]} / / to find the largest first, then find out the minimumfor (leti = arr.length - 1; i >= 1; I --) {// Start with 1, and compare with the previous digit each time.for (let j = 1; j <= i; j++) {
arr[j] < arr[j - 1] && swap(arr, j-1, j)
}
}
}
const arr2 = [91, 60, 96, 9, 30, 20, 31, 77, 81, 24];
bubble_sort(arr2)
console.log(arr2);
Copy the codeMerge sort
// Index [a,b) and [b,c) // merge function parts,functionMerge (arr, a, b, c) {// Merge (arr, a, b, c)let arr1 = arr.slice(a, b);
letarr2 = arr.slice(b, c); // Place sentry arr1.push(Infinity) behind two arrays; arr2.push(Infinity); Var I = 0, j = 0; var I = 0, j = 0; // Loop to assign arrfor (letk = a; k < c; K ++) {//k: next write position // I: write back position in arr1 //j: write back position in arr2 arr[k] = arr1[I] < arr2[j]? arr1[i++] : arr2[j++]; }}functionMergeSort (arr, a, c) {// Check whether the array length is 1if (c - a < 2) { return}; const b = Math.ceil((a + c) / 2); // mergeSort(arr, a, b); // mergeSort(arr, b, c); // Merge merge(arr, a, b, c); } // Split the array into one, one array, and perform concatenationCopy the codeDual fast
functionQuickSort (arr) {// Recursive exit, array length 0if (arr.length == 0) return[]; Var left = []; var left = []; var right = []; var pivot = arr[0]; // Start with the first digit of the arrayfor (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else{ right.push(arr[i]); }} // Recursively concatenates arrays. This function is pure and does not change the original array.return quickSort(left).concat(pivot, quickSort(right))
}
let arr = [4, 51, 59, 13, 1, 31, 3, 1, 8];
let result = quickSort(arr);
console.log(result)
Copy the codeThree way fast row
function qSort3(arr) {
if (arr.length == 0) {
return[]; } var left = []; Var center = []; var center = []; var right = []; // Set a comparison value var pivot = arr[0]; // Loop comparison sectionfor (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else if (arr[i] == pivot) {
center.push(arr[i]);
} else{ right.push(arr[i]); }} // Loop recursively over parts greater than and less than the comparison valuereturn [...qSort3(left), ...center, ...qSort3(right)];
}
var newArr = qSort3([9, 4, 10, 8, 12, 2, 6, 7, 3, 1, 1, 0, 9, 1, 0])
console.log(newArr)
Copy the codeThe depth of the clone
function deepClone2(origin, target) {
var target = target || ((origin instanceof Array) ? [] : {});
for (var prop in origin) {
if (origin.hasOwnProperty(prop)) {
if (typeof origin[prop] == 'object') {
if (Object.prototype.toString.call(origin[prop]) === '[object Array]') {
target[prop] = [];
} else {
target[prop] = {};
}
deepClone2(origin[prop], target[prop]);
} else {
target[prop] = origin[prop]
}
}
}
return target;
}
Copy the codeArray flattening
function platArray(arr) {
var newArr = [];
function pushToArray(arr) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] instanceof Array) {
pushToArray(arr[i])
} else {
newArr.push(arr[i])
}
}
}
pushToArray(arr)
return newArr;
}
console.log(platArray([[1, 2], [[[[3]]]], [{ name: "lyz", info: { age: "24"}}], [4, [5, [6]]]])); // [1, 2, 3, { name:'lyz', info: { age: '24'}}, 4, 5, 6]Copy the codeString inversion
var str = 'abcde';
functionStrReverse (STR) {// new String is an array of classes that cannot be changed; // writeable isfalse; var strObj = [...new String(str)]; vartimes = strObj.length / 2 | 0;
for (var i = 0; i < times; i++) {
var y = strObj.length - 1 - i;
[strObj[i], strObj[y]] = [strObj[y], strObj[i]];
}
return strObj.join(' ');
}
console.log(strReverse(str));
Copy the codeObserver model
//es6
class Event {
constructor() {
this.cache = {};
}
on(type, handle) {
if(! this.cache[type]) {
this.cache[type] = [handle];
} else {
this.cache[type].push(handle)}} // Execute somethingtypeAll of the following functionsemmit() {// argiments first istypeType, and the remaining bits are arguments to the function // gettype
var type= arguments[0]; Var arg = [].slice.call(arguments, 1); // Execute the functions in the arrayfor (var i = 0; i < this.cache[type].length; i++) {
this.cache[type[I].apply(this, arg)}typeThe empty array (type) {
this.cache[type] = []; } // Empty the specifiedtypeThe specified Hanle remove(type, handle) {
var infos = this.cache[type];
if(! infos)return false;
if(! handle) { infos && (infos.length = 0); }else {
for (var i = 0, len = infos.length; i < len; i++) {
if (infos[i] === handle) {
infos.splice(i, 1);
}
}
}
}
}
Copy the codeA simplified version of promises (no support for asynchronous triggering within promises yet)
// The executor function is a synchronous function with two parameters. Resolve reject // Promise has three states pending, depressing and RejectedfunctionMyPromise (executor) {var _this = this; // Set the initial state and the resolve and reject arguments _this.status ="pending";
_this.resolveValue = null;
_this.rejectValue = null;
function resolve(value) {
if (_this.status === 'pending') {
_this.status = "fulfilled"; _this.resolveValue = value; }}function reject(reason) {
if (_this.status === 'pending') {
_this.status = "rejected"; _this.rejectValue = reason; } // Use a try catch to handle an exception in a Promise. Try {executor(resolve, reject)} catch (e) { Reject (e)}} // The method on the prototype chainthenMypromise.prototype.then =function (onFulfilled, onRejected) {
var _this = this;
if (_this.status === "fulfilled") {
onFulfilled(_this.resolveValue)
}
if (_this.status === "rejected") {
onRejected(_this.rejectValue)
}
}
Copy the codeA simplified version of Promise that supports asynchrony (no chaining)
// The executor function is a synchronous function with two parameters. Resolve reject // Promise has three states: // Pending, depressing, and RejectedfunctionMyPromise (executor) {var _this = this; // Set the initial state and the resolve and reject arguments _this.status ="pending"; _this.resolveValue = null; _this.rejectValue = null; _this.ResolveCallbackList = []; _this.RejectCallbackList = [];function resolve(value) {
if (_this.status === 'pending') {
_this.status = "fulfilled"; _this.resolveValue = value; / / execution time is asynchronous, if it is asynchronous, / / array function, otherwise there is no function. _this ResolveCallbackList. ForEach (function(ele) { ele(); }}})function reject(reason) {
if (_this.status === 'pending') {
_this.status = "rejected"; _this.rejectValue = reason; / / execution time is asynchronous, if it is asynchronous, / / array function, otherwise there is no function. _this RejectCallbackList. ForEach (function(ele) { ele(); } // Use a try catch to handle a Promise exception. Try {executor(resolve, reject)} catch (e) { Reject (e)}} // The method on the prototype chainthenMypromise.prototype.then =function (onFulfilled, onRejected) {
var _this = this;
if (_this.status === "fulfilled") {
onFulfilled(_this.resolveValue)
}
if (_this.status === "rejected") {onRejected(_this.rejectValue)} // Add the pending status to the array of the execution events you rejected (_this.rejectValue)if (_this.status === "pending") {
onFulfilled && _this.ResolveCallbackList.push(function () {
onFulfilled(_this.resolveValue);
});
onRejected && _this.RejectCallbackList.push(function() { onRejected(_this.rejectValue); }}})Copy the codeSimplified Promise supports chained calls (then is currently synchronous)
functionMyPromise (executor) {var _this = this; // Set the initial state and the resolve and reject arguments _this.status ="pending"; _this.resolveValue = null; _this.rejectValue = null; _this.ResolveCallbackList = []; _this.RejectCallbackList = [];function resolve(value) {
if (_this.status === 'pending') {
_this.status = "fulfilled";
_this.resolveValue = value;
_this.ResolveCallbackList.forEach(function(ele) { ele(); }}})function reject(reason) {
if (_this.status === 'pending') {
_this.status = "rejected";
_this.rejectValue = reason;
_this.RejectCallbackList.forEach(function(ele) { ele(); } // Use a try catch to handle a Promise exception. Try {executor(resolve, reject)} catch (e) { Reject (e)}} // The method on the prototype chainthenThen returns a >>> new Promise object <<< note the new myPromise.prototype.then =function (onFulfilled, onRejected) {
var _this = this;
var nextPromise = new myPromise(function (resolve, reject) {
if (_this.status === "fulfilled") { var nextResolveValue = onFulfilled(_this.resolveValue); / / to getthenThe return value of the first function inside is given to the next onethenResolve (nextResolveValue); resolve(nextResolveValue); }if (_this.status === "rejected") { var nextRejectValue = onRejected(_this.rejectValue); // This must also be a function of resolve, resolve(nextRejectValue); }if (_this.status === "pending") {
onFulfilled && _this.ResolveCallbackList.push(function() { var nextResolveValue = onFulfilled(_this.resolveValue); Resolve (nextResolveValue); resolve(nextResolveValue); }); onRejected && _this.RejectCallbackList.push(function() { var nextRejectValue = onRejected(_this.rejectValue); // This must also be the resolve function resolve(nextRejectValue); }}}));return nextPromise;
}
Copy the codePromise implements empty THEN () passing, and.then() asynchronously executes.then() throwing errors
functionMyPromise (executor) {var _this = this; // Set the initial state and the resolve and reject arguments _this.status ="pending"; _this.resolveValue = null; _this.rejectValue = null; _this.ResolveCallbackList = []; _this.RejectCallbackList = [];function resolve(value) {
if (_this.status === 'pending') {
_this.status = "fulfilled";
_this.resolveValue = value;
_this.ResolveCallbackList.forEach(function(ele) { ele(); }}})function reject(reason) {
if (_this.status === 'pending') {
_this.status = "rejected";
_this.rejectValue = reason;
_this.RejectCallbackList.forEach(function(ele) { ele(); } // Use a try catch to handle a Promise exception. Try {executor(resolve, reject)} catch (e) { Reject (e)}} // The method on the prototype chainthenThen returns a >>> new Promise object <<< note is ** new ** // // emptythenThen ((val)=>val, err=>err) myPromise.prototype. Then =function(onFulfilled, onRejected) { var _this = this; / / implementationthenThe transfer of dataif(! onFulfilled) { onFulfilled =function (val) {
returnval; }}if(! onRejected) { onRejected =function (reason) {
throw reason
}
}
var nextPromise = new myPromise(function (resolve, reject) {
if (_this.status === "fulfilled") {// usethenImplement asynchronous execution, and throw error handlingsetTimeout(function() { try { var nextResolveValue = onFulfilled(_this.resolveValue); / / to getthenThe return value of the first function inside is given to the next onethenResolve (nextResolveValue); resolve(nextResolveValue); } catch (e) { reject(e) } }) }if (_this.status === "rejected") {
setTimeout(function() { try { var nextRejectValue = onRejected(_this.rejectValue); // This must also be a function of resolve, resolve(nextRejectValue); } catch (e) { reject(e) } }) }if (_this.status === "pending") {
onFulfilled && _this.ResolveCallbackList.push(function () {
setTimeout(function() { try { var nextResolveValue = onFulfilled(_this.resolveValue); Resolve (nextResolveValue); resolve(nextResolveValue); } catch (e) { reject(e) } }) }); onRejected && _this.RejectCallbackList.push(function () {
setTimeout(function() { try { var nextRejectValue = onRejected(_this.rejectValue); // This must also be the resolve function resolve(nextRejectValue); } catch (e) { reject(e) } }) }) } });return nextPromise;
}
Copy the codeThe complete Promise function implementation principle
functionMyPromise(executor) {var _this = this; // Set the initial state and the resolve and reject arguments _this.status ="pending"; _this.resolveValue = null; _this.rejectValue = null; _this.ResolveCallbackList = []; _this.RejectCallbackList = [];function resolve(value) {
if (_this.status === 'pending') {
_this.status = "fulfilled";
_this.resolveValue = value;
_this.ResolveCallbackList.forEach(function(ele) { ele(); }}})function reject(reason) {
if (_this.status === 'pending') {
_this.status = "rejected";
_this.rejectValue = reason;
_this.RejectCallbackList.forEach(function(ele) { ele(); } // Use a try catch to handle a Promise exception. Try {executor(resolve, reject)} catch (e) { Reject (e)}} // The method on the prototype chainthenThen returns a >>> new Promise object <<< note is ** new ** // // emptythenThen ((val)=>val, err=>errthenThe function inside returns a new New promisefunction ResolutionReturnValue(returnValue, resolve, reject) {
if (returnValue instanceof MyPromise) {// If it is a promise object, usethenProcessing back to the nextthen.returnValue.then(function (val) {
resolve(val);
}, function(reason) { reject(reason); })}else {
// returnValue is a common Value resolve(returnValue);
}
}
MyPromise.prototype.then = function(onFulfilled, onRejected) { var _this = this; / / implementationthenThe transfer of dataif(! onFulfilled) { onFulfilled =function (val) {
returnval; }}if(! onRejected) { onRejected =function (reason) {
throw reason
}
}
var nextPromise = new MyPromise(function (resolve, reject) {
if (_this.status === "fulfilled") {// usethenImplement asynchronous execution, and throw error handlingsetTimeout(function() {//nextResolveValue may be an object new Promise (), var nextResolveValue = ondepressing (_this.resolvevalue); // Because it is asynchronous code, nextPromise can be passed to function execution becausesetResolutionReturnValue(nextResolveValue, resolve, reject) after assigning nextPromise; } catch (e) { reject(e) } }) }if (_this.status === "rejected") {
setTimeout(function() { try { var nextRejectValue = onRejected(_this.rejectValue); // This must also be a resolve function, ResolutionReturnValue(nextRejectValue, resolve, reject); } catch (e) { reject(e) } }) }if (_this.status === "pending") {
onFulfilled && _this.ResolveCallbackList.push(function () {
setTimeout(function() { try { var nextResolveValue = onFulfilled(_this.resolveValue); ResolutionReturnValue(nextResolveValue, resolve, reject); } catch (e) { reject(e) } }) }); onRejected && _this.RejectCallbackList.push(function () {
setTimeout(function () {
try {
var nextRejectValue = onRejected(_this.rejectValue);
// 这个也必须要是resolve的函数
ResolutionReturnValue(nextRejectValue, resolve, reject);
} catch (e) {
reject(e)
}
})
})
}
});
returnnextPromise; } // module exports = MyPromise} catch (e) {}Copy the codePromise.all
MyPromise.all = function(promises) {
return new Promise(function(resolve, reject) {// Type judgmentif(! isArray(promises)) {return reject(new TypeError('arguments must be an array')); Var resolvedCounter = 0; Var promisesNum = promises. Length; Var resolvedValues = new Array(promiseNum); // The array is traversed asynchronously to prevent closure.for (var i = 0; i < promiseNum; i++) {
(function (i) {
Promise.resolve(promises[i]).then(function(value) {resolvedCounter++ resolvedValues[I] = value // the outermost resolve execution is triggered only if the number of resolve matches the number of promiseif (resolvedCounter == promisesNum) {
return resolve(resolvedValues)
}
}, function (reason) {
return reject(reason)
})
})(i)
}
})
}
Copy the code