Js Code sorting
Call apply bind new mock implementation
/** call a function with a specified value of this Execute function 3. Delete the object property */
Function.prototype.newCall = function(){
if(typeof this! = ='function') throw new Error('no function')
var context = arguments[0] | |window
context.fn = this
var args = []
for(var i = 1; i < arguments.length; i++){
args.push(arguments[i])
}
var result = eval('context.fn(' + args + ') ')
delete context.fn
return result
}
Copy the code/* Call a function with a specified value of this Execute function 3. Delete the object property */
Function.prototype.newApply = function(){
if(typeof this! = ='function') throw new Error('no function')
var context = arguments[0] | |window
context.fn = this
var args = arguments[1[]] | |var result = eval('context.fn(' + args + ') ')
delete context.fn
return result
}
Copy the code/* Create a new function, and use the first argument as this to run the new function. F(); F(); F(); F(); F(); F(); Change the return function's prototype to the binding function's prototype so that the instance inherits the binding function's prototype 5. 6. Self.apply (this instanceof F? This: context, arg) 'whether new call ', this instanceof fBound" */
Function.prototype.newBind = function(){
if(typeof this! = ='function') throw new Error('no function')
var context = arguments[0] | |window
var fn = this
var args = []
for(let i = 1; i < arguments.length; i++) args.push(arguments[i])
var bind = function(){
for(let i = 0; i < arguments.length; i++) args.push(arguments[i])
context = this instanceof bind ? this : context
return fn.apply(context, args)
}
var F = function(){}
F.prototype = this.prototype
bind.prototype = new F()
return bind
}
Copy the codeO 2. Construtor is a constructor imported externally 3. O.__proto__ = Construtor.prototype 4 = Construtor. Apply (O, the arguments) use a constructor to obj set properties 5. Ret | | O always returns an object * /
function New(){
var obj = new Object(a);var Constructor = Array.prototype.shift.call(arguments)
obj.__proto__ = Constructor.prototype
let ret =Constructor.apply(obj, arguments)
return typeof ret === 'object' ? ret : obj
}
Copy the codeIf the throttle
/* Execute after N seconds, no matter how many times the timer is fired. 3. Within the function, set timer 4. Returns a wrapped function */
function debounce(fn, wait, immediate) {
var timeout, result
var debounced = function(){
var context = this
var args = arguments
// If it exists, cancel and wait for seconds before calling again
if(timeout) clearTimeout(timeout)
if(immediate){
// Trigger immediately
// If it has not been triggered, it is triggered directly
varcaller = ! timeout timeout =setTimeout(function(){
timeout = null
}, wait)
if(caller) result = fn.apply(context, args)
}else{
timeout = setTimeout(function(){
result = fn.apply(context, args)
timeout = null
}, wait)
}
return result
}
/ / cancel
debounced.cancel = function(){
if(timeout) clearTimeout(timeout)
timeout = null
}
return debounced
}
Copy the code/* Execute only once, no matter how many times in a period of time You can set the current timestamp + time interval to control whether the event */ is triggered
// The timestamp implementation will execute immediately, and there is no way to execute the event after stopping the trigger
function throttle(fn, wait){
var prev = 0
var throttled = function(){
var now = +new Date(a)var context = this
var args = arguments
if(now - prev > wait){
fn.apply(context, args)
prev = now
}
}
return throttled
}
// The timer is executed for the first time after n seconds, and the event is executed again after the trigger is stopped
function throttle(fn, wait){
var timeout
var throttled = function(){
var context = this
var args = arguments
if(! timeout){ timeout =setTimeout(function(){
timeout = null
fn.apply(context, args)
}, wait)
}
}
return throttled
}
/ * * * *@param {function} Fn Execution method *@param {number} Wait Wait time *@param {} configuration Options Leading: Whether to allow immediate execution of trailing: Whether to allow the last execution of *@returns * /
function throttle(fn, wait, options) {
options = options || {}
var result, context, args, timeout
var prev = 0
var later = function(){
prev = options.leading === false ? 0 : +new Date()
timeout = null
result =fn.apply(context, args)
}
var t = function(){
var now = +new Date() prev = ! prev && options.leading ===false ? now : prev
var r = wait - (now - prev)
context = this
args = arguments
if(r > wait || r <= 0) {if(timeout){
clearTimeout(timeout)
timeout = null
}
prev = now
result = fn.apply(context, args)
}else if(! timeout && options.trailing ! = =false){
timeout = setTimeout(later, r)
}
return result
}
t.cancel = function(){
clearTimeout(timeout)
timeout = null
prev = 0
}
return t
}
Copy the codepromise
// Three states
const PENDING = 'pending'
const FULFILLED = 'fulfilled'
const REJECTED = 'rejected'
class MyPromise {
// State: the initial state is pending
status = PENDING
/ / value
value = null
/ / reasons
reason = null
// Execute the onFulfilled queue
onFulfilledCallbacks = []
// Execute the onRejected queue
onRejectedCallbacks = []
// The constructor
constructor(executor){
try {
executor(this.resolve, this.reject)
} catch (error) {
this.reject(error)
}
}
resolve = value= > {
// Check whether the state is in the wait state
if(this.status === PENDING){
// Change the state
this.status = FULFILLED
/ / assignment
this.value = value
// Loop call
while(this.onFulfilledCallbacks.length){
this.onFulfilledCallbacks.shift()(this.value)
}
}
}
reject = reason= > {
// Check whether the state is in the wait state
if(this.status === PENDING){
// Change the status
this.status = REJECTED
// Assignment reason
this.reason = reason
// Loop call
while(this.onRejectedCallbacks.length){
this.onRejectedCallbacks.shift()(this.reason)
}
}
}
then(onFulfilled, onRejected){
// This parameter is optional
const realOnFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value= > value
const realOnRejected = typeof onRejected === 'function' ? onRejected : reason= > { throw reason }
const promise1 = new MyPromise((resolve, reject) = > {
// Create a function to complete the microtask
const fulfilledMicrotask = () = > {
queueMicrotask(() = > {
try{
let x = realOnFulfilled(this.value)
resolvePromise(promise1, x, resolve, reject)
}catch (error) {
reject(error)
}
})
}
// Create a microtask to execute the rejected function
const rejectMicrotask = () = > {
queueMicrotask(() = > {
try{
let x = realOnRejected(this.reason)
resolvePromise(promise1, x, resolve, reject)
}catch (error) {
reject(error)
}
})
}
// Execute directly after the status is determined
if(this.status == FULFILLED){
fulfilledMicrotask()
}else if(this.status == REJECTED){
rejectMicrotask()
}else{
// Asynchronously, join the queue
this.onFulfilledCallbacks.push(fulfilledMicrotask)
this.onRejectedCallbacks.push(rejectMicrotask)
}
})
// then returns a new promise
return promise1
}
/ / catch method
catch (onRejected) {
this.then(null, onRejected)
}
// The finally() method is used to specify an action that will be performed regardless of the final state of the Promise object
finally(fn) {
return this.then(value= > {
return MyPromise.resolve(fn()).then(() = > {
return value
})
}, reason= > {
return MyPromise.resolve(fn()).then(() = > {
return reason
})
})
}
Sometimes it is necessary to turn an existing object into a Promise object with the state fulfilled
static resolve(parameter){
// If a promise object is passed, return it directly
if(parameter instanceof MyPromise){
return parameter
}
return new MyPromise(resolve= > {
resolve(parameter)
})
}
// The promise.reject (reason) method also returns a new Promise instance with the state rejected
static reject(reason){
return new MyPromise((resolve, reject) = > {
reject(reason)
})
}
// the all method returns when all is successful
static all(promiseList){
return new MyPromise((resolve, reject) = > {
let count = 0
let length = promiseList.length
let result = []
if(length === 0) return resolve(result)
for(let i = 0; i < length; i++){
MyPromise.resolve(promiseList[i]).then(value= > {
count++
results[i] = value
// All successful
if(count === length) resolve(result)
}, reason= > {
// A failure
reject(reason)
})
}
})
}
// The race method returns after only one success
static race(promiseList){
return new MyPromise((resolve, reject) = > {
let length = promiseList.length
if(length === 0) return resolve()
for (let i = 0; i < length; i++) {
MyPromise.resolve(promiseList[i]).then(value= > {
return resolve(value)
}, reason= > {
return reject(reason)
})
}
})
}
// Take a set of Promise instances as parameters and wrap it into a new Promise instance. Until all of these parameter instances have returned results,
static allSettled(promiseList){
return new MyPromise((resolve, reject) = > {
let count = 0
let length = promiseList.length
let result = []
if(length === 0) return resolve(result)
for (let i = 0; i < length; i++) {
MyPromise.resolve(promiseList[i]).then(value= > {
count++;
result[i] = {
value,
status: FULFILLED
}
if(count === length) resolve(result)
}, reason= > {
count++;
result[i] = {
reason,
status: REJECTED
}
if(count === length) resolve(result)
})
}
})
}
}
function resolvePromise(promise, x, resolve, reject){
if(x === promise){
// Call in a loop and report an error directly
return reject(new TypeError('The promise and the return value are the same'));
}
if(typeof x === 'function' || typeof x === 'object') {// null returns directly
if(x === null) return resolve(x)
let then
try {
then = x.then
} catch (error) {
// There is no direct rejection
return reject(error)
}
// If the object has a THEN method
if(typeof then === 'function') {let called = false
try {
then.call(x, y= > {
// Ignore multiple times
if(called) return
called = true
// Then execute
resolvePromise(promise, y, resolve, reject)
}, r= > {
// Ignore multiple times
if(called) return
called = true
reject(r)
})
} catch (error) {
//
if(called) return
called = true
reject(error)
}
}else{
// Then is not a function
resolve(x)
}
}else{
// If x is not an object or function, execute the promise with x as the argument
resolve(x)
}
}
Copy the codecurry compose pipe partial
// add(1, 2, 3) => add = curry(add) add(1, 2, 3) = add(1)(2)(3) = add(1)(2, 3) = ...
function curry(fn, args){
var length = fn.length
args = args || []
return function(){
var _args = args.slice().concat(Array.prototype.slice.call(arguments))
if(_args.length < length){
return curry.call(this, fn, _args)
}else{
return fn.apply(this, _args)
}
}
}
Copy the code// a(b(c(d))) => compose(c, b, a)(d)
function compose(){
var args = arguments
var start = args.length
return function(){
var result = args[--start].apply(this.arguments)
while(start--) result = args[start].call(this, result)
return result
}
}
Copy the code// a(b(c(d))) => pipe(a, b, c)(d)
function pipe(){
var args = arguments
var start = 0
return function(){
var result = args[start++].apply(this.arguments)
while(start < args.length){
result = args[start++].call(this, result)
}
return result
}
}
Copy the code// partial(func, _, 'b', _, 'd')('a', 'c')
var _ = {}
function partial(){
var fn = arguments[0]
var args = Array.prototype.slice.call(arguments.1)
var bind = function(){
var position = 0
_args = args.slice(0)
var len = _args.length
for(var i = 0; i < len; i++){
_args[i] = _args[i] === _ ? arguments[position++] : _args[i]
}
while(position < arguments.length) _args.push(arguments[position++])
return fn.apply(this, _args)
}
inherit(fn, bind)
return bind
}
function inherit(parent, child){
var F = function(){}
F.prototype = parent.prototype
child.prototype = new F()
}
Copy the codePublish and subscribe to the EventEmitter & Observer pattern Observer
/* The sender of a one-to-many message (called a publisher) does not send the message directly to a specific receiver (called a subscriber). Instead, the published messages are divided into different categories and sent separately to different subscribers. * /
class EventEmitter{
constructor(){
this.cache = {}
return this
}
on(type, event){
if(!this.cache[type]) this.cache[type] = []
if(this.cache[type].indexOf(event) == -1) {this.cache[type].push(event)
}
return this
}
off(type, event){
if(!this.cache[type]) return this
this.cache[type] = this.cache[type].filter(e= >e ! == event)return this
}
once(type, event){
let _event = function(){
event.apply(this.arguments)
this.off(type, _event)
}
this.on(type, _event)
return this
}
emit(){
let type = arguments[0]
let args = Array.prototype.slice.call(arguments.1)
let list = this.cache[type] || []
for (const event of list) {
event.apply(this, args)
}
return this}}Copy the code/* Observer mode, which defines a one-to-many relationship in which multiple observer objects listen to a topic object at the same time. When the topic object's state changes, all observer objects are notified so that they can automatically update themselves. There are two main roles in the Observer pattern: Subject and Observer. * /
class Observer {
constructor(name){
this.name = name
}
notify(){
console.log(`The ${this.name} has been notified`)}}class Subject {
observers = []
addObserver(observer){
console.log(observer.name, 'is push')
this.observers.push(observer)
}
deleteObserver(observer){
console.log('remove observer: ', observer.name)
this.observers = this.observers.filter(o= >o ! == observer) }notifyObservers(){
console.log('notify')
this.observers.forEach(o= > o.notify())
}
}
Copy the codeinherit
/** * Prototype === new Parent * child.__proto__.constructor === Parent */
function Parent(){
this.name = 'Parent'
}
Parent.prototype.say = function(){
console.log(this.name)
}
function Child(){
}
Child.prototype = new Parent()
var child = new Child()
console.log(child.__proto__ === Child.prototype) // true
console.log(child.__proto__.constructor === Parent) // true
child.say()
Copy the code/** * Borrow constructor inheritance * advantages ** avoids the problem of reference types being shared * Child can pass arguments to Parent * disadvantages * Every time an instance is created, the Parent method is created * child-.__proto__ === child-.prototype * child.__proto__.constructor === Child */
function Parent(name){
this.name = name
this.say = function(){
console.log(this.name)
}
}
function Child(){
Parent.apply(this.arguments)}var child = new Child('child')
console.log(child.__proto__ === Child.prototype) // true
console.log(child.__proto__.constructor === Child) // true
child.say() // child
Copy the code/** * Composite pattern * advantages: * avoids the need for references to be shared * no need to create methods repeatedly * Disadvantages: * Requires more new times */
function Parent(name){
this.name = name
}
Parent.prototype.say = function(){
console.log(this.name)
}
function Child(name){
Parent.apply(this.arguments)
}
Child.prototype = new Parent()
Child.prototype.constructor = Child
var child = new Child('child')
console.log(child.__proto__ === Child.prototype) // true
console.log(child.__proto__.constructor === Child) // true
child.say() // child
Copy the code/** * Prototype inheritance * Defects * Reference type sharing * child.__proto__ === parent * child.__proto__
function CreateObj(o){
function F(){}
F.prototype = o
return new F()
}
var parent = {
name: 'parent'.say: function(){
console.log(this.name)
}
}
var child = CreateObj(parent)
child.say()
console.log(child.__proto__ === parent)
console.log(child.__proto__.constructor === Object)
Copy the code/** * Parasitic inheritance * creates a function that only encapsulates the inheritance process, internally making the enhanced object in some form, and finally returning the object. * /
function CreateObj(o){
function F(){}
F.prototype = o
return new F()
}
var parent = {
name: 'parent'.say: function(){
console.log(this.name)
}
}
var Child = function(o, name){
var clone = CreateObj(o)
clone.name = name
return clone
}
var child = Child(parent, 'child')
child.say()
console.log(child.__proto__ === parent)
console.log(child.__proto__.constructor === Object)
Copy the code/** * Parasitic combinative inheritance * benefits * Calls the constructor of the Parent class only once * avoids creating unnecessary properties on parent-. prototype * the prototype chain remains unchanged; Therefore, instanceof and isPrototypeOf */ can also be used normally
function inherit(Child, Parent){
function F(){}
F.prototype = Parent.prototype
Child.prototype = new F()
Child.prototype.constructor = Child
}
function Parent(name){
this.name = name
}
Parent.prototype.say = function(){
console.log(this.name)
}
function Child(){
Parent.apply(this.arguments)
}
inherit(Child, Parent)
var child = new Child('child')
child.say()
console.log(child.__proto__ === Child.prototype)
console.log(child.__proto__.constructor === Child)
Copy the codecreate object
/* The factory function can take arguments to build an object containing the necessary information. It can be called an infinite number of times. While returning one object at a time advantages: batch generation of similar objects disadvantages: objects point to the same prototype, generated objects cannot recognize each method needs to be created once */
function factory(name, age){
var o = new Object()
o.name = name
o.age = age
o.say = function(){
console.log(`name=The ${this.name}, age=The ${this.age}`)}return o
}
var a = factory('a'.20)
var b = factory('b'.10)
a.say()
b.say()
Copy the code/* The constructor pattern uses constructors to create objects of a particular type to use the new operator advantages: each instance can be identified as a particular type disadvantages: each instance method needs to be created once every time an instance is created */
function create(name, age){
this.name = name
this.age = age
this.say = function(){
console.log(`name=The ${this.name}, age=The ${this.age}`)}}var a = new create('a'.20)
var b = new create('b'.10)
a.say()
b.say()
Copy the code/* Prototype mode: each function has a prototype. You can use the prototype object to share all instances of the object's property methods. Advantages: Methods are not created repeatedly
function Prototype(){
}
Prototype.prototype = {
constructor: Prototype,
name: 'a'.say:function(){
console.log(this.name)
}
}
var a = new Prototype()
var b = new Prototype()
a.say()
b.say()
Copy the code/* The combined pattern constructor works with the prototype pattern. The constructor pattern is used to define instance properties, prototype properties to define methods and shared properties. Advantages the share of the share, the private private disadvantage of the lack of encapsulation */
function Create(name, age){
this.name = name;
this.age = age;
}
Create.prototype.say = function(){
console.log(`name=The ${this.name}, age=The ${this.age}`)}var a = new create('a'.20)
var b = new create('b'.10)
a.say()
b.say()
Copy the code/* Dynamic prototype pattern To solve the problem of separate constructors and prototypes, the dynamic prototype pattern encapsulates information into the constructor and initializes the prototype in the constructor
function CreatePrototype(name, age){
this.name = name
this.age = age
if(typeof this.say ! = ='function'){
CreatePrototype.prototype.say = function(){
console.log(`name=The ${this.name}, age=The ${this.age}`)}}}var a = new CreatePrototype('a'.20)
var b = new CreatePrototype('b'.10)
a.say()
b.say()
Copy the code/* The parasitic constructor pattern creates a function that merely encapsulates the code that created the object and then returns the newly created object
function NewFactory(name, age){
var o = new Object(a); o.name = name; o.age = age; o.say =function () {
console.log(`name=The ${this.name}, age=The ${this.age}`)};return o;
}
var a = new NewFactory('a'.20)
var b = new NewFactory('b'.10)
a.say()
b.say()
Copy the code/* Safe function patterns have no public properties and their methods do not reference this
function StaticCreate(name, age){
var o = new Object()
o.say = function () {
console.log(`name=${name}, age=${age}`)}return o
}
var a = new StaticCreate('a'.20)
var b = new StaticCreate('b'.10)
a.say()
b.say()
Copy the codeinstanceof
function instanceOf(l, r){
while(true) {if(l === null) return false
if(l.__proto__ === r.prototype) return true
l = l.__proto__
}
}
Copy the codeEqual to the judge
function eq(a, b, aStack, bStack){
if(a === b) returna ! = =0 || 1 / a === 1 / b
if(a === null || b === null) return false
if(a ! == a)returnb ! == bvar type = typeof a
if(type ! = ='object'&& type ! = ='function' && typeofb ! = ='object') return false
return deepEq(a, b, aStack, bStack)
}
function deepEq(a, b, aStack, bStack){
var type = Object.prototype.toString.call(a)
if(type ! = =Object.prototype.toString.call(b)) return false
switch (type) {
case '[object Number]':
if(+a ! == +a)return+b ! == +breturn +a === +b && 1 / a === 1 / b
case '[object String]':
case '[object RegExp]':
return ' ' + a === ' ' + b
case '[object Date]':
case '[object Boolean]':
return +a === +b
case '[object Symbol]':
return Symbol.prototype.valueOf.call(a) === Symbol.prototype.valueOf.call(b)
default:
break;
}
var areArrays = type === '[object Array]';
if(! areArrays){if(typeofa ! = ='object' && typeofb ! = ='object') return false
var aCtor = a.constructor
var bCtor = b.constructor
if(aCtor ! == bCtor && ! (typeof aCtor === 'function' && typeof bCtor === 'function' && aCtor instanceof aCtor && bCtor instanceof bCtor)
&& ('constructor' in a && 'constructor' in b)
) return false
}
aStack = aStack || []
bStack = bStack || []
var length = aStack.length
if(length ! == bStack.length)return false
while(length--) if(aStack[length] === a) return bStack[length] === b
aStack.push(a)
bStack.push(b)
if(areArrays){
length = a.length
if(length ! == b.length)return false
while(length--) if(! eq(a[length], b[length], aStack, bStack))return false
}else{
var keys = Object.keys(a)
length = keys.length
if(length ! = =Object.keys(b).length) return false
while(length--) if(! eq(a[keys[length]], b[keys[length]], aStack, bStack))return false
}
aStack.pop()
bStack.pop()
return true
}
Copy the codeduplicate removal
/** * Delete *@param {} [] Array Array to be deduplicated *@param {Boolean} IsSorted Specifies whether to sort *@param {function} Iteratee comparison function *@param {object} Context scope */
function unique(array, isSorted, iteratee, context){
if(typeofisSorted ! = ='boolean'){
context = iteratee
iteratee = isSorted
isSorted = false
}
if(isSorted == true){
iteratee = function(value){ return value }
}else if(typeofiteratee ! = ='function'){
iteratee = function(value){
value = value instanceof RegExp ? value.toString() : value
var key = (typeof value) + JSON.stringify(value)
if(this[key]) return false
this[key] = true
return true
}
}
iteratee = iteratee.bind(context || {})
var result = []
var last
for(var i = 0; i < array.length; i++){
var value = array[i]
var computed = iteratee(value, i, array)
if(isSorted){
if(! i || last ! == computed) result.push(value) last = value }else{
if(computed) result.push(value)
}
}
return result
}
Copy the codeBubble sort
/** After each round of the outermost for loop, the maximum value of the remaining digits is moved to the last digit of the current round, and some neighboring digits are exchanged to become ordered. The total number of comparisons is (n-1)+(n-2)+(n-3)+... + 1 (n - 1) + (n - 2) + (n - 3) +... + 1. This is the equivalent of pairwise comparison of adjacent numbers, and states: "The one who is bigger stands on the right." After n-1n-1 rounds, the numbers are sorted from smallest to largest. * /
/** * time :O(n*n) * space :O(1) * stable *@param {[Number]} Arr Array to be sorted *@returns {[Number]}* /
var bubbleSort = (arr) = > {
let n = arr.length
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if(arr[j] > arr[j + 1]){
swap(arr, j, j + 1)}}}return arr
}
// Improved version of bubble sort: if there is no swap, it will jump out early
var bubbleSort = arr= > {
let n = arr.length
let swapped = true
for (let i = 0; i < n - 1; i++) {
if(! swapped)break
swapped = false
for (let j = 0; j < n - i - 1; j++) {
if(arr[j] > arr[j + 1]){
swap(arr, j, j + 1)
swapped = true}}}return arr
}
// Improved version of bubble sort: record the position of the last exchange
var bubbleSort = arr= > {
let lastIndex = arr.length - 1
let swapped = true
let swappedIndex = 0
while (swapped){
swapped = false
for (let i = 0; i < lastIndex; i++) {
if(arr[i] > arr[i + 1]){
swap(arr, i, i + 1)
swapped = true
swappedIndex = i
}
}
lastIndex = swappedIndex
}
return arr
}
Copy the codeInsertion sort
/** * Insert sort: Insert a new number in the process of swapping with the previous number until it finds its proper place. Exchange method * time :O(n*n) * space :O(1) * stable *@param {[Number]} Arr Array to be sorted */
var InsertSort = function(arr){
for (let i = 1; i < arr.length; i++) {
let j = i
while (j >= 1 && arr[j - 1] > arr[j]){
swap(arr, j, j - 1)
j--
}
}
return arr
}
/** * Insert sort: Insert a new number in the process of swapping with the previous number until it finds its proper place. Insert one time method * time :O(n*n) * space :O(1) * stability *@param {[Number]} Arr Array to be sorted */
var InsertSort = function(arr){
for (let i = 1; i < arr.length; i++) {
let x = arr[i]
let j = i - 1
while (j >= 0 && arr[j] > x){
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = x
}
return arr
}
Copy the codeHill sorting
/** * Hill sort: it is essentially an optimization of insert sort. It takes advantage of the simplicity of insert sort and * overcomes the disadvantage that insert sort only swaps two adjacent elements at a time. The basic idea is: * Divide the array to be sorted into multiple subarrays at certain intervals, and insert sort each group separately. * By interval, we don't mean to take a continuous array, but rather to take a set of values at a certain interval per jump * Narrow the interval for the next round * For the last round, take an interval of 11, which is the same as using insertion sort directly. * Time :O(n)~O(n*n) is generally up to O(1.3*n) * space :O(1) * unstable *@param {[Number]} Arr Array to be sorted */
var ShellSort = arr= > {
let maxGap = 1
let n = arr.length
while (maxGap <= n / 3){
maxGap = maxGap * 3 + 1
}
for (let gap = maxGap; gap > 0; gap = (gap - 1) / 3) {
for (let i = gap; i < n; i++) {
let curr = arr[i]
let preIndex = i - gap
while (preIndex >= 0 && curr < arr[preIndex]){
arr[preIndex + gap] = arr[preIndex]
preIndex -= gap
}
arr[preIndex + gap] = curr
}
}
return arr
}
Copy the codeSelection sort
/** * select sort: double loop through the group, each round of comparison, find the lowest subscript, swap it to the first. * Time :O(n*n) * Space :O(1) * unstable *@param {[Number]} Arr Array to be sorted */
var SelectSort = (arr) = > {
let n = arr.length
let min
for (let i = 0; i < n - 1; i++) {
min = i
for (let j = i + 1; j < n; j++) {
if(arr[j] < arr[min]) {
min = j
}
}
swap(arr, i, min)
}
return arr
}
/** * Select sort improvement: double loop through the group, each round of comparison, find the lowest subscript, swap it to the first. Find the largest coordinate in the last bit * Time :O(n*n) * Space :O(1) * unstable *@param {[Number]} Arr Array to be sorted */
var SelectSort = (arr) = > {
let n = arr.length
let min
let max
for (let i = 0; i < n >> 1; i++) {
min = i
max = i
for (let j = i + 1; j < n - i; j++) {
if(arr[j] < arr[min]) {
min = j
}
if(arr[j] > arr[max]) {
max = j
}
}
if(arr[min] == arr[max]) break
swap(arr, i, min)
Arr [I] and arr[min] have been swapped, so update the value of Max.
if(i == max) max = min
swap(arr, max, n - i - 1)}return arr
}
Copy the codeMerge sort
/** * Merge sort: split an array into N smaller arrays, and then merge the smaller arrays into an ordered array * time: O(N logn) * space: O(N) * stability *@param {*} Arr Array to be sorted */
var MergeSort = function(arr){
if(! arr.length)return
let result = mergeSort(arr, 0 , arr.length - 1)
for (let i = 0; i < arr.length; i++) {
arr[i] = result[i]
}
return arr
}
/** * Binary split array *@param {[Number]} arr
* @param {Number} start
* @param {Number} end
* @returns * /
var mergeSort = function(arr, start, end){
if(start == end) return [arr[start]]
let mid = Math.floor((start + end) / 2)
let left = mergeSort(arr, start, mid)
let right = mergeSort(arr, mid + 1, end)
return merge(left, right)
}
/** * Merge two ordered arrays *@param {[Number]} arr1
* @param {[Number]} arr2
*/
var merge = function(arr1, arr2){
let result = new Array(arr1.length + arr2.length)
let i = 0
let j = 0
while (i < arr1.length && j < arr2.length){
result[i + j] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++]
}
while(i < arr1.length){
result[i + j] = arr1[i++]
}
while(j < arr2.length){
result[i + j] = arr2[j++]
}
return result
}
/** * Merge sort space optimization version: split an array into N small arrays, and then merge the small arrays one by one into an ordered array * time: O(N logn) * space: O(N) * stable *@param {*} Arr Array to be sorted */
var MergeSort = function(arr){
if(! arr.length)return
let result = new Array(arr.length)
mergeSort(arr, 0 , arr.length - 1, result)
return arr
}
/** * Binary split array *@param {[Number]} arr
* @param {Number} start
* @param {Number} end
* @returns * /
var mergeSort = function(arr, start, end, result){
if(start == end) return
let mid = Math.floor((start + end) / 2)
mergeSort(arr, start, mid, result)
mergeSort(arr, mid + 1, end, result)
merge(arr, start, end, result)
}
/** * Merge two ordered arrays *@param {[Number]} arr1
* @param {[Number]} arr2
*/
var merge = function(arr, start, end, result) {
let end1 = Math.floor((start + end) / 2)
let start2 = end1 + 1
let end2 = end
let index1 = start
let index2 = start2
while(index1 <= end1 && index2 <= end2) {
result[index1 + index2 - start2] = arr[index1] <= arr[index2] ? arr[index1++] : arr[index2++]
}
while(index1 <= end1){
result[index1 + index2 - start2] = arr[index1++]
}
while(index2 <= end2){
result[index1 + index2 - start2] = arr[index2++]
}
while(start <= end){
arr[start] = result[start++]
}
return arr
}
Copy the codeQuick sort
/* * @Author: xiaohuolong * @Date: 2021-03-29 09:05:24 * @LastEditors: xiaohuolong * @LastEditTime: 2021-05-14 20:36:10 * @FilePath: /js-demo/algorithm/Sort/QuickSort.js */
/** * partition function: from the beginning, double pointer partition *@param {*} Array arr *@param {*} P left pointer *@param {*} Q Right pointer *@returns * /
var partition = (arr, p, q) = > {
let x = arr[p]
let i = p
let j = p + 1
for (j; j <= q; j++) {
if(arr[j] < x){
swap(arr, ++i, j)
}
}
swap(arr, i, p)
return i
}
/** * partition function: from the beginning, double pointer partition *@param {*} Array arr *@param {*} P left pointer *@param {*} Q Right pointer *@returns * /
var partition = (arr, p, q) = > {
// Take the first number as the base
let pivot = arr[p]
// Partition from the second number
let i = p + 1
/ / right border
let j = q
// Exit the loop on encounter
while (i < j){
// Find the first position that is greater than the cardinality
// console.log(arr.join(','), i, j);
while (i < j && arr[i] <= pivot) i++
// console.log(i, arr[i], pivot);
if(i ! = j){// Switch to the right partition so that the left partition is less than or equal to the cardinality and the right partition is greater than or equal to the cardinality
swap(arr, i, j)
j--
}
}
// console.log('while-end')
// console.log(arr.join(','))
// If the two Pointers are equal, compare arr[j] pivot separately
if(i == j && arr[j] > pivot) j--
// Swap the base with the middle tree
// console.log(j, p, arr[p], arr[j]);
if(j ! = p) swap(arr, p, j)// console.log(arr.join(','))
// Return the middle index
return j
}
Partition function: partition arr from p to q, leaving the left area smaller than the cardinality, leaving the right area larger than the cardinality, and return the subscript * of the middle value@param {*} Array arr *@param {*} P left pointer *@param {*} Q Right pointer *@returns * /
var partition = (arr, p, q) = > {
// Take the first number as the base
let pivot = arr[p]
// Partition from the second number
let i = p + 1
/ / right border
let j = q
// Exit the loop on encounter
while (i < j){
// Find the first position that is greater than the cardinality
// console.log(arr.join(','), i, j);
while (i < j && arr[i] <= pivot) i++
while (i < j && arr[j] >= pivot) j--
// console.log(i, arr[i], arr[j], pivot);
if(i < j){
// Switch to the right partition so that the left partition is less than or equal to the cardinality and the right partition is greater than or equal to the cardinality
swap(arr, i, j)
i++
j--
}
}
// console.log('while-end')
// console.log(arr.join(','))
// If the two Pointers are equal, compare arr[j] pivot separately
if(i == j && arr[j] > pivot) j--
// Swap the base with the middle tree
swap(arr, p, j)
// console.log(arr.join(','))
// Return the middle index
return j
}
Partition function: partition arr from p to q, leaving the left area smaller than the cardinality, leaving the right area larger than the cardinality, and return the subscript * of the middle value@param {*} Array arr *@param {*} P left pointer *@param {*} Q Right pointer *@returns * /
var partition = (arr, p, q) = > {
let pivot = arr[p]
let i = p + 1
let j = q
while (i < j){
while (i < j && arr[i] <= pivot) i++
while (i < j && arr[j] >= pivot) j--
if(i ! = j){ swap(arr, i, j) i++ j-- } }if(i == j && arr[j] >= pivot) j--
swap(arr, p, j)
return j
}
/** * The basic idea of the quicksort algorithm is: * Take a number from the array and call it the base (pivot) * Go through the array, putting the larger number to its right and the smaller number to its left. After the traversal is complete, the array is divided into two regions * Treat the left and right regions as two arrays and repeat the first two steps until the sorting is complete * Time complexity: O(nlogn ~ n*n) * Space complexity: O(logn ~ n) * Stable: unstable *@param {*} arr
* @param {*} p
* @param {*} q
* @returns * /
var sortArray = function(arr){
shuffle(arr)
return QuickSort(arr, 0, arr.length - 1)}var QuickSort = (arr, p, q) = > {
if(p < q){
// Partition the array and get the index of the intermediate value
const r = partition(arr, p, q)
// Sort the left area quickly
QuickSort(arr, p, r - 1)
// Quicksort the right area
QuickSort(arr, r + 1, q)
}
return arr
}
/** * optimization: shuffle the sorted array using the shuffle algorithm *@return {number[]}* /
var shuffle = function(nums) {
let n = nums.length
A random integer in [n, m]
var randOne = function(n, m) {
return Math.floor(Math.random() * (m - n + 1)) + n;
};
for (let i = 0; i < n; i++) {
let rand = randOne(i, n - 1)
swap(nums, i, rand)
}
return nums
};
/ / exchange
var swap = function(arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
};
Copy the codeHeap sort
/** * heap: a complete binary tree with one of the following conditions: * The value of the root node ≥ the value of the child nodes, such a heap is called the maximum heap, or large top heap; * If the value of the root node is less than or equal to the value of the child nodes, the heap is called the minimum heap, or the small top heap. * The sorting process is as follows: * Build a large top heap with a sequence of numbers, take the top number of the heap; * Adjust the remaining numbers to create a new big top heap, and take out the top number of the heap again; * Loop to complete the entire sort. * Time: O(nlogn) * Space: O(n) * unstable */
class Heap {
constructor(size, handle){
this.list = new Array(size + 1)
this.list[0] = size
this.handle = handle || this.handle
this.realSize = 0
}
handle(a, b){
return a > b
}
getParentIndex(i){
return Math.floor(i / 2)}getLeftChildIndex(i){
return i * 2
}
getRightChildIndex(i){
return i * 2 + 1
}
swap(i, j){
let temp = this.list[i]
this.list[i] = this.list[j]
this.list[j] = temp
}
heapUp(i){
// 1. Find the parent node of the node and determine whether to switch
let j = this.getParentIndex(i)
while(this.list[i] ! = =undefined && this.handle(this.list[i], this.list[j]) && j >= 1) {this.swap(i, j)
i = j
j = this.getParentIndex(i)
}
}
heapDown(i){
let n = Math.floor(this.realSize / 2)
while(i < this.realSize && i <= n){
let l = this.getLeftChildIndex(i)
let r = this.getRightChildIndex(i)
let left = this.list[l]
let right = this.list[r]
let curr = this.list[i]
let j = i
// console.log(curr, left, right)
if(left === undefined && right === undefined) break
if(right === undefined && this.handle(curr, left)) break
if(this.handle(curr, left) && this.handle(curr, right)) break
if(left === undefined) j = r
else if(right === undefined) j = l
else{
if(this.handle(left, right)){
j = l
}else{
j = r
}
}
this.swap(i, j)
i = j
}
}
add(val){
if(this.realSize >= this.list[0]) {if(this.handle(this.peek(), val)){
this.pop()
}else{
return}}this.realSize++
this.list[this.realSize] = val
// Float up after insertion
this.heapUp(this.realSize)
}
pop(){
let head = this.list[1]
this.list[1] = this.list[this.realSize]
this.list[this.realSize--] = undefined
this.heapDown(1)
return head
}
peek(){
return this.list[1] != undefined ? this.list[1] : -1
}
size(){
return this.realSize
}
heapify(list = [], handle){
let size = list.length
this.list = new Array(size + 1)
this.list[0] = size
this.handle = handle || this.handle
this.realSize = 0
for (let i = 0; i < size; i++) {
this.add(list[i])
}
}
}
class MinHeap extends Heap{
constructor(size, handle){
super(size, handle)
}
handle(a, b){
return a < b
}
}
var sortArray = function(arr){
let n = arr.length
let heap = new MinHeap(n)
heap.heapify(arr)
for (let i = 0; i < n; i++) {
arr[i] = heap.pop()
}
return arr
}
Copy the codeCount sorting
/** * Count sort * The count sort is done n or K times each time, so the count sort time is O(n + k), k is the range size of the data. * The space used is mainly the count array of length K and the result array of length n, so the space complexity is also O(n + k) * stable * count sort is only suitable for scenarios with small data range *@param {*} arr
*/
var CountingSort = (arr) = > {
// Judge null and prevent array from crossing bounds
if (arr == null || arr.length <= 1) return arr;
// Find maximum and minimum
let max = arr[0]
let min = arr[0]
for (let i = 1; i < arr.length; i++) {
max = Math.max(max, arr[i])
min = Math.min(min, arr[i])
}
let range = max - min + 1
// Create a range array with subscripts 0 to 8 corresponding to numbers 1 to 9
let counting = new Array(range).fill(0)
// Iterate over each element in the ARR
for (const x of arr) {
// Count the number of occurrences of each integer to the position of the corresponding index in the count array
counting[x-min] += 1
}
// Record the total number of the previous numbers smaller than oneself
let preCounts = 0
for (let i = 0; i < counting.length; i++) {
// Calculate counting as the starting subscript position of the current number in the result. Position = the total number of smaller numbers in front of you.
preCounts += counting[i]
// The current number is less than the next number, add to the preCounts
counting[i] = preCounts - counting[i]
}
let result = new Array(arr.length)
for (const x of arr) {
// Counting [x-1] Specifies the index of each element in the result array
let index = counting[x - min]
result[index] = x
// Update counting[x-1] to point to the next index of each element
counting[x-min]+=1
}
for (let i = 0; i < arr.length; i++) {
arr[i] = result[i]
}
return arr
}
Copy the codeRadix sort
/** * Base sort * Base sort can be divided into three steps: MaxDigit * Get the cardinality of each number in the array * Walk through the maxDigit array, sorting it by cardinality each round * time complexity O(d(n +k)) * Space complexity O(n+k) * stable *@param {number[]} arr
*/
var radixSort = function(arr){
if(arr.length <= 1) return arr
let max = -Infinity
for (const x of arr) {
max = Math.max(max, Math.abs(x))
}
let maxDigit = 0;
while(max ! =0) {
maxDigit++;
max = Math.floor(max / 10);
}
let counting = new Array(20).fill(0)
let result = new Array(arr.length)
let dev = 1
for (let i = 0; i < maxDigit; i++) {
// console.log(arr)
for (const x of arr) {
let radix = (dev <= Math.abs(x) ? parseInt(x / dev) % 10 : 0) + 9
// console.log(radix, x)
counting[radix]++
}
// console.log(counting)
for (let j = 1; j < counting.length; j++) {
counting[j] += counting[j - 1]}for (let j = arr.length - 1; j >= 0; j--){
let radix = (dev <= Math.abs(arr[j]) ? parseInt(arr[j] / dev) % 10 : 0) + 9
result[--counting[radix]] = arr[j]
}
// console.log(result)
for (let j = 0; j < result.length; j++) {
arr[j] = result[j];
}
counting.fill(0)
dev *= 10
}
return arr
}
Copy the codediff
// react
function diff1(prev, next){
let container = prev.slice()
let nextIndex = {}
let prevIndex = {}
let prevLength = prev.length
let nextLength = next.length
let lastIdx = 0
// Generate a mapping table for easy lookup
for(let i = 0; i < prevLength; i++) prevIndex[prev[i].key] = i
for(let i = 0; i < nextLength; i++){
// 1. Iterate next to get nextNode, position I
let nextNode = next[i]
nextIndex[nextNode.key] = i
// 3. If a node is found and its position is j, update the node and determine whether j is less than lastIdx (lastIdx = 0). If not, then lastIdx = j
let j = prevIndex[nextNode.key]
if(j ! = =undefined){
patch(prev[j], nextNode)
// 4. If less than lastIdx, insert the node after next[i-1]
if(j < lastIdx){
container = insertBefore(next[i - 1], nextNode, container, 1)}else{
lastIdx = j
}
}else{
Nextnode.key = nextnode.key; next[i-1] = next[i-1]
container = insertBefore(next[i - 1], nextNode, container, 1)}}// 5. After traversing next, traverse prev. If the node is not in next, delete the node
for(let p of prev){
if(nextIndex[p.key] === undefined){
remove(p, container)
}
}
return container
}
Copy the code// vue2
function diff2(prev, next){
let container = prev.slice()
// 1. Declare four variables prevStart, prevEnd, nextStart, and nextEnd to take out prevStartNode, prevEndNode, nextStartNode, and nextEndNode
let prevStart = 0
let nextStart = 0
let prevEnd = prev.length - 1
let nextEnd = next.length - 1
let prevStartNode = prev[prevStart]
let prevEndNode = prev[prevEnd]
let nextStartNode = next[nextStart]
let nextEndNode = next[nextEnd]
let prevIndex = {}
for(let i = 0; i < prev.length; i++) prevIndex[prev[i].key] = i
// 2. Loop, condition does not meet prevStart <= prevEnd && nextStart <= nextEnd jump loop
while(prevStart <= prevEnd && nextStart <= nextEnd){
// 3. PrevStartNode or prevEndNode does not exist, prevStart++, prevEnd--, back to 2
if(! prevStartNode){ prevStartNode = prev[++prevStart] }else if(! prevEndNode){ prevEndNode = prev[--prevEnd] }else if(prevStartNode.key === nextStartNode.key){
// 4. Prevstartnode. key == nextstartnode. key, equal to update node, prevStart++ nextStart++, back to 2
patch(prevStartNode, nextStartNode)
prevStartNode = prev[++prevStart]
nextStartNode = next[++nextStart]
}else if(prevEndNode.key === nextEndNode.key){
// 5. Prevendnode. key == NexTendNode. key, equal to update node, prevEnd-- nextEnd --, return to 2
patch(prevEndNode, nextEndNode)
prevEndNode = prev[--prevEnd]
nextEndNode = next[--nextEnd]
}else if(prevStartNode.key === nextEndNode.key){
// 6.prevstartnode. key == nextendnode. key, equals to update node, insert prevStartNode before prevendnode. next, prevStart++ nextEnd--, return to 2
patch(prevStartNode, nextEndNode)
container = insertBefore(prevEndNode, prevStartNode, container, 1)
prevStartNode = prev[++prevStart]
nextEndNode = next[--nextEnd]
}else if(prevEndNode.key === nextStartNode.key){
// 7. Prevendnode. key == nextstartnode. key, update node, insert prevEndNode before prevStartNode, prevEnd-- nextStart++, back to 2
patch(prevEndNode, nextStartNode)
container = insertBefore(prevStartNode, prevEndNode, container)
prevEndNode = prev[--prevEnd]
nextStartNode = next[++nextStart]
}else{
NextStartNode ++, prev[J], prev[J], prev[J], prev[J], prev[J] Back to 2
let j = prevIndex[nextStartNode.key]
if(j ! = =undefined){
patch(prev[j], nextStartNode)
prev[j] = undefined
}
container = insertBefore(prevStartNode, nextStartNode, container)
nextStartNode = next[++nextStart]
}
}
if(prevEnd < prevStart){
// 9. If prevEnd < prevStart proves that a new node has not been processed after the end of the loop, insert the node from nextStart until newEnd, each time before next[newEnd + 1]
let ref = next[nextEnd + 1] | |null
while(nextStart <= nextEnd){
container = insertBefore(ref, next[nextStart++], container)
}
}else if(nextEnd < nextStart){
// 10. If nextEnd < newStart proves that a node has been removed and has not been processed, remove the node from prevStart until prevEnd
while(prevStart <= prevEnd){
remove(prev[prevStart++], container)
}
}
return container
}
Copy the code// vue3
function diff3(prev, next){
let container = prev.slice()
// 1.j indicates the position of the current match. The initial value is 0
let j = 0
let prevEnd = prev.length - 1
let nextEnd = next.length - 1
let prevNode = prev[j]
let nextNode = next[j]
J / / 2. Start matching the same elements, if prev [j]. Key = = next [j]. The key, the updated j++ if j > prevEnd | | j > nextEnd jump out ahead of time
while(prevNode && nextNode && prevNode.key === nextNode.key){
patch(prevNode, nextNode)
j++
if(j > prevEnd || j > nextEnd) break
prevNode = prev[j]
nextNode = next[j]
}
// 3. J stops at the first difference after matching the previous identical elements
prevNode = prev[prevEnd]
nextNode = next[nextEnd]
PrevEnd and nextEnd / / 4. Start from the back to find the same suffix, updated prevEnd - nextEnd - if j > prevEnd | | j > nextEnd jump out ahead of time
while(prevNode && nextNode && prevNode.key === nextNode.key){
patch(prevNode, nextNode)
prevEnd--
nextEnd--
if(j > prevEnd || j > nextEnd) break
prevNode = prev[prevEnd]
nextNode = next[nextEnd]
}
// console.log(j, prevEnd, nextEnd)
// console.log(container, prev, next)
// 5. At this point, the same prefix and suffix have been updated
if(j > prevEnd && j <= nextEnd){
// if j > prevEnd && j <= nextEnd, next inserts element before [j, nextEnd + 1]
let ref = next[nextEnd + 1] | |null
while(j <= nextEnd){
container = insertBefore(ref, next[j++], container)
}
}else if(j > nextEnd && j <= prevEnd){
// 7. If j > nextEnd && j <= prevEnd, prev is deleted from [j, prevEnd]
while(j <= prevEnd){
remove(prev[j++], container)
}
}else if(j <= nextEnd){
// 8. If neither of the preceding two conditions exists, then there are nodes in the [j, prevEnd] segment with the length of nextLeft = nextEnd -j + 1
let nextLeft = nextEnd - j + 1
// 9. Initialize an auxiliary array source length nextLeft Default value -1, patched = 0, move = false, pos = 0
let source = new Array(nextLeft).fill(-1)
let pos = 0
let patched = 0
let move = false
let keyIndex = {}
// 10. Iterate next, from j to nextEnd, and generate a key-i mapping table keyIndex
for(let i = j; i <= nextEnd; i++) keyIndex[next[i].key] = i
// 11. Iterate over prev from j to prevEnd
for (let i = j; i <= prevEnd; i++) {
let prevNode = prev[i]
// 12. If patched is larger than nextLeft, the same elements are retrieved from prev and the following elements are to be deleted. Delete the elements directly
if(patched < nextLeft){
let k = keyIndex[prevNode.key]
K = keyIndex[prev[I]], if k does not exist, this node does not exist in next, delete it directly
if(k ! = =undefined) {Next [k]. Key == prev[I]. Key, patched++, source[k - j] = I, if k < pos, prev[I] = true, otherwise pos = k
patch(prevNode, next[k])
source[k - j] = i
patched++
if(k < pos){
move = true
}else{
pos = k
}
}else{
remove(prevNode, container)
}
}else{
remove(prevNode, container)
}
}
// console.log(source)
// 15. Check whether move is true
if(move){
// 17. If true, an out-of-order/new situation occurs in this range
Seq = lis(source) j = seq.length-1
let seq = lis(source)
let k = seq.length - 1
for(let i = nextLeft - 1; i >= 0; i--){
if(source[i] === -1|| i ! == seq[k]){Next [pos + 1] next[pos + 1] next[pos + 1] next[pos + 1]
// 20. If I == seq[j], then we need to move the node, pos = j + I, insert next[pos] in prev before next[pos + 1] in prev
let pos = j + i
container = insertBefore(next[pos + 1] | |null, next[pos], container)
}else{
// 21. Other information, J --
k--
}
// console.log(container)}}else{
Next [pos] next[pos + 1] next[pos + 1] next[pos + 1]
for(let i = nextLeft - 1; i >= 0; i--){
if(source[i] === -1) {let pos = j + i
container = insertBefore(next[pos + 1] | |null, next[pos], container)
}
}
}
}
return container
}
function lis(arr) {
const p = arr.slice()
const result = [0]
let i
let j
let u
let v
let c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
if(arrI ! = =0) {
j = result[result.length - 1]
if (arr[j] < arrI) {
p[i] = j
result.push(i)
continue
}
u = 0
v = result.length - 1
while (u < v) {
c = ((u + v) / 2) | 0
if (arr[result[c]] < arrI) {
u = c + 1
} else {
v = c
}
}
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result
}
Copy the code