JavaScript算法实现与编程练习
排序算法实现
1. 冒泡排序
原理：依次比较相邻元素，每次排序确定一个最大元素的位置
时间复杂度：O(n²)，空间复杂度：O(1)
外层循环：每轮确定一个最大元素，比较范围逐渐缩小
内层循环：从前往后比较相邻元素，交换位置
class DataList {
bubbleSort() {
const size = this.data.length;
// 外层循环控制比较范围，每轮确定一个最大元素
for (let boundary = size - 1; boundary > 0; boundary--) {
// 内层循环进行相邻元素比较
for (let index = 0; index < boundary; index++) {
// 升序排列，如果前一个元素大于后一个元素，则交换
if (this.data[index] > this.data[index + 1]) {
// 使用解构赋值实现元素交换
[this.data[index], this.data[index + 1]] = [this.data[index + 1], this.data[index]];
}
}
}
}
}
2. 选择排序
原理：每次从未排序部分选择最小元素，放到已排序部分的末尾
时间复杂度：O(n²)，空间复杂度：O(1)
外层循环：遍历所有元素
内层循环：找到未排序部分的最小元素
class DataList {
selectionSort() {
const size = this.data.length;
// 外层循环，逐个确定最小元素的位置
for (let current = 0; current < size - 1; current++) {
// 假设当前元素是最小的
let minIndex = current;
// 内层循环，在剩余元素中寻找最小值
for (let compare = minIndex + 1; compare < size; compare++) {
if (this.data[minIndex] > this.data[compare]) {
// 更新最小元素的索引
minIndex = compare;
}
}
// 将找到的最小元素与当前位置交换
[this.data[minIndex], this.data[current]] = [this.data[current], this.data[minIndex]];
}
}
}
3. 插入排序
原理：维护一个有序序列，将未排序元素插入到适当位置
时间复杂度：O(n²)，空间复杂度：O(1)
外层循环：从第二个元素开始，依次处理每个元素
内层循环：将当前元素插入到已排序部分的适当位置
class DataList {
insertSort() {
const size = this.data.length;
// 外层循环，从第二个元素开始，依次插入到已排序部分
for (let i = 1; i < size; i++) {
// 保存当前待插入元素
const current = this.data[i];
let j = i;
// 将比当前元素大的元素向后移动
while (j > 0 && this.data[j - 1] > current) {
this.data[j] = this.data[j - 1];
j--;
}
// 将当前元素插入到正确位置
this.data[j] = current;
}
}
}
4. 希尔排序
原理：通过分组进行插入排序，逐渐减小分组间隔
时间复杂度：O(n^(1.3-2))，空间复杂度：O(1)
外层循环：控制分组间隔，逐渐减小
内层循环：在各分组内进行插入排序
class DataList {
shellSort() {
const size = this.data.length;
// 初始化分组间隔
let gap = Math.floor(size / 2);
// 不断减小分组间隔，直到间隔为1
while (gap >= 1) {
// 对每个分组进行插入排序
for (let i = gap; i < size; i++) {
const current = this.data[i];
let j = i;
// 在分组内进行插入排序
while (j >= gap && this.data[j - gap] > current) {
this.data[j] = this.data[j - gap];
j -= gap;
}
// 插入到正确位置
this.data[j] = current;
}
// 减小分组间隔
gap = Math.floor(gap / 2);
}
}
}
5. 快速排序
原理：使用分治策略，通过基准值将数组分为两部分，递归排序
时间复杂度：平均O(n log n)，最坏O(n²)，空间复杂度：O(log n)
双指针法：分别从两端向中间遍历，交换不符合条件的元素
function quickSort(arr, left = 0, right = arr.length - 1) {
// 递归终止条件
if (left < right) {
// 选择基准值
const pivot = arr[left];
let i = left;
let j = right;
// 双指针遍历
while (i < j) {
// 从右向左寻找比基准小的元素
while (i < j && arr[j] > pivot) {
j--;
}
// 将找到的元素交换到左侧
arr[i] = arr[j];
// 从左向右寻找比基准大的元素
while (i < j && arr[i] < pivot) {
i++;
}
// 将找到的元素交换到右侧
arr[j] = arr[i];
}
// 将基准值放到正确位置
arr[i] = pivot;
// 递归排序基准值左侧和右侧
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
return arr;
}
JavaScript手写实现
1. Object.create 实现
创建一个新对象，其原型指向指定的对象
function create(proto) {
// 创建一个构造函数
function TempConstructor() {}
// 设置构造函数的原型
TempConstructor.prototype = proto;
// 返回构造函数的实例
return new TempConstructor();
}
// 测试用例
const nullObject = create(null);
console.log(nullObject);
2. instanceof 实现
判断一个对象是否属于某个构造函数的实例
function myInstanceof(obj, constructor) {
// 获取对象的原型
let proto = Object.getPrototypeOf(obj);
// 获取构造函数的原型
const prototype = constructor.prototype;
// 向上遍历原型链
while (proto !== null) {
if (proto === prototype) {
return true;
}
proto = Object.getPrototypeOf(proto);
}
return false;
}
// 测试用例
const array = [1, 2, 3];
console.log(myInstanceof(array, Array)); // true
3. new 操作符实现
模拟 new 操作符的行为，创建实例并初始化
function newOperator(constructor, ...args) {
// 创建一个新对象
const obj = {};
// 设置对象的原型
Object.setPrototypeOf(obj, constructor.prototype);
// 执行构造函数，绑定 this
const result = constructor.apply(obj, args);
// 如果构造函数返回对象，则返回该对象，否则返回新创建的对象
return (result && typeof result === 'object') ? result : obj;
}
// 测试用例
function Person(name, age) {
this.name = name;
this.age = age;
return { name: '张三', age: 18 };
}
const person = newOperator(Person, 'Hugh', 24);
console.log(person);
4. Promise.all 实现
接收多个 Promise 实例，返回一个新的 Promise，所有 Promise 都成功时才成功
function all(promises) {
return new Promise((resolve, reject) => {
// 参数检查
if (!Array.isArray(promises)) {
throw new Error('参数必须是一个数组');
}
const results = [];
const count = promises.length;
let completed = 0;
// 遍历所有 Promise
for (let i = 0; i < count; i++) {
// 处理每个 Promise
Promise.resolve(promises[i]).then(
// 成功回调
value => {
completed++;
results[i] = value;
// 所有 Promise 都完成时， resolve 结果数组
if (completed === count) {
resolve(results);
}
},
// 失败回调
error => {
reject(error);
}
);
}
});
}
// 测试用例
const p1 = new Promise(resolve => setTimeout(() => resolve(1), 1000));
const p2 = new Promise(resolve => setTimeout(() => resolve(2), 2000));
all([p1, p2]).then(results => {
console.log(results); // [1, 2]
}).catch(error => {
console.error(error);
});
5. Promise.race 实现
接收多个 Promise 实例，返回一个新的 Promise，最先完成的 Promise 的结果作为结果
Promise.race = function(promises) {
return new Promise((resolve, reject) => {
// 遍历所有 Promise
for (let i = 0; i < promises.length; i++) {
// 处理每个 Promise，一旦有完成就 resolve 或 reject
promises[i].then(resolve, reject);
}
});
};
// 测试用例
const p1 = new Promise(resolve => setTimeout(() => resolve(1), 1000));
const p2 = new Promise(resolve => setTimeout(() => resolve(2), 2000));
Promise.race([p1, p2]).then(result => {
console.log(result); // 1
}).catch(error => {
console.error(error);
});
6. 防抖函数实现
函数在触发后等待一段时间再执行，如果在等待时间内再次触发，则重新计时
function debounce(func, delay) {
let timer = null;
return function(...args) {
const context = this;
// 清除之前的定时器
if (timer) {
clearTimeout(timer);
}
// 设置新的定时器
timer = setTimeout(() => {
func.apply(context, args);
timer = null;
}, delay);
};
}
7. 节流函数实现
函数在触发后立即执行，并在指定时间内不再执行，直到时间结束
// 使用时间戳实现，会立即执行
function throttle(func, limit) {
let lastTime = 0;
return function(...args) {
const context = this;
const now = Date.now();
if (now - lastTime >= limit) {
func.apply(context, args);
lastTime = now;
}
};
}
// 使用定时器实现，不会立即执行，但会在最后一次触发后执行
function throttleWithTimer(func, limit) {
let timer = null;
return function(...args) {
const context = this;
if (!timer) {
timer = setTimeout(() => {
func.apply(context, args);
timer = null;
}, limit);
}
};
}
8. 类型判断函数
准确判断 JavaScript 数据类型
function getType(value) {
// 处理 null 值
if (value === null) {
return 'null';
}
// 处理基本类型
if (typeof value !== 'object') {
return typeof value;
}
// 处理对象类型
const typeString = Object.prototype.toString.call(value);
// 提取类型名称
return typeString.slice(8, -1).toLowerCase();
}
// 测试用例
console.log(getType(null)); // 'null'
console.log(getType(undefined)); // 'undefined'
console.log(getType(123)); // 'number'
console.log(getType('abc')); // 'string'
console.log(getType(true)); // 'boolean'
console.log(getType({})); // 'object'
console.log(getType([])); // 'array'
console.log(getType(function() {})); // 'function'
