算法的世界博大精深，路漫漫，上下求索
算法
下边说的都还比较简单，感兴趣的同学可以去各大OJ上刷刷题：
https://leetcode.com/
http://acm.hdu.edu.cn/
http://poj.org/
…
先说数据结构
- 简单数据结构
- 有序数据结构：栈、队列、链表，有序数据结构省空间（存储空间小）
- 无序数据结构：集合、字典、散列表，无序数据结构省时间（读取时间快）
- 复杂数据结构
对于简单数据结构，在 ES 中对应的是数组（Array）和对象（Object）。可以想一下，数组的存储是有序的，对象的存储是无序的，我要在对象中根据key找到一个值是立即返回的，数组则需要查找的过程。
数组&链表的区别：
数组在内存中连续，链表不连续；
数组静态分配内存，大小固定，不能动态拓展，链表动态分配内存拓展灵活； （js中数组是特殊的对象）
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
算法复杂度分析
这里只说时间复杂度
常见的时间复杂度有：
- 常数阶 O(1)
- 对数阶 O(logN)
- 线性阶 O(n)
- 线性对数阶 O(nlogN)
- 平方阶 O(n^2)
- 立方阶 O(n^3)
- !k次方阶 O(n^k)
- 指数阶O(2^n)
- 看看有几重循环，一般来说一重就是O(n)，两重就是 O(n^2)，以此类推
- 如果有二分，则为O(logN)
- 保留最高项，去除常数项
例子：
1
2
3
4
| let number = 1; // 语句执行一次
while (number < n) { // 语句执行 logN 次
number *= 2; // 语句执行 logN 次
}
|
上面代码while的跳出判断条件是number<n，而循环体内number增长速度是(2^n)，所以循环代码实际执行logN次，复杂度为：1 + 2 * logN = O(logN)
详情
前端相对来说需要高深复杂算法的情况不多，下边简单介绍一些基础算法：
递归
实现一个深拷贝：
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
57
| (function () {
'use strict';
var types = 'Array Object String Date RegExp Function Boolean Number Null Undefined'.split(' ');
function type () {
return Object.prototype.toString.call(this).slice(8, -1);
}
for (var i = types.length; i--;) {
$['is' + types[i]] = (function (self) {
return function (elem) {
return type.call(elem) === self;
};
})(types[i]);
}
return $;
})(window.$ || (window.$ = {}));//类型判断
function copy (param,deep) {
// 原始类型
if (param === null || (typeof param !== "object" && !$.isFunction(param))) {
return param;
}
// 函数
if ($.isFunction(param)) {
return new Function("return " + param.toString())();
}
else {
// 数组、对象
var target = $.isArray(param) ? [] : {},
name,
value;
for (name in param) {
value = param[name];
// 防止循环引用 和不是自身属性的拷贝
if (value === param || !param.hasOwnProperty(name)) {
continue;
}
// 深拷贝
if (deep) {
target[name] = copy(value,deep); // 数组的索引可以是非负整数字符串 eg. target['1']
} else {
// 浅拷贝
target[name] = value;
}
}
return target;
}
}
|
快排
O(NlogN)
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
| const Arr = [85, 24, 63, 45, 17, 31, 96, 50];
function quickSort(arr) {
if(!arr) {
return [];
}
if(arr.length <= 1) {
return arr;
}
// 取出中间值
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] < pivot) { // 左边值
left.push(arr[i]);
} else {
right.push(arr[i]); // 右边值
}
}
// 递归
return quickSort(left).concat([pivot], quickSort(right)); // 合并
}
console.log(quickSort(Arr));
|
二分查找
O(logN)
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
| function find(arr, value) {
if(!arr || arr.length === 0) {
return false;
}
let low = 0;
let high = arr.length - 1;
let mid;
let midValue;
while( low <= high ) {
mid = Math.floor((low + high)/2);
midValue = arr[mid];
if(midValue === undefined) {
console.log('未查找到数的index', );
return false;
}
if(value === midValue) {
console.log('查找到数的index为：', mid);
return mid;
}
if(value > midValue) {
low = mid + 1;
}
if(value < midValue) {
high = mid - 1;
}
}
return false;
}
//测试用例
find([1], 2);
find([1,2,3,4], 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
| function CreatePerson(name,age,sex) {
var obj = new Object();
obj.name = name;
obj.age = age;
obj.sex = sex;
obj.sayName = function(){
return this.name;
}
return obj;
}
var p1 = new CreatePerson("longen",'28','男');
var p2 = new CreatePerson("tugenhua",'27','女');
console.log(p1.name); // longen
console.log(p1.age); // 28
console.log(p1.sex); // 男
console.log(p1.sayName()); // longen
console.log(p2.name); // tugenhua
console.log(p2.age); // 27
console.log(p2.sex); // 女
console.log(p2.sayName()); // tugenhua
// 返回都是object 无法识别对象的类型 不知道他们是哪个对象的实列
console.log(typeof p1); // object
console.log(typeof p2); // object
console.log(p1 instanceof Object); // true
|
复杂工厂；
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| // 定义自行车的构造函数
var BicycleShop = function(name){
this.name = name;
this.method = function(){
return this.name;
}
};
BicycleShop.prototype = {
constructor: BicycleShop,
/*
* 买自行车这个方法
* @param {model} 自行车型号
*/
sellBicycle: function(model){
var bicycle = this.createBicycle(model);
// 执行A业务逻辑
bicycle.A();
// 执行B业务逻辑
bicycle.B();
return bicycle;
},
createBicycle: function(model){
throw new Error("父类是抽象类不能直接调用，需要子类重写该方法");
}
};
// 实现原型继承
function extend(Sub,Sup) {
//Sub表示子类，Sup表示超类
// 首先定义一个空函数
var F = function(){};
// 设置空函数的原型为超类的原型
F.prototype = Sup.prototype;
// 实例化空函数，并把超类原型引用传递给子类
Sub.prototype = new F();
// 重置子类原型的构造器为子类自身
Sub.prototype.constructor = Sub;
// 在子类中保存超类的原型,避免子类与超类耦合
Sub.sup = Sup.prototype;
if(Sup.prototype.constructor === Object.prototype.constructor) {
// 检测超类原型的构造器是否为原型自身
Sup.prototype.constructor = Sup;
}
}
var BicycleChild = function(name){
this.name = name;
// 继承构造函数父类中的属性和方法
BicycleShop.call(this,name);
};
// 子类继承父类原型方法
extend(BicycleChild,BicycleShop);
// BicycleChild 子类重写父类的方法
BicycleChild.prototype.createBicycle = function(){
var A = function(){
console.log("执行A业务操作");
};
var B = function(){
console.log("执行B业务操作");
};
return {
A: A,
B: B
}
}
var childClass = new BicycleChild("龙恩");
console.log(childClass);
|
单例模式
单例是如果它可以被实例化，那么它只能被实例化一次的对象，应用：每一个弹窗需要创建一个div，用单例所有弹窗只创建一个div减少页面重绘。
单体模式的优点是：
- 可以用来划分命名空间，减少全局变量的数量。
- 使用单体模式可以使代码组织的更为一致，使代码容易阅读和维护。
- 可以被实例化，且实例化一次。
通用单例模式：
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
| // 创建div
var createWindow = function(){
var div = document.createElement("div");
div.innerHTML = "我是弹窗内容";
div.style.display = 'none';
document.body.appendChild(div);
return div;
};
// 创建iframe
var createIframe = function(){
var iframe = document.createElement("iframe");
document.body.appendChild(iframe);
return iframe;
};
// 获取实例的封装代码(存储在闭包中，读到了直接返回，读不到创建保存并返回)
var getInstance = function(fn) {
var result;
return function(){
return result || (result = fn.call(this,arguments));
}
};
// 测试创建div
var createSingleDiv = getInstance(createWindow);
document.getElementById("Id").onclick = function(){
var win = createSingleDiv();
win.style.display = "block";
};
// 测试创建iframe
var createSingleIframe = getInstance(createIframe);
document.getElementById("Id").onclick = function(){
var win = createSingleIframe();
win.src = "http://cnblogs.com";
};
|
观察者模式(又叫发布—订阅模式)
在稍微复杂点的页面中，比如组件化开发的页面，同一个页面由两三个人来开发，为了保证组件的独立性和降低组件间耦合度，我们往往使用「订阅发布模式」，即组件间通信使用事件监听和派发的方式，而不是直接相互调用组件方法
为此我们可以封装一个全局订阅发布模式对象；
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
57
58
59
60
61
62
63
64
65
66
| var Event = (function(){
var list = {},
listen,
trigger,
remove;
// 无数组，创建数组后push
listen = function(key,fn){
if(!list[key]) {
list[key] = [];
}
list[key].push(fn);
};
// 不触发（触发函数数组不存在||为空）
// 触发（有数组，依次触发）
trigger = function(){
var key = Array.prototype.shift.call(arguments), // 也可以用splice(0,1)[0]
fns = list[key];
if(!fns || fns.length === 0) {
return false;
}
for(var i = fns.length; i >= 0; i--) { // 必须倒序，因为once函数执行完删除函数会影响数组长度
fns[i].apply(this,arguments);
}
};
// 无法删除 （数组不存在或为空return false）
// 全部删除 （不指定具体删除函数）
// 删除某个（指定具体的函数）
remove = function(key,fn){
var fns = list[key];
if(!fns || fns.length === 0) {
return false;
}
if(!fn) {
fns.length = 0;
return false;
}
for(var i = fns.length - 1; i >= 0; i--){
var _fn = fns[i];
if(_fn === fn) {
fns.splice(i,1);
}
}
};
once = function(key, fn) {
function fun() {
// var arr = Array.prototype.slice.apply(arguments);
fn.apply(this, arguments);
this.remove(key, fun);
}
this.add(key, fun);
};
return {
listen: listen,
trigger: trigger,
remove: remove,
once: once
}
})();
// 测试代码如下：
Event.listen("color",function(size) {
console.log("尺码为:"+size); // 打印出尺码为42
});
Event.trigger("color",42);
|