常见的手写代码
常见的手写代码
实现一个 new 操作符
/** 手写 new 操作符
* 用法：创建一个实例化对象
* 思路：
* 1、判断传入的 fn 是否为 function
* 2、创建一个空对象
* 3、将这个空对象的原型设置为构造函数的 prototype 属性。
* 4、使用 apply 执行构造函数 并传入参数 arguments 获取函数的返回值
* 5、判断这个返回值 如果返回的是 Object || Function 类型 就返回该对象 否则返回创建的对象
* @param {Function} fn 构造函数
* @return {*}
*/
function myNew(fn, ...args) {
// 判断 fn 是否为函数
if (typeof fn !== "function") {
return new TypeError("fn must be a function");
}
// 创建一个空的对象
let obj = null;
// 将这个空对象的原型设置为构造函数的 prototype 属性。
obj = Object.create(fn.prototype);
// 将该对象作为this传递进构造函数, 然后运行构造函数进行赋值
let result = fn.apply(obj, args);
// 如果构造函数有返回值, 并且是对象, 则返回该对象, 否则为我们创建的对象
return result instanceof Object ? result : obj;
}
实现一个 intanceof 操作符
/** 手写 instanceof 方法
* 用法：instanceof 运算符用于检测构造函数的 prototype 属性是否出现在某个实例对象的原型链上。
* 思路：
* 1、通过 Object.getPrototypeOf 获取 obj 的原型
* 2、循环判断 objProtoType 是否和 constructor 的原型相等
* 2.1、如果相等就返回 true
* 2.2、如果不相等 就重新赋值一下 obj 的原型 进入下一次循环
* 3、判断是 objProtoType 是否为空 如果为空就说明不存在 返回 false
* @param {Object} obj 需要判断的数据
* @param {Object} constructor
* @return {*}
*/
function myInstanceof(obj, type) {
let objPrototype = Object.getPrototypeOf(obj);
while (true) {
if (!objPrototype) return false;
if (objPrototype === type.prototype) return true;
objPrototype = Object.getPrototypeOf(objPrototype);
}
}
继承
1. 原型继承
原型链继承主要是利用原型对所有实例共享的特性来实现继承的。该继承方式主要有如下特点:
- 原型在包含有引用类型的数据时, 会被所有的实例对象所共享, 容易造成修改的混乱。
- 创建子类型的时候不能向超类型传递参数。
- 实例属于子类不属于父类。
// 子类
function Child(name, age) {
this.name = name;
this.age = age;
}
//原型对象
const Father = {
colors: ["red", "blue"],
};
// 原型继承
Child.prototype = Father;
const child = new Child("randy", 26);
2. 构造继承
使用借用构造函数继承这种方式是通过在子类型的函数中调用父类型的构造函数来实现的。该继承方式有如下特点
- 构造函数继承解决了不能向父类型传递参数的缺点。
- 但是它存在的一个问题就是无法实现函数方法的复用, 就是父类方法在每个实例里面都会存在, 相较于原型继承浪费了存储空间。
- 并且父类型原型上定义的方法子类型也没有办法访问到。
- 实例属于子类不属于父类。
// 父类
function Father(name, age) {
this.name = name;
this.age = age;
this.fatherColors = ["green", "yellow"];
}
//子类
function Child(name, age, sex) {
// 构造继承 可以传参 解决了不能向父类型传递参数的缺点
Father.call(this, name, age);
this.sex = sex;
}
const child = new Child("randy", 26, "male");
3. 组合继承
组合继承是将原型链继承和构造函数继承组合起来使用的一种方式。通过借用构造函数的方式来实现实例属性的继承, 通过将子类型的原型设置为父类的实例来实现原型属性的继承。该继承方式有如下特点
- 这种方式解决了上面的两种模式单独使用时的问题。能向父类型传递参数, 能获取父类原型上的属性和方法。
- 由于我们是以超类型的实例来作为子类型的原型, 所以调用了两次超类的构造函数。
- 由于原型是父类实例, 所以实例对象的原型中多了很多不必要的属性（实例中有父类的方法和属性, 原型里面还有, 都是重复的）。
- 实例对象既属于父类又属于子类。
// 父类
function Father(name, age) {
this.name = name;
this.age = age;
this.fatherColors = ["green", "yellow"];
}
//子类
function Child(name, age, sex) {
// 构造继承
Father.call(this, name, age);
this.colors = ["red", "blue"];
this.sex = sex;
}
// 原型继承
Child.prototype = new Father();
Child.prototype.constructor = Child;
const child = new Child("randy", 26, "male");
4. 寄生式继承
寄生式继承的思路是创建一个用于封装继承过程的函数, 通过传入一个对象, 然后创建一个新对象, 该对象的原型是传入的对象。然后对该新对象进行扩展, 最后返回这个新对象。这个扩展的过程就可以理解是一种继承。该继承方式有如下特点
- 这种继承的优点就是对一个简单对象实现继承。
- 没有办法实现函数的复用。
- 传入对象会被作为新对象的原型, 会被所有的实例对象所共享, 容易造成修改的混乱。
- 创建子类型的时候不能向超类型传递参数。
- 实例是父类的实例。
function CreateObj(obj) {
// 把传进来的对象作为新创建对象的原型
let newObj = Object.create(obj);
// 简单的一些扩展
newObj.colors = ["red", "blue"];
return newObj;
}
function Father(name, age) {
this.name = name;
this.age = age;
this.sayFather = function () {
console.log("child sayFather", this.name, this.age);
};
this.fatherColors = ["green", "yellow"];
}
let child = CreateObj(new Father("randy", 24));
5. 寄生式组合继承
组合继承的缺点就是使用超类型的实例作为子类型的原型, 导致添加了不必要的原型属性。寄生式组合继承的方式是使用父类型的原型的副本来作为子类型的原型, 这样就避免了创建不必要的属性。该继承方式是组合继承的升级版, 有如下特点
- 原型在包含有引用类型的数据时, 会被所有的实例对象所共享, 容易造成修改的混乱。
- 创建子类型的时候能向超类型传递参数。
- 实例对象不再臃肿, 原型只包含父类的原型。
- 实例对象既属于父类又属于子类。
function CreateObj(obj) {
// 把传进来的对象作为新创建对象的原型
let newObj = Object.create(obj);
// 简单的一些扩展
newObj.say = function () {
console.log("say");
};
return newObj;
}
// 父类
function Father(name, age) {
this.name = name;
this.age = age;
this.fatherColors = ["green", "yellow"];
}
//子类
function Child(name, age) {
// 构造继承
Father.call(this, name, age);
this.colors = ["red", "blue"];
}
// 将父类原型传递过去, 创建一个新对象, 不再是父类的实例对象
const obj = CreateObj(Father.prototype);
// 寄生式组合继承 使用新对象作为子类的原型
Child.prototype = obj;
Child.prototype.constructor = Child;
const child = new Child("randy", 26);
6. 类继承(class extends 继承)
从上面 class 的介绍我们知道, 只有方法才会被挂载到原型上, 这是寄生式组合继承的升级版, 除了有寄生式组合继承的优点外还解决了原型修改混乱的问题。这应该是最佳的继承方式了
- 创建子类型的时候能向超类型传递参数。
- 实例既属于子类又属于父类。
- 实例对象不再臃肿, 原型只包含父类的原型。
class Father {
constructor(name, age) {
// 构造函数里面的属性或方法都会在子类实例上
this.name = name;
this.age = age;
}
// 父类方法会被挂载到原型的原型上
sayFather() {
console.log("child sayFather", this.name, this.age);
}
}
// 子类继承
class Child extends Father {
_colors = ["blue", "red"];
constructor(name, age, sex) {
// 没参数
// super();
// 有参数
super(name, age);
this.sex = sex;
}
// 方法会挂载到原型上
say() {
console.log("child say", this.name, this.age, this.sex);
}
}
const child = new Child("randy", 24, "male");
防抖
所谓防抖, 就是指单位时间内函数只执行一次, 如果在单位时间内重复触发该事件, 则会重新计算函数执行时间。
常见的使用场景是在一些点击请求的事件上, 避免因为用户的多次点击向后端发送多次请求。
实现思路:
- 保存一个变量 timer
- 返回一个闭包函数 函数内判断一下 timer 是否有值 2.1 如果有值 说明 定时器已经开启 需要将定时器清空
- 设置定时器 等待 wait 后执行 将定时器赋值给 timer 记录
- 通过 apply 执行函数 传入 arguments
/**
* @desc 防抖函数: 一定时间内, 只有最后一次操作, 再过 wait 毫秒后才执行函数
* @param {Function} fn 函数
* @param {Number} wait 延迟执行毫秒数
*
* args -> 允许回调函数传参
* this_ -> 场景: 在给 dom 绑定事件并使用 this 时, 由于函数 fn 是在 setTimeout 中调用的, 所以 this 会指向 window, 这时需要将闭包中的 this 存下来, 再在调用 fn 时手动更改 this 的指向
* 箭头函数 -> 涉及到 this 时不用箭头函数, 不需要 this 的情景可以写成箭头函数的语法
*/
function debounce(fn, wait = 1000, immediate = false) {
let timer = null;
// 返回一个闭包, 接收参数
return function (...arguments) {
// 保存闭包被调用时的 this
const this_ = this;
// 存在定时器, 清空
if (timer) {
clearTimeout(timer);
timer = null;
}
// 立即执行
if (immediate) {
// 判断是否执行过 如果执行过 timer 不为空
const flag = !timer;
// 执行函数
// 通过 apply 修改 fn 的 this
flag && fn.apply(this_, arguments);
// n 秒后清空定时器
timer = setTimeout(() => {
timer = null;
}, wait);
} else {
// wait 时间后执行
timer = setTimeout(() => {
// fn(...arguments);
// 通过 apply 修改 fn 的 this
fn.apply(this_, arguments);
}, wait);
}
};
}
节流
所谓节流, 就是单位时间内不管触发多少次函数, 只固定执行一次函数。
常见的使用场景是在一些 scroll 函数的事件监听上, 通过事件节流来降低事件调用的频率。
实现思路:
- 思路：
-
记录函数上一次执行的时间戳 startTime
-
返回一个闭包函数 当被调用时会记录一下执行时间 nowTime
-
比较两次执行时间间隔 是否超过了 wait 时间
-
如果是大于 wait 时间 说明已经过了一个 wait 时间 可以执行函数
- 4.1 更新 startTime 方便下次对比
- 4.2 通过 apply 执行函数 fn 传入 arguments 参数
-
如果没有超过 wait 时间 说明是在 wait 时间内又执行了一次 忽略
// 方法一: 使用时间戳
/**
* @desc 节流函数: 在一定时间内, 只能触发一次
* @param {Function} func 函数
* @param {Number} wait 延迟执行毫秒数
*
* 思路:
1. 定义一个标记变量来表示是否允许执行目标函数, 默认为 0;
2. 当事件触发时, 检查当前的时间戳与标记变量的差值, 如果差值大于设定的延迟时间, 则执行函数并将标记变量设为当前的时间戳;如果差值小于设定的延迟时间, 则不执行;
3. 在指定时间间隔内再次触发事件时, 则重复 2 步骤;
*/
const throttle = (fn, wait) => {
let startTime = Date.now();
// 返回闭包
return function (...args) {
// 绑定this
const this_ = this;
const nowTime = Date.now();
if (nowTime - startTime >= wait) {
// 更新pre的时间
startTime = nowTime;
// 执行真正的方法
return fn.apply(this_, args);
}
};
};
// 问题: 因为间隔的检查, 可能最后一次操作恰好在这个 wait 时间内, 导致不满足条件, 从而未能做最后一次更新
// 方法二: 使用定时器
/**
* @desc 节流函数: 在一定时间内, 只能触发一次
* @param {Function} func 函数
* @param {Number} wait 延迟执行毫秒数
*
* 思路:
第一次操作: time 为空, 创建定时器, 它会在 wait 时间后执行;
第二次操作: 假设这个操作间隔仍在 wait 之内, 所以 time 还没执行, 因此我们不创建新的定时器;
第三次操作: 假设这个操作的时间间隔已经超过了 wait, 那么 time 一定执行过了, 我们提前在 time 内定义 time = null 的操作, 保证定时器自己执行后清空定时器ID
*/
const throttle = (fn, wait) => {
let time;
return function (...args) {
const this_ = this;
// 如果存在time则不创建新的定时器
if (!time) {
time = setTimeout(() => {
// 定时器会在wait后执行, 执行完毕清空time
time = null;
fn.apply(this_, args);
}, wait);
}
};
};
// 问题: 因为定时器的存在, 第一次执行一定是 wait 之后才会执行
// 方案三: 结合使用定时器和时间戳
const throttle = (fn, wait) => {
let time;
let startTime = Date.now();
return function (...args) {
// 保存this
const this_ = this;
// 获取当前时间
const nowTime = Date.now();
// 每次都计算剩余时间
const remaining = wait - (nowTime - startTime);
// 不用等了就直接执行
if (remaining <= 0) {
startTime = nowTime;
fn.apply(this_, args);
// 考虑到之前可能还有定时器没执行, 清除定时器并重置id
if (time) {
clearTimeout(time);
time = null;
}
} else if (!time) {
time = setTimeout(() => {
// 记录当前最新的时间
startTime = Date.now();
// 定时器会在wait后执行, 执行完毕清空time
time = null;
fn.apply(this_, args);
// 根据剩余时间执行定时器
}, remaining);
}
};
};
浅拷贝
深拷贝和浅拷贝都是针对引用数据类型来说的;
浅拷贝是指, 一个新的对象对原始对象的属性值进行精确地拷贝, 如果拷贝的是基本数据类型, 拷贝的就是基本数据类型的值, 如果是引用数据类型, 拷贝的就是内存地址。如果其中一个对象的引用内存地址发生改变, 另一个对象也会发生变化。
常见的浅拷贝方法有对象的 Object.assign()、扩展运算符{...obj}, 数组的 Array.concat(),Array.slice(), Array.from(), 扩展运算符[...arr]
/** 浅拷贝
* 思路：
* 1、判断是否为对象
* 2、根据obj类型创建一个新的对象
* 3、for in 遍历对象 拿到 key
* 4、判断 key 是否在 obj 中
* 5、将 key 作为新对象的key 并赋值 value
*
* @param {*} obj
* @return {*}
*/
function shallowCopy(obj) {
// 只拷贝对象
if (!obj || typeof obj !== "object") {
return obj;
}
// 根据 object 的类型判断是新建一个数组还是对象
const newObj = Array.isArray(obj) ? [] : {};
// 遍历 object, 并且判断是 object 的属性才拷贝, 不处理原型上的属性
for (const key in obj) {
// 判断 key 是否在 obj 中
if (obj.hasOwnProperty(key)) {
newObj[key] = obj[key];
}
}
return newObj;
}
深拷贝
深拷贝是指拷贝出的值不会随原值的改变而改变;
1. 方案一: 递归
// 递归去复制所有层级属性
/** 深拷贝
* 用法：拷贝一个对象的属性值 如果遇到属性值为引用类型的时候, 它新建一个引用类型并将对应的值复制给它, 因此对象获得的一个新的引用类型而不是一个原有类型的引用
* 思路：
* 1、判断是否为对象
* 2、判段对象是否在 map 中 如果存在就不需要操作
* 3、将 obj 放入 map 中 避免重复引用
* 4、for in 遍历对象 拿到 key 判断 key 是否在 obj 中
* 5、value 如果为对象 就递归拷贝 否则就赋值
* @param {*} obj
* @param {*} [map=new Map()]
* @return {*}
*/
function deepCopy(obj, map = new Map()) {
// 只拷贝对象
if (!obj || typeof obj !== "object") {
return obj;
}
// 判断 obj 是否在 map 中存在 如果存在就不需要递归调用 直接返回数据
if (map.get(obj)) {
return map.get(obj);
}
const newObj = Array.isArray(obj) ? [] : {};
// 放入 map 中 记录当前对象 避免重复拷贝 循环引用
map.set(obj, newObj);
// 遍历 object, 并且判断是 object 的属性才拷贝, 不处理原型上的属性
for (const key in obj) {
if (obj.hasOwnProperty(key)) {
// 如果还是对象, 则递归处理
newObj[key] =
typeof obj[key] === "object" ? deepCopy(obj[key], map) : obj[key];
}
}
return newObj;
}
let a = [1, 2, 3, 4],
b = deepClone(a);
a[0] = 2;
console.log(a, b);
2. 方案二: JSON 对象的 parse 和 stringify
function deepClone(obj) {
let _obj = JSON.stringify(obj),
objClone = JSON.parse(_obj);
return objClone;
}
let a = [0, 1, [2, 3], 4],
b = deepClone(a);
a[0] = 1;
a[2][0] = 1;
console.log(a, b);
3. 方案三: jQ.extend
let a = [0, 1, [2, 3], 4],
b = $.extend(true, [], a);
// extend 参数1: 深拷贝 true,浅拷贝 false; 参数2: 目标对象; 参数三及之后的参数: 第一个及第 N 个被合并的对象
a[0] = 1;
a[2][0] = 1;
console.log(a, b);
call
/** 手写 call
* 用法：call 方法用于调用一个函数, 并指定函数内部 this 的指向, 传入一个对象
* 思路：
* 1、判断 this 是否指向一个函数 只有函数才可以执行
* 2、获取传入的 context 上下文 也就是我们要指向的 如果不存在就指向 window
* 3、将当前 this 也就是外部需要执行的函数 绑定到 context 上 然后执行获取 result 传入 ...args 确保参数位置正确
* 4、删除 context 对象的 fn 属性 并将 result 返回
*/
Function.prototype.myCall = function (context, ...args) {
// 判断调用对象, 不是方法直接抛错
if (typeof this !== "function") {
console.error("type error");
}
context = context || window;
// 获取参数, 除去第一个
let args = [...arguments].slice(1);
let result = null;
// 将调用该函数的方法设为对象的方法
context.fn = this; // 这里的this就是调用myCall的方法
// 调用函数获取结果
result = context.fn(...args);
// 将属性删除
delete context.fn;
// 返回结果
return result;
};
apply
/** 手写 apply
* 用法：apply 方法用于调用一个函数, 并指定函数内部 this 的指向, 传入一个数组
* 思路：
* 1、判断 this 是否指向一个函数 只有函数才可以执行
* 2、获取传入的 context 上下文 也就是我们要指向的 如果不存在就指向 window
* 3、将当前 this 也就是外部需要执行的函数 绑定到 context 上的一个 fn 属性上
* 4、执行 fn 函数 判断 args 是否有 如果没有参数就直接执行 如果有参数 将参数展开传入 fn
* 5、删除 context 对象的 fn 属性 并将 result 返回
*/
Function.prototype.myApply = function (context, args) {
// 判断调用对象, 不是方法直接抛错
if (typeof this !== "function") {
console.error("type error");
}
context = context || window;
// 获取第二个参数
let args = [...arguments][1];
let result = null;
// 将调用该函数的方法设为对象的方法
context.fn = this; // 这里的this就是调用myCall的方法
// 调用函数获取结果
result = args ? context.fn(...args) : context.fn();
// 将属性删除
delete context.fn;
// 返回结果
return result;
};
bind
/** 手写 bind
* 用法：bind() 方法创建一个新的函数, 在 bind() 被调用时, 这个新函数的 this 被指定为 bind() 的第一个参数, 而其余参数将作为新函数的参数, 供调用时使用。
* 思路：
* 1、判断 this 是否指向一个函数 只有函数才可以执行
* 2、获取传入的 context 上下文 也就是我们要指向的 如果不存在就指向 window
* 3、将当前 this 也就是外部需要执行的函数 绑定到 context 上的一个 fn 属性上
* 4、返回一个函数 供外部调用 执行函数后传入新的参数
* 5、执行在闭包内缓存的 fn 将两次参数一起传入 删除 fn 返回 result
*/
Function.prototype.myBind = function (context, ...args1) {
if (typeof this !== "function") {
console.error("type error");
}
context = context || window;
context.fn = this;
// 和 call apply 不一样的是 bind 返回一个函数 需要在外部执行 参数为多个对象 且返回的对象里也会有参数
return function (...args2) {
const result = context.fn(...args1, ...args2);
delete context.fn;
return result;
};
};
函数柯里化
/** 函数柯里化
* 用法：函数柯里化是一种将接受多个参数的函数转换为接受一系列单一参数的函数的技术
* 思路：
* 1、使用 fn.length 获取函数的形参数量
* 2、如果没有传入初始参数数组 则将其初始化为空数组 在递归的时候会接受上一次的形参
* 3、返回一个闭包函数 接受函数的实参 将 args 中的形参和当前的形参进行合并 得到 newArgs
* 4、如果新的参数数组 newArgs 长度大于等于 length 函数的形参数量 调用 apply 执行函数 传入 newArgs
* 5、如果新的参数数组长度小于函数的形参数量 则再次调用 curry 函数 将新的参数数组作为初始参数传入 返回一个新的闭包函数
* @param {*} fn
* @param {*} args
* @return {*}
*/
function curry(fn, args) {
// 获取函数需要的参数长度
const length = fn.length;
// 递归执行时传递的上一次参数 第一次执行 [] 第二次执行 [1]
args = args || [];
return function () {
// 将上一次参数和这次的参数进行合并 得到新的参数数组
const newArgs = [...args, ...arguments];
// 判断参数的长度是否已经满足函数所需参数的长度
if (newArgs.length >= length) {
// 如果满足, 执行函数
return fn.apply(this, newArgs);
} else {
// 小于函数需要的形参长度 递归调用 curry 函数 累积参数 传递 newArgs
return curry(fn, newArgs);
}
};
}
// es 的实现方式
function curry(fn, ...args) {
return fn.length <= args.length ? fn(...args) : curry.bind(null, fn, ...args);
}
数组去重
1. Set 结构
const arr = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8];
const uniqueArr = [...new Set(arr)];
2. 使用 filter 和 indexOf
const uniqueArr = arr.filter((item, index) => {
return arr.indexOf(item) === index;
});
3. 使用 Map 存储
function uniqueArray(array) {
let map = {};
let res = [];
for (var i = 0; i < array.length; i++) {
if (!map.hasOwnProperty([array[i]])) {
map[array[i]] = 1;
res.push(array[i]);
}
}
return res;
}
排序算法
1. 冒泡排序
从数组的第一个元素开始, 依次比较相邻的两个元素, 如果前一个元素大于后一个元素, 就交换它们的位置, 这样大的元素会逐步“冒泡”到数组的末尾。经过一轮比较, 最大的元素会位于数组的最后一个位置。然后继续进行下一轮比较, 但已经排序好的元素不再参与比较。
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
2. 选择排序
在未排序部分选择最小的元素, 然后将其与未排序部分的第一个元素交换, 以此逐步构建已排序部分。在每一轮遍历中, 算法会找到未排序部分的最小元素的索引, 然后与当前轮的第一个元素交换位置, 这样当前轮的第一个元素会是已排序部分的最小元素。 与冒泡排序不同, 选择排序每轮只进行一次交换操作, 因此交换次数相对较少, 性能稍优。
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
3. 插入排序
将数组划分为已排序和未排序两个部分, 初始状态下, 第一个元素被视为已排序部分。然后从未排序部分逐个选择元素插入到已排序部分的正确位置, 以此逐步构建有序数组。 对于每个待插入元素 current, 算法会从已排序部分从后往前遍历, 将比 current 大的元素往后移动一个位置, 直到找到合适的位置插入 current。
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
4. 快速排序
选择一个基准元素（通常是数组的第一个元素）, 然后将数组分成小于基准和大于基准的两个部分。接着, 对这两个部分分别递归地应用快速排序, 最终将所有子数组合并成有序数组。 快速排序的核心是将数组划分为小于基准和大于基准的两部分, 这是通过遍历数组并根据元素与基准的比较结果来实现的。首先选择第一个元素作为基准 pivot, 然后遍历数组的其他元素, 将小于基准的元素放入 left 数组, 将大于基准的元素放入 right 数组。 最后, 递归地对 left 和 right 数组应用快速排序, 然后将排序后的 left 数组、基准元素和排序后的 right 数组依次连接起来, 形成最终有序的数组。
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
5. 归并排序
组递归地划分为两个子数组, 然后分别对这两个子数组进行递归的归并排序, 最后将两个有序子数组合并成一个有序数组。 mergeSort 函数用于递归地将数组划分为子数组, 直到每个子数组只包含一个元素或为空。然后, merge 函数用于将两个有序子数组合并成一个有序数组。在 merge 函数中, 分别设置左子数组和右子数组的索引, 然后依次比较两个子数组的元素, 将较小的元素添加到 result 数组中, 直到其中一个子数组的元素全部添加完毕。然后将剩余子数组的元素依次添加到 result 数组中, 最终得到有序的合并数组。
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
6. 计数排序
统计数组中每个元素出现的次数, 然后根据统计信息构建有序数组。 首先, 通过 Math.min() 和 Math.max() 函数找到数组中的最小值和最大值, 然后确定计数数组的范围。然后, 创建一个 countArr 数组, 用于统计每个元素出现的次数。接着, 遍历原始数组, 将每个元素映射到 countArr 数组中, 并递增对应元素的计数值。 然后, 通过累积计数数组, 将计数数组中的每个元素更新为小于等于当前索引的元素总数。这样, countArr 数组中的值表示原数组中小于等于该元素值的元素总数。 接下来, 从后往前遍历原始数组, 根据元素值从 countArr 中获取位置, 然后将元素放入输出数组 output 中, 同时将对应计数数组的计数值减少 1。 最后, 将 output 数组的值赋给原始数组, 完成排序。
function countingSort(arr) {
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const countArr = new Array(range).fill(0);
const output = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
countArr[arr[i] - min]++;
}
for (let i = 1; i < range; i++) {
countArr[i] += countArr[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
output[countArr[arr[i] - min] - 1] = arr[i];
countArr[arr[i] - min]--;
}
for (let i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
return arr;
}
7. 堆排序
将数组构建成一个堆（通常是最大堆）, 然后不断地将堆顶元素（最大元素）与堆末尾的元素交换, 然后重新调整堆结构, 使得交换后的堆仍然满足堆的性质。这样, 每次交换后, 堆中的最大元素会被置于末尾, 最终形成一个有序的数组。 首先通过 heapify 函数构建初始的最大堆。然后进行两个阶段的循环：第一个循环用于构建最大堆, 从数组的中间位置开始, 依次向前调用 heapify 函数, 使得整个数组满足最大堆的性质；第二个循环用于不断地将堆顶元素与堆末尾元素交换, 并重新调整堆, 直到整个数组有序。
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
8. 希尔排序
将数组分成多个子数组, 分别进行插入排序。初始时, 选取一个递减的间隔值 gap（通常为数组长度的一半）, 然后按照这个间隔将数组分成若干组。然后对每组分别进行插入排序, 不断缩小间隔值, 直到间隔值为 1, 完成最后一次插入排序。 希尔排序的关键在于选择合适的间隔序列, 不同的间隔序列会影响算法的性能。经过一系列的实验和研究, 确定了一些间隔序列, 例如希尔序列（1, 4, 13, 40, 121...）。
function shellSort(arr) {
const n = arr.length;
for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < n; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
return arr;
}
9. 桶排序
将待排序的数据元素分散到不同的桶中, 然后对每个桶内的元素进行排序, 最后将所有桶的元素按顺序合并起来, 形成有序数组。 首先, 通过 Math.min() 和 Math.max() 函数找到数组中的最小值和最大值, 然后确定需要的桶的数量。接着, 创建一个数组 buckets, 用于存放不同的桶, 以及将待排序元素分散到各个桶中。每个元素根据其值映射到相应的桶中。 然后, 对每个桶内的元素进行排序, 这里使用了插入排序作为每个桶内部的排序算法。对每个桶使用插入排序的原因是, 桶的数量可能较小, 而插入排序在小规模数据的排序上性能较好。 最后, 将排序后的各个桶的元素按顺序合并到原始数组中, 完成整个排序过程。
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) {
return arr;
}
const minValue = Math.min(...arr);
const maxValue = Math.max(...arr);
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
const buckets = new Array(bucketCount);
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
for (let i = 0; i < arr.length; i++) {
const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
buckets[bucketIndex].push(arr[i]);
}
arr.length = 0;
for (let i = 0; i < bucketCount; i++) {
insertionSort(buckets[i]);
arr.push(...buckets[i]);
}
return arr;
}
10. 基数排序
将待排序的非负整数按照个位、十位、百位等位数依次进行分配和收集, 从低位到高位逐渐完成排序。 首先, 通过 getMaxDigit 函数找到数组中最大元素的位数。然后, 从个位开始到最高位, 循环进行位数的分配和收集操作。 在每一轮循环中, 创建一个桶列表 bucketList, 其中包含 10 个桶（0 到 9）。然后遍历数组中的每个元素, 根据当前位数的值将元素放入对应的桶中。之后, 将桶列表中的元素按顺序取出并拼接, 更新原数组, 以便进入下一轮循环。 最终, 经过所有位数的循环, 数组中的元素将会被依次排列成有序的序列。
function radixSort(arr) {
const maxDigit = getMaxDigit(arr);
for (let digit = 0; digit < maxDigit; digit++) {
const bucketList = Array.from({ length: 10 }, () => []);
for (let i = 0; i < arr.length; i++) {
const digitValue = getDigitValue(arr[i], digit);
bucketList[digitValue].push(arr[i]);
}
arr = bucketList.flat();
}
return arr;
}
function getMaxDigit(arr) {
let max = 0;
for (let i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i].toString().length);
}
return max;
}
function getDigitValue(num, digit) {
return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
}
ajax
// 根据浏览器支持与否, 动态创建一个兼容性更好的 XHR 对象
let $ = {
createXHR: function () {
// 若浏览器支持, 则创建XMLHttpRequest对象
if (window.XMLHttpRequest) {
return new XMLHttpRequest();
}
// 若不支持, 则创建ActiveXobject对象
else {
return new ActiveXObject();
}
},
};
// 封装 get 方法
/*
parmas:
URL: 请求的url地址
data: 携带的参数
callback: 成功回调函数
dataType: 返回数据的类型
*/
let $ = {
// 动态生成XHR对象的方法
createXHR: function () {
if (window.XMLHttpRequest) {
return new XMLHttpRequest();
} else {
return new ActiveXObject();
}
},
get: function (url, data, callback, dataType) {
// 避免dataType大小写的问题
let dataType = dataType.toLowerCase();
// 如果有传入data, 则在url后面跟上参数
if (data) {
url += "?";
Object.keys(data).forEach((key) => (url += `${key}=${data[key]}&`));
url = url.slice(0, -1);
}
// 调用我们封装的方法生成XHR对象
let xhr = this.createXHR();
// 创建get请求
xhr.open("get", url);
// 发送请求
xhr.send();
xhr.onreadystatechange = function () {
if (xhr.readyState === 4) {
if ((xhr.status >= 200 && xhr.status < 300) || xhr.status == 304) {
// 若dataType为json, 则将返回的数据通过JSON.parse格式化
let res =
dataType === "json"
? JSON.parse(xhr.responseText)
: xhr.responseText;
// 调用回调函数, 并把参数传进去
callback(res, xhr.status, xhr);
}
}
};
},
};
// 封装 post 方法
let $ = {
// ...,
post: function (url, data, callback, dataType) {
// 避免dataType大小写的问题
let dataType = dataType.toLowerCase();
// 调用我们封装的方法动态生成XHR对象
let xhr = this.createXHR();
let str = "";
// 若传入参数, 则将参数序列化
if (data) {
Object.keys(data).forEach((key) => (str += `${key}=${data[key]}&`));
str = str.slice(0, -1);
}
// 设置头部信息
xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
// 发送请求, 并携带参数
xhr.send(str);
xhr.onreadystatechange = function () {
if (xhr.readyState === 4) {
if ((xhr.status >= 200 && xhr.status < 300) || xhr.status == 304) {
// 若dataType为json, 则将返回的数据通过JSON.parse格式化
let res =
dataType === "json"
? JSON.parse(xhr.responseText)
: xhr.responseText;
// 调用回调函数, 把对应参数传进去
callback(res, xhr.status, xhr);
}
}
};
},
};
// 封装 ajax 方法, 既可以发送 get 请求, 也可以发送 post 请求, 该方法可传入多种参数, 且支持 promise 处理回调函数
let $ = {
// ...,
ajax: function (params) {
// 初始化参数
let type = params.type ? params.type.toLowerCase() : "get";
let isAsync = params.isAsync ? params.isAsync : "true";
let url = params.url;
let data = params.data ? params.data : {};
let dataType = params.dataType.toLowerCase();
// 用我们封装的方法动态生成XHR对象
let xhr = this.createXHR();
let str = "";
// 拼接字符串
Object.keys(data).forEach((key) => (str += `${key}=${data[key]}&`));
str = str.slice(0, -1);
// 如果是get请求就把携带参数拼接到url后面
if (type === "get") url += `?${str}`;
// 返回promise对象, 便于外部then和catch函数调用
return new Promise((resolve, reject) => {
// 创建请求
xhr.open(type, url, isAsync);
if (type === "post") {
xhr.setRequestHeader(
"Content-Type",
"application/x-www-form-rulencoded"
);
xhr.send(str);
} else {
xhr.send();
}
xhr.onreadystatechange = function () {
if (xhr.readyState === 4) {
if ((xhr.status >= 200 && xhr.status < 300) || xhr.status == 304) {
let res =
dataType === "json"
? JSON.parse(xhr.responseText)
: xhr.responseText;
resolve(res); // 请求成功, 返回数据
} else {
reject(xhr.status); // 请求失败, 返回状态码
}
}
};
});
},
};