耿直咸鱼

的45°人生

0%

Posted on Edited on In , Symbols count in article: 8.8k Reading time ≈ 8 mins.

回顾

定义类的方式

  • 类声明
1
class Person{}

类声明与函数声明不同之处在于：

  • 函数声明有声明提前，类声明没有

  • 函数受函数作用域限制，而类受块作用域限制

1
2
3
4
5
6
7
{
    function fn() {}
    class ClassFn{}
}

console.log(fn);   // fn() {}
console.log(ClassFn);   // Uncaught ReferenceError: ClassFn is not defined
  • 类表达式
1
const Animal = class{};

类表达式的名称是可选的

在把类表达式赋值给变量后，可以通过name 属性取得类表达式的名称字符串

但不能在类表达式作用域外部访问这个标识符

1
2
3
4
5
6
7
8
9
10
11
12
let Person = class PersonName {
	identify() {
		console.log(Person.name, PersonName.name);
	}
}

let p = new Person();

p.identify(); // PersonName PersonName

console.log(Person.name); // PersonName
console.log(PersonName); // ReferenceError: PersonName is not defined

类的构成

类可以包含构造函数方法、实例方法、获取函数、设置函数、静态类方法，但都不是必须的，空的类定义照样有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 空类定义，有效
class Foo {}
// 有构造函数的类，有效
class Bar {
	constructor() {}
}
// 有获取函数的类，有效
class Baz {
	get myBaz() {}
}
// 有静态方法的类，有效
class Qux {
	static myQux() {}
}

类构造函数

constructor关键词用于在类定义块内部创建类的构造函数（constructor会告诉解释器，在new操作符的时候应该调用这个函数创建新的实例）

构造函数的定义不是必需的，不定义构造函数相当于将构造函数定义为空函数

实例化

使用new 操作符实例化Person 的操作等于使用new 调用其构造函数

补课：new操作符会发生什么？包含手写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Animal {}

class Person {
    constructor() {
        console.log('person ctor');
    }
}

class Vegetable {
    constructor() {
        this.color = 'orange';
    }
}

let a = new Animal();

let p = new Person();   // person ctor

let v = new Vegetable();
console.log(v.color);   // orange
  • 类实例化时传入的参数会用作构造函数的参数（如果不需要参数，则类名后面的括号也是可选的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Person {
	constructor(name) {
		console.log(arguments.length);
		this.name = name || null;
	}
}

let p1 = new Person; // 0
console.log(p1.name); // null

let p2 = new Person(); // 0
console.log(p2.name); // null

let p3 = new Person('Jake'); // 1
console.log(p3.name); // Jake

  • 默认情况下，类构造函数会在执行之后返回this 对象

    构造函数返回的对象会被用作实例化的对象，如果没有什么引用新创建的this对象，那么这个对象会被销毁

    不过，如果返回的不是this对象，而是其他对象，那么这个对象不会通过instanceof 操作符检测出跟类有关联，因为这个对象的原型指针并没有被修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Person {
	constructor(override) {
		this.foo = 'foo';
		if (override) {
			return {
				bar: 'bar'
			};
		}
	}
}

let p1 = new Person(),
p2 = new Person(true);

console.log(p1); // Person{ foo: 'foo' }
console.log(p1 instanceof Person); // true

console.log(p2); // { bar: 'bar' }
console.log(p2 instanceof Person); // false

// 因为p2返回的不是this对象，而是 {bar: 'bar'}， 因此instance检测不出p2和Person类的关联

  • 类构造函数与构造函数的主要区别是：调用类构造函数必须使用new 操作符

    普通构造函数如果不使用new调用，那么就会以全局的this（通常是window）作为内部对象

    调用类构造函数时如果忘了使用new则会抛出错误

1
2
3
4
5
6
7
function Person() {}
class Animal {}

// 把window 作为this 来构建实例
let p = Person();
let a = Animal();
// TypeError: class constructor Animal cannot be invoked without 'new'
  • 实例化类构造函数后可以在实例上引用构造函数
1
2
3
4
5
6
7
8
9
10
class Person {}

// 使用类创建一个新实例
let p1 = new Person();

p1.constructor();
// TypeError: Class constructor Person cannot be invoked without 'new'

// 使用对类构造函数的引用创建一个新实例
let p2 = new p1.constructor();

类是特殊的函数

  • typeof检测类为function
1
2
3
class Person{}

typeof Person    //  'function'
  • 类有prototype属性，原型有constructor属性指向类自身
1
2
3
4
class Person {}

console.log(Person.prototype);                         // {constructor: f()}
console.log(Person.prototype.constructor === Person)    // true
  • instaceof操作符可以用于检查构造函数的原型是否存在于实例的原型链中
1
2
3
4
5
class Person{}

let p = new Person();

console.log(p instanceof Person);   // true
  • 类本身在使用new操作符时会被当成构造函数，但是类的constructor方法不会被当作构造函数，因此instanceof操作符会返回false，但是创建实例时直接将类构造函数当作普通构造函数来使用，instanceof操作符返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Person{}

let p1 = new Person()         // 直接将类使用构造函数调用

console.log(p1.constructor === Person)  // true
console.log(p1 instanceof Person)  // true
console.log(p1 instanceof Person.constructor);  // false   类的constructor方法不会被当作构造函数

let p2 = new Person.constructor();    // 直接将类构造函数当作普通构造函数来使用，就满足普通构造函数的特点了

console.log(p2.constructor === Person)  // false
console.log(p2 instanceof Person)  // false
console.log(p2 instanceof Person.constructor);  // true

/*
	通俗来说，谁调用new操作符生成实例的，那么谁就是实例的构造函数
	实例.constructor === 谁
	实例 instanceof 谁 === true
*/
  • 类可以作为参数传递
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 类可以像函数一样在任何地方定义，比如在数组中
let classList = [
	class {
		constructor(id) {
			this.id_ = id;
			console.log(`instance ${this.id_}`);
		}
	}
];

function createInstance(classDefinition, id) {
	return new classDefinition(id);
}

let foo = createInstance(classList[0], 3141); // instance 3141
  • 与立即调用函数类似，类可以立即实例化
1
2
3
4
5
6
7
let p = new class Person {
    constructor(name) {
        console.log(name);
    }
} ('Katrina');    // Katrina

console.log(p);   // Person {}

实例、原型和类成员

实例成员

  • 每个实例都对应着一个唯一的成员对象，这意味着所有成员都不会在原型上共享
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Person {
    constructor() {
        this.name = 'Katrina';
        this.age = 18;
        this.sayName = function() {
            console.log(this.name);
        };
        this.friends = ['Kate', 'Lisa'];
    }
}

let p1 = new Person();
let p2 = new Person();

p1.sayName();  // 'Katrina'
p2.sayName();  // 'Katrina'

console.log(p1.name === p2.name); // false
console.log(p1.sayName === p2.sayName); // false
console.log(p1.friends === p2.friends); // false

p1.name = p1.friends[0];
p2.name = p2.friends[1];

p1.sayName();  // 'Kate'
p2.sayName();  // 'Lisa'

原型方法和访问器

为了在实例间共享方法，类定义语法把在类块中定义的方法作为原型方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Person {
    constructor() {
        this.name = 'Katrina';
        this.age = 18;
        // 添加到this 的所有内容都会存在于不同的实例上
        this.sayName = function() {
            console.log(this.name);
        };
        this.friends = ['Kate', 'Lisa'];
    }
    
    // 在类块中定义的所有内容都会定义在类的原型上
    sayHello() {
            console.log('Hello');
        };
}

Person.prototype.sayHello();  // Hello

let p1 = new Person();
let p2 = new Person();

console.log(p1.sayHello === p2.sayHello);   // true
  • 可以把方法定义在类构造函数中或者类块中，但不能在类块中给原型添加原始值或对象作为成员数据
1
2
3
4
5
class Person {
    name: 'Kate';
}

// Uncaught SyntaxError: Unexpected identifier
  • 类方法等同于对象属性，因此可以使用字符串、符号或计算的值作为键
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const symbolKey = Symbol('symbolKey');

class Person {
	stringKey() {
		console.log('invoked stringKey');
	}
	[symbolKey]() {
		console.log('invoked symbolKey');
	}
	['computed' + 'Key']() {
		console.log('invoked computedKey');
	}
}

let p = new Person();

p.stringKey(); // invoked stringKey
p[symbolKey](); // invoked symbolKey
p.computedKey(); // invoked computedKey
  • 类定义也支持获取和设置访问器。语法与行为跟普通对象一样
1
2
3
4
5
6
7
8
9
10
11
12
class Person {
    set name(newName) {
        this.name_ = newName;
    }
    get name() {
        return this.name_;
    }
}

let p = new Person();
p.name = 'Katrina';
console.log(p.name);   // 'Katrina'

静态类方法

可以在类上定义静态方法

这些方法通常用于执行不特定于实例的操作，也不要求存在类的实例

与原型成员类似，静态成员每个类上只能有一个

静态类成员在类定义中使用static关键字作为前缀

在静态成员中，this引用类自身，而构造函数的this是指向实例的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Person {
    constructor() {
        // 添加到this	的所有内容都会存在于不同的实例上
		this.locate = () => console.log('instance', this);
    }
    
    // 定义在类的原型对象上
	locate() {
		console.log('prototype', this);
	}
    
	// 定义在类本身上
	static locate() {
        // this指向Peron类本身
		console.log('class', this); 
	}
}

let p = new Person();

p.locate();    // instance Perons{}
Person.protype.locate();  // prototype {constructor: ... }
Person.locate(); // class, class Person {}
  • 静态类方法适合作为实例工厂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person {
	constructor(age) {
	this.age_ = age;
	}
    
	sayAge() {
		console.log(this.age_);
	}
    
	static create() {
	// 使用随机年龄创建并返回一个Person 实例
		return new Person(Math.floor(Math.random()*100));
	}
}

console.log(Person.create()); // Person { age_: ... }

非函数原型和类成员

  • 虽然类定义并不显式支持在原型或类上添加成员数据，但在类定义外部，可以手动添加
1
2
3
4
5
6
7
8
9
10
11
12
13
class Person {
	sayName() {
		console.log(`${Person.greeting} ${this.name}`);
	}
}

// 在类上定义数据成员
Person.greeting = 'My name is';

// 在原型上定义数据成员
Person.prototype.name = 'Jake';
let p = new Person();
p.sayName(); // My name is Jake

迭代器与生成器方法

  • 类定义语法支持在原型和类本身上定义生成器方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Person {
    // 在原型上定义生成器方法
	*createNicknameIterator() {
		yield 'Jack';
		yield 'Jake';
		yield 'J-Dog';
	}
    
	// 在类上定义生成器方法
	static *createJobIterator() {
		yield 'Butcher';
		yield 'Baker';
		yield 'Candlestick maker';
	}
}

let jobIter = Person.createJobIterator();
console.log(jobIter.next().value); // Butcher
console.log(jobIter.next().value); // Baker
console.log(jobIter.next().value); // Candlestick maker

let p = new Person();
let nicknameIter = p.createNicknameIterator();
console.log(nicknameIter.next().value); // Jack
console.log(nicknameIter.next().value); // Jake
console.log(nicknameIter.next().value); // J-Dog
  • 因为支持生成器方法，所以可以通过添加一个默认的迭代器，把类实例变成可迭代对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person {
	constructor() {
		this.nicknames = ['Jack', 'Jake', 'J-Dog'];
	}
    
	*[Symbol.iterator]() {
		yield *this.nicknames.entries();
	}
}

let p = new Person();
for (let [idx, nickname] of p) {
	console.log(nickname);
}


  • 或者可以只返回迭代器实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Person {
	constructor() {
		this.nicknames = ['Jack', 'Jake', 'J-Dog'];
	}
    
	[Symbol.iterator]() {
		return this.nicknames.entries();
	}
}

let p = new Person();

for (let [idx, nickname] of p) {
	console.log(nickname);
}
// Jack
// Jake
// J-Dog

Posted on Edited on In , Symbols count in article: 7.3k Reading time ≈ 7 mins.

冒泡排序

冒泡排序是通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

算法思路

（以升序为例）

  • 比较相邻元素，初始为索引为0和索引为1的元素，如果第一个比第二个大，就交换这两个元素
  • 对每一对相邻元素重复同样的工作，直到最后一对，索引为arr.length - 2 和 arr.length - 1，这样 arr.length - 1索引处的元素将会是最大的
  • 重复步骤1和2，得到索引为arr.length - 2为剩余元素中最大的
  • 重复步骤1-3，直到排序完成

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSort(arr) {
    for (let i = arr.length; i > 0; i--) {    // 用i来设置最后一组的边界
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[j-1]) {      // 如果顺序不对就交换
                [arr[j], arr[j-1]] = [arr[j-1], arr[j]];   // 交换
            }
        }
    }
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
bubbleSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： O(1)
		
	稳定性分析：冒泡排序并不会破坏元素的相对位置
		稳定
*/

代码优化

  • 外层优化：在某一层循环的时候并没有发生交换，说明前面已经全部有序，不需要再执行下去了，直接退出

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    function bubbleSortA(arr) {
        for (let i = arr.length; i > 0; i--) {
            let flag = false;   // flag用于标识此轮是否有交换行为
            for (let j = 0; j < i; j++) {
                if (arr[j-1] > arr[j]) {
                    flag = true;   // flag === true就表示有
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                }
            }
            
            if (flag === false) {   // 这一轮没有交换行为 就表示全部都有序了 直接返回arr 
                return arr;
            }
        };
        return arr;
    }

    /*
    	复杂度分析：
    		时间复杂度： 最好O(n),只需要循环一次，最坏O(n^2)
    		空间复杂度： O(1)
    		
    	稳定性分析：冒泡排序并不会破坏元素的相对位置
    		稳定
    */

    // test
    const arr = [2,7,4,3,8,9,10,1,5,2,3];
    bubbleSortA(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

  • 内层优化：在每一层循环的时候，记住这一层循环最后一次交换的位置，这样就说明后面的是有序的不用重复比较交换了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    function bubbleSortB(arr) {
        let i = arr.length, pos;  // 用pos记录最后一次交换的位置
        while (i > 0) {
            let flag = false;   // flag用于标识此轮是否有交换行为
            for (let j = 0; j < i; j++) {
                if (arr[j-1] > arr[j]) {
                    flag = true;   // flag === true就表示有
                    pos = j;       // 目前最后一次交换在j的位置
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                }
            };
            i = pos;    // 边界用pos代替
            
            if (flag === false) {   // 说明此轮没有交换行为
                return arr;
            }
        }
        return arr;
    }


    // test
    const arr = [2,7,4,3,8,9,10,1,5,2,3];
    bubbleSortB(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


    /*
    	复杂度分析：
    		时间复杂度： O(n^2)
    		空间复杂度： O(1)
    		
    	稳定性分析：冒泡排序并不会破坏元素的相对位置
    		稳定
    */

选择排序

算法思路

  • 首先在未排序的数组中找到最大（小）的元素，放在排序数组的起始位置
  • 再从剩余的元素中找到最大（小）的元素，放在已经排序的末尾
  • 重复步骤2，直至排序完成

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function selectSort(arr) {
    for(let i = 0; i < arr.length; i++) {   // i表示排序数组的末尾索引
        let minValue = arr[i], minIndex = i;   // 用于记录未排序数组的最小元素和对应的索引
        for (let j = i+1; j < arr.length; j++) {
            if (arr[j] < minValue) {   // 通过遍历的方式查找
                minValue = arr[j];
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];   // 找到后把排序数组的末尾索引元素和未排序数组中最小的元素进行交换
    }
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
selectSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： O(1)
		
	稳定性分析：选择排序在找到后把排序数组的末尾索引元素和未排序数组中最小的元素进行交换这个过程就破坏了元素的相对位置
		不稳定
*/

代码优化

  • 优化：一次就选出最大最小的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function selectSortA(arr) {
    for (let left = 0, right = arr.length - 1; left < right; left++, right--) {
        // 用于记录最大值和最小值的索引
        let minIndex = left, maxIndex = right;
        
        // 找到每次遍历的最大值和最小值的索引
        for (let index = left; index <= right; index++) {
            if (arr[index] < arr[minIndex]) minIndex = index;
            if (arr[index] > arr[maxIndex]) maxIndex = index;
        }
        
        // 交换
        [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
        
        //此处是先排最小值的位置，所以得考虑最大值（arr[maxIndex]）在最小位置（left）的情况
        // 如果不考虑这里的话，因为前面已经交换过了，所以会导致无效交换，反而把最大值的value交换回来了
        if (left === maxIndex) {
            maxIndex = minIndex;
        }
        
        // 交换
        [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
    }
    
    return arr;
};

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
console.log(selectSortA(arr));   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

算法思路

  • 初始化：将第一个元素看作是有序数组，将第一个元素之后的元素看作是未排序序列
  • 遍历未排序序列，并依次插入到有序数组的合适位置（这里需要注意的是，插入到排序数组合适位置之后排序数组的其他元素的位置是如何处理的？）
  • 返回排序数组

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let value = arr[i];   // 记录未排序数组的第一个元素
        let position = i;     // 记录此刻的位置
        while (position >= 0 && arr[position - 1] > value) {   // 把此刻的元素插入到排序数组的合适位置
            [arr[position], arr[position - 1]] = [arr[position-1], arr[position]];
            position--;
        };
    };
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
insertSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： O(1)
		
	稳定性分析：插入排序并没有破坏相对位置
		稳定
*/

算法优化

优化点：在找插入位置的时候可以采用二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function insertSortA(arr) {
	for (let i = 1; i < arr.length; i++) {
        let value = arr[i];  // 记录当前元素
        let position = i;   // 记录当前位置
        let insertIndex = searchInsert(arr.slice(0, i), value);   // 利用二分查找找到要插入的位置
        
        // 找到位置后把后面的元素都往后面移动
        while (insertIndex !== position && position > insertIndex) {
            arr[position] = arr[position-1];
            position--;
        };
        arr[insertIndex] = value;
    }  
    return arr;
}

// 利用二分查找找到要插入的位置
function searchInsert(nums, target) {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; 
        } else {
            right = mid -1;
        };
    };
    return right + 1;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
insertSortA(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

归并排序

算法步骤

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设两个指针，最初位置为两个已经排好序序列的起始位置
  • 比较两个指针所指向的元素，选择相对较小的元素放入合并空间，并移动指针
  • 重复步骤3直到指针到达末尾
  • 将另一序列剩下的元素直接合并到序列尾部

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function mergeSort(arr) {
    if (arr.length === 1) return arr;   // 只有一个元素不用比较了
    
    // 找到中点分隔数组
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    
    return merge(mergeSort(left), mergeSort(right));
}

// 合并
function merge(left, right) {
    // 给合并数组分配空间
    let res = [];
    
    // 判断指针指向元素的大小，把小的放入res数组中
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            res.push(left.shift())
        } else {
            res.push(right.shift())
        }
    }
    // 判断是否有元素剩余
    res = left.length ? [...res, ...left] : [...res, ...right];
    return res;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
mergeSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(nlogn)
		空间复杂度： O(n)
		
	稳定性分析：归并排序并没有破坏相对位置
		稳定
*/

快速排序

算法思路

  • 找到一个元素，作为基准
  • 剩余元素重新排序，比基准小的放在左边，比基准大的放在右边
  • 递归左边和右边，得到结果

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function quickSort(arr) {
    // 设置递归终止条件 arr只有一个元素或者没有元素 直接返回arr
    if (arr.length <= 1) return arr;
    
    // 找到基准点
    let mid = Math.floor(arr.length - 1);
    let pivot = arr[mid];
    arr.splice(mid, 1);  // 从数组中删除基准
    
    // 分配空间用于存放比基准大和小的元素
    let left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        };
    };
    
    // 返回结果为 左 + 基准 + 右
    // 左和右还要递归
    return [...quickSort(left), pivot, ...quickSort(right)];
};

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
mergeSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(nlogn)
		空间复杂度： O(logn)
		
	稳定性分析：快速排序一直在打乱相对位置
		不稳定
*/

堆排序

算法思路

  • 构造大顶堆，把堆顶元素和最后一个元素交换（相当于把最大的元素放在最后面了），堆大小减去1
  • 交换后，把剩余的元素继续构造大顶堆，即把剩余元素最大的元素选出来放在堆顶，重复步骤1
  • 继续重复步骤1和2，直至堆大小为1

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 实现最大堆的构建
/*
	注意最大堆的特点：所有节点都大于其子节点
*/

var len;
function buildMaxHeap(array) {
     len = array.length;
     for (let i = Math.floor(len / 2); i >= 0; i--) {
         heapify(array, i);
     };
    return array;
}


function heapify(arr, i) {
    let left = 2 * i + 1,    // 如果存在，左子节点index为2 * i + 1
        right = 2 * i + 2,   // 如果存在，右子节点index为2 * i + 2
        largest = i;
    
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest);
    }
}


function heapSort(arr) {
    buildMaxHeap(arr);
    
    for (let i = arr.length-1; i>0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        len--;
        heapify(arr, 0);
    };
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
heapSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析
	时间复杂度： O(nlogn)
*/

参考

十大经典排序算法

Posted on Edited on In , , , Symbols count in article: 5.8k Reading time ≈ 5 mins.

原型链继承

基本思想：通过原型链继承多个引用类型的属性和方法

我们知道，实例和原型是有直接联系的，实例可以通过__proto__访问原型，所以原型链继承即将父类的实例作为子类的原型，这样子类的原型就可以通过__proto__访问父类的原型了

1
2
3
4
5
6
7
8
function Father() {};

function Son() {};

// 继承Father
Son.prototype = new Father();

console.log(Son.prototype.__proto__ === Father.prototype);   // true

优点

  • 父类的方法子类能够被子类复用，因为子类可以访问父类原型，原型存在着父类实例可以共享的方法和属性

缺点

  • 更改一个子类的引用，其他子类也会受到影响
1
2
3
4
5
6
7
8
9
10
11
12
function Father() {};
Father.prototype.colors = ['red', 'black', 'yellow'];

function Son() {};
Son.prototype = new Father();

let p1 = new Son();
let p2 = new Son();

p1.colors[1] = 'pink';
console.log(p1.colors);    // ['red', 'pink', 'yellow']
console.log(p2.colors);    // ['red', 'pink', 'yellow']
  • 子类在实例化的时候不能向父类传参

盗用构造函数继承

基本思想：在子类构造函数中调用父类构造函数，可以使用call或者apply的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function Father() {
    this.colors = ['red', 'black', 'yellow'];
};

function Son() {
    // 继承Father
    Father.call(this);   // 通过此方法让子类继承父类中的方法和属性
};

let p1 = new Son();
let p2 = new Son();

console.log(p1.colors);    // ['red', 'black', 'yellow']
console.log(p2.colors);    // ['red', 'black', 'yellow']

优点

  • 可以在子类构造函数中向父类构造函数传参
1
2
3
4
5
6
7
8
9
10
11
function Father(name) {
    this.name = name;
};

function Son() {
    // 继承Father
    Father.call(this, 'Katrina');   // 通过此方法让子类继承父类中的方法和属性
};

let p1 = new Son();
console.log(p1.name);   // Katrina
  • 父类的引用属性不会被共享
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Father() {
    this.colors = ['red', 'black', 'yellow'];
};

function Son() {
    // 继承Father
    Father.call(this);   // 通过此方法让子类继承父类中的方法和属性
};

let p1 = new Son();
let p2 = new Son();

p1.colors[1] = 'pink';
console.log(p1.colors);    // ['red', 'pink', 'yellow']
console.log(p2.colors);    // ['red', 'black', 'yellow']

缺点

  • 必须在构造函数中定义方法，函数不能复用，每次创建都会初始化
1
2
3
4
5
6
7
function Father(name) {
 	this.colors = ['red', 'black', 'yellow'];
    this.name = name;
    this.sayHello = function() {
        console.log(`${this.name} say hello!`)
    };
}

每一次调用new Father，就会在实例内部定义一次这个sayHello方法，也就是new Function(console.log(${this.name} say hello!))，其实是更推荐把方法定义在Father.prototype上的，这样每个实例构造出来就自动继承这个方法，不需要在构造函数里面一次次地写

1
2
3
4
5
6
7
8
9
10
11
12
function Son(name) {
 	Father.call(this, name);   
}

// 等价于
function Son(name) {
    this.colors = ['red', 'black', 'yellow'];
    this.name = name;
    this.sayHello = function() {
        console.log(`${this.name} say hello!`)
    };
}

也就是说在构造函数继承的时候也在一次次调用sayHello这个方法

  • （上个问题的延申）子类不能访问父类原型上的方法【instanceOf会失效】，所有方法都只能定义在父类构造函数中

组合式继承

基本思想：使用原型链继承原型上的属性和方法，而通过盗用构造函数继承实例属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function Father(name, age) {
    this.name = name;
    this.age = age;
    this.friends = ['Jack', 'Jenny', 'Lucy'];
}

Father.prototype.sayName = function() {
    console.log(this.name);
}

function Son(name, age) {
    // 构造函数继承
    Father.call(this, name, age);                 // 调用两次
};

// 原型链继承
Son.prototype = new Father();                     // 调用一次

let p1 = new Son('Katrina', 18);
let p2 = new Son('Kate', 20);

p1.sayName();   // 'Katrina'
p2.sayName();   // 'Kate'

p1.friends.push('Bob');
console.log(p1.friends);    // ['Jack', 'Jenny', 'Lucy', 'Bob']
console.log(p2.friends);    // ['Jack', 'Jenny', 'Lucy']

优点

  • 父类的方法子类能够被子类复用
  • 父类的引用属性不会被共享
  • 子类可以访问父类原型上的方法

缺点

  • 效率问题：父类构造函数始终会被调用两次
    • 创建子类原型时调用
    • 在子类构造函数中调用

原型式继承

基本思想：把现有的对象指定为构造函数的原型对象，并返回以这个对象为原型的构造函数的实例

适用于：你有一个对象，你想在这个对象的基础上再创建一个对象 以及 不需要单独创建构造函数，但仍需要在对象间共享信息的场合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function object(o) {
    function F(){};     // 临时构建构造函数
    F.prototype = o;    // 把传入的对象指定为
    return new F();     // 返回临时类型的实例
}


// 本质上，object是吧传入的o进行了一次浅复制
let person = {
    name: 'Katrina',
    age: 18,
    gender: 'female',
    friends: ['Jack', 'Jenny', 'Lucy'],
};

let anotherPerson = object(person);
anotherPerson.name;   // 'Katrina';
anotherPerson.friends.push('Kate');

let yetAnotherPerson = object(person);
yetAnotherPerson.name;   // 'Katrina';
yetAnotherPerson.friends.push('Bob');

console.log(person.friends);   // ['Jack', 'Jenny', 'Lucy', 'Kate', 'Bob']

ES5中新增的Object.create()只传一个参数时就是运用的这种思想：手写原理 | Object.create

优点

  • 父类方法可以复用

缺点

  • 更改一个子类的引用，其他子类也会受到影响
  • 子类在实例化的时候不能向父类传参

寄生式继承

基本思想：创建一个实现继承的函数，以某种方式增强对象，然后返回这个对象

适用于：主要关注对象，而不在乎类型和构造函数的场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function object(o) {
    function F(){};     // 临时构建构造函数
    F.prototype = o;    // 把传入的对象指定为
    return new F();     // 返回临时类型的实例
} 


function createAnotherPerson(original) {
    let clone = object(original);    // 创建一个新对象，它的构造函数的原型是original
    clone.sayHi = function() {      // 给对象添加一个sayHi的方法
        console.log('Hi');
    };
    return clone;       // 返回这个对象
}

let person = {
    name: 'Katrina',
    age: 18,
    gender: 'female',
    friends: ['Jack', 'Jenny', 'Lucy'],
};

let anotherPerson = createAnotherPerson(person);
anotherPerson.sayHi();        // Hi

object()函数不是寄生式继承所必需的，任何返回新对象的函数都可以在这里使用

寄生式组合继承

寄生式组合继承主要是为了解决组合继承的效率问题

基本思想：不通过调用父类构造函数给子类原型赋值，而是取得父类函数的一个副本，即使用寄生式继承来继承父类原型，然后将返回的新对象赋值给子类原型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function object(o) {
    function F(){};     // 临时构建构造函数
    F.prototype = o;    // 把传入的对象指定为
    return new F();     // 返回临时类型的实例
}

function inheritPrototype(Son, Father) {
    let prototype = object(Father.prototype);    // 创建对象
    prototype.constructor = Son;                 // 增强对象
    Son.prototype = prototype;                   // 赋值对象
}




function Father(name, age) {
    this.name = name;
    this.age = age;
    this.friends = ['Jack', 'Jenny', 'Lucy'];
}

Father.prototype.sayName = function() {
    console.log(this.name);
}

function Son(name, age) {
    // 构造函数继承
    Father.call(this, name, age);                  // 调用一次   
};

inheritPrototype(Father, Son);

instanceof 和 isPrototypeof方法正常有效

总结

参考

关于构造函数继承的缺点的一个疑问

一篇文章理解JS继承——原型链/构造函数/组合/原型式/寄生式/寄生组合/Class extends

Posted on Edited on In , , , Symbols count in article: 3.9k Reading time ≈ 4 mins.

工厂模式

1
2
3
4
5
6
7
8
9
10
11
12
13
function createPerson(name, age, job) {
    let obj = new Object();
    obj.name = name;
    obj.age = age;
    obj.job = job;
    obj.sayName = function() {
        console.log(this.name);      // 考考你：this指向哪里？
    };
    return obj;
};

let p1 = createPerson('Katrina', 18, 'student');
console.log(p1);   // {name: 'Katrina', age: 18, job: 'student', sayName: ƒ}

优点

  • 可以解决创建多个类似对象的问题

缺点

  • 没有解决对象标识问题（即新创建的对象是什么类型）
    • 通俗来说，工厂模式中我们直接用new Object来创建，所以实例的原型链上只有Object.prototype对象

构造函数模式

1
2
3
4
5
6
7
8
9
10
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    this.sayName = function() {
        console.log(this.name); 
    };
}

let p1 = new Person('Katrina', 18, 'student');

Person()构造函数代替了createPerson()工厂函数，实际上，Person()内部代码跟createPerson()基本一样，有如下区别：

  • 没有显示地创建对象
  • 属性和方法直接付给了this
  • 没有return

这就需要我们明白new操作符的机制了：手写原理 | new操作符

优点

1
2
3
4
5
6
7
8
9
10
11
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    this.sayName = function() {
        console.log(this.name); 
    };
}

let p1 = new Person('Katrina', 18, 'student');
console.log(p1 instanceof Person);   // true

缺点

  • 定义的每个方法会在每个实例上都创建一遍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    this.sayName = function() {
        console.log(this.name); 
    };
}

let p1 = new Person('Katrina', 18, 'student');
let p2 = new Person('Kate', 20, 'doctor');

console.log(p1.sayName === p2.sayName)    // false

/*
	Person.prototype.sayHello = function() {
		console.log(this.name);
	}
	
	console.log(p1.sayHello === p2.sayHello)    // true
*/

在上面这个例子中，p1和p2都有sayName方法，但这两个方法不是同一个sayName实例

在ECMAScript中的函数是对象，因此每次定义函数时，都会初始化一个对象

1
2
3
4
5
6
7
8
9
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    /*
    	每个Person实例都会有自己的Function实例用于显示name属性
    */
    this.sayName = new Function(console.log(this.name); )   // 逻辑等价
}

因为都是做同样一件事，所以定义两个Function实例是没必要的，要解决这个问题，可以把函数定义转移到函数外部

1
2
3
4
5
6
7
8
9
10
11
12
13
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    this.sayName = sayName;
}

function sayName() {
    console.log(this.name); 
}

let p1 = new Person('Katrina', 18, 'student');
let p2 = new Person('Kate', 20, 'doctor');

这里，sayName()被定义在了构造函数外部，在构造函数内部，sayName 属性等于全局sayName()函数

因为这一次sayName 属性中包含的只是一个指向外部函数的指针，所以person1 和person2共享了定义在全局作用域上的sayName()函数

原型模式

每个函数都会创建一个prototype属性，这个属性是一个对象，包含应该由特定引用类型的实例共享的属性和方法
补课：理解原型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Person() {}

Person.prototype.name = "Katrina";
Person.prototype.age = 18;
Person.prototype.job = "Student";
Person.prototype.sayName = function() {
	console.log(this.name);
};

let person1 = new Person();
person1.sayName(); // "Katrina"

let person2 = new Person();
person2.sayName(); // "Katrina"

console.log(person1.sayName == person2.sayName); // true

优点

  • 原型上定义的属性和方法可以被对象实例共享

缺点

  • 更改一个子类的引用，其他子类也会受到影响
1
2
3
4
5
6
7
8
9
10
function Person() {}
Person.prototype.colors = ['red', 'black', 'yellow'];

let p1 = new Person();
let p2 = new Person();

p1.colors[1] = 'pink';

console.log(p1.colors);    // ['red', 'pink', 'yellow']
console.log(p2.colors);    // ['red', 'pink', 'yellow']
  • 子类在实例化的时候不能向父类传参

构造函数模式+原型模式

属性写在构造函数模型中，方法写在原型模型中

这样的话，每个实例都有自己实例属性的副本，但同时又共享着对方法的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Person(name, age, job) {
    this.name = name;
    this.age = age;
    this.job = job;
    this.colors = ['red', 'black', 'yellow'];
}

Person.prototype.sayName = function() {
	console.log(this.name);
};

let p1 = new Person('Katrina', 18, 'student');
let p2 = new Person('Kate', 20, 'doctor');

console.log(p1.sayName == p2.sayName);   // true

p1.colors[1] = 'pink';

console.log(p1.colors);    // ['red', 'pink', 'yellow']
console.log(p2.colors);    // ['red', 'black', 'yellow']

Posted on In , Symbols count in article: 906 Reading time ≈ 1 mins.

Promise.finally()返回一个Promise实例，在promise结束时，无论结果是fulfilled还是rejected，都会执行指定的回调函数

应用场景：无论Promise是成功还是失败都会执行，避免了在then和catch各写一次的情况

finally和then(onFinally, onFinally)类似，不同之处在于：

  • 调用内联函数时，不需要多次声明该函数或为该函数创建一个变量保存它
  • 由于无法知道 promise 的最终状态，所以 finally 的回调函数中不接收任何参数，它仅用于无论最终结果如何都要执行的情况
  • 与Promise.resolve(2).then(() => {}, () => {})（resolved 的结果为undefined[因为这里的then没有显式的返回语句，所以结果为undefined]）不同，Promise.resolve(2).finally(() => {}) resolved 的结果为 2
  • 同样，Promise.reject(3).then(() => {}, () => {}) (fulfilled 的结果为undefined[因为这里的then没有显式的返回语句，所以结果为undefined]), Promise.reject(3).finally(() => {}) rejected 的结果为 3
1
2
3
4
5
6
7
8
9
10
11
function myPromiseFinally(callback) {
    return this.then(function(value) {
        return Promise.resolve(callback()).then(function() {
            return value;
        })
    }, function(err) {
        return Promise.reject(callback()).then(function() {
            throw err;
        })
    })
}

Posted on In , Symbols count in article: 325 Reading time ≈ 1 mins.

Promise.race返回一个Promise实例，一旦迭代器中的某个 promise 解决或拒绝，返回的 promise 就会解决或拒绝

应用场景：可以测试接口的响应速度

1
2
3
4
5
6
7
8
9
10
11
function MyPromiseRace(promises) {
    return new Promise((resolve, reject) => {
        for (let item of promises) {
         	Promise.resolve(item).then(res => {
                resolve(res);
            }).catch(err => {
                reject(err);
            })    
        }
    });
};

Posted on Edited on In , Symbols count in article: 1.5k Reading time ≈ 1 mins.

Promise.all 方法接收一个promise的iterable类型（比如：Array，Map，Set）的输入，并且只返回一个Promise实例，如果所有的promise都是resolve状态，value就为结果数组，结果的顺序与传入顺序一致，如果promise中有reject，就会抛出错误，reason为抛出的是第一个reject的信息

应用场景：在请求数据的过程中，偶尔会遇到发送多个请求并根据请求顺序获取和使用数据的场景

实现思路及注意点

  • 输入promises可以是一个iterator类型的参数，不一定需要局限在array（好多手写一上来就判断是不是array）
  • 如果iterator为空，resolve返回空数组
  • 非Promise实例的需要经过Promise.resolve包裹
  • 如果都会resolve，输出的结果数组必须和原顺序一致，并不是谁先执行完谁先进入结果数组
  • 返回一个Promise实例可以调用then和catch方法，then里面为保持原顺序的数组，catch里面则为最早reject的返回值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function myPromiseAll(promises) {
    return new Promise((resolve, reject) => {
        const promiseResults = [];
        // 迭代的顺序
        let iteratorIndex = 0;
        // 用于记录已经完成的数量，注意这个不是顺序
        let fullCount = 0;
        // 迭代开始
        for (let promise of promises) {   // for of就是用于遍历可迭代对象的
            // for of 是顺序执行的
            let resultIndex = iteratorIndex;
            iteratorIndex++;
            
            // 非Promise实例的需要经过Promise.resolve包裹
            Promise.resolve(promise).then(res => {
                promiseResults[resultIndex] = res;
                // then后表示完成
                fullCount++;
                
                // Iterator接口无法单纯根据length和size判断长度
                if (fullCount === iteratorIndex) {
                    resolve(promiseResults);
                }
            }).catch(err => {
                reject(err);
            })
        }
        
        // 如果iterator为空，resolve返回空数组
        if (iteratorIndex === 0) {
            resolve(promiseResults);
        }
    })
}

// test
var p1 = Promise.resolve(3);
var p2 = 1337;
var p3 = new Promise((resolve, reject) => {
  setTimeout(resolve, 100, 'foo');
});

var p = myPromiseAll([p1, p2, p3]);  // Promise {<fulfilled>: [3, 1337, "foo"]}
p.then(values => {
  console.log(values); // [3, 1337, "foo"]
})

Posted on In , Symbols count in article: 1.2k Reading time ≈ 1 mins.

Promise.allSettled()方法返回一个在所有给定的 promise 都已经fulfilled或rejected后的 promise，并带有一个对象数组，每个对象表示对应的 promise 结果

[ {status: 'fulfilled', value: 3}, {status: 'rejected', reason: 'foo'}]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function myPromiseAllSelected(promises) {
    return new Promise((resolve, reject) => {
        let res = [];
        let iteratorIndex = 0;
        let fullCount = 0;
        
        for (let item of promises) {
          let resIndex =  iteratorIndex;
          iteratorIndex++;
            
          Promise.resolve(item).then(value => {
              res[resIndex] = {
                  status: 'fulfilled',
                  value,
              };
              fullCount++;
              
              if (fullCount === iteratorIndex) {
                  resolve(res);
              }
          }).catch(reason => {
              res[resIndex] = {
                  status: 'rejected',
                  reason,
              };
              fullCount++;
              
              if (fullCount === iteratorIndex) {
                  resolve(res);
              }
          })
        };
    })
};


// test

let p1 = Promise.resolve(3);
let p2 = Promise.reject(2);

Promise.allSettled([p1, p2]).then(val => {
    console.log(val)
}). catch(err => {
    console.log(err)
});  

/*
    [
        { status: 'fulfilled', value: 3 },
        { status: 'rejected', reason: 2 }
    ]
*/ 


myPromiseAllSelected([p1,p2]).then(res => console.log(res), err => console.log(err))

Posted on In , Symbols count in article: 632 Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
MyPromise.prototype.then = function(onResolved, onRejected) {
    // 首先判断resolve 和 reject是否为function类型
    onResolved = typeof onResolved === "function" ? onResolved : function(value) {
        return value;
    };

    onResolved = typeof onResolved === "function" ? onRejected : function(error) {
        return error;
    };
    
    // 如果是等待状态，则将函数加入对应的列表中
    if (this.state === PENDING) {
        this.rejectedCallbacks.push(onResolved);
        this.rejectedCallbacks.push(onRejected);
    };

    // 如果状态已经改变（凝固），则执行对应状态的函数
    if (this.state === RESOLVED) {
        onResolved(this.value);
    };

    if (this.state === REJECTED) {
        onRejected(this.value);
    };
}

Posted on In , Symbols count in article: 1.1k Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const PENDING = 'pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';

function myPromise(fn) {
    // 保存初始的状态
    const self = this;
    
    // 定义初始的状态为pending
    this.state = PENDING;
    
    // 用于保存resolve reject传入的值
    this.value = [];
    // 用于保存resolve reject的回调函数
    this.resolveCallbacks = [];
    this.rejectCallbacks = [];
    
    // 状态转变为resolve的操作
    function resolve(value) {
        // 判断传入元素是否为 Promise 值，如果是，则状态改变必须等待前一个状态改变后再进行改变
        if (value instanceof myPromise) {
            return value.then(resolve, reject);
        }
        
        // 保证代码的执行顺序为本轮事件循环的末尾
        setTimeout(() => {
            if (this.state === PENDING) {
                this.state = FULFILLED;
                this.value = value;
                resolveCallbacks.forEach(callback=>callback(value));
            }
        }, 0);
    }
    
    // 状态转变为reject的操作
    function reject(reason) {
         setTimeout(() => {
            if (this.state === PENDING) {
                this.state = REJECTED;
                this.value = reason;
                resolveCallbacks.forEach(callback=>callback(reason));
            }
        }, 0);
    }
    
    // 把两个函数传入fn中
    try{
        fn(resolve, reject);
    } catch (err) {
        reject(err);
    }
}