JavaScript 数组方法背后的算法-js教程-PHP中文网

首页

web前端

js教程

JavaScript 数组方法背后的算法

Susan Sarandon

Nov 03, 2024 am 07:10 AM

Algorithms Behind JavaScript Array Methods

JavaScript 数组方法背后的算法。

JavaScript 数组带有各种内置方法，允许操作和检索数组中的数据。以下是从大纲中提取的数组方法列表：

concat()
加入()
填充()
包括()
indexOf()
反向()
排序()
拼接()
在()
copyWithin()
平()
Array.from()
findLastIndex()
forEach()
每个()
条目()
值()
toReversed()（创建数组的反向副本而不修改原始数组）
toSorted()（创建数组的排序副本而不修改原始数组）
toSpliced()（创建一个新数组，添加或删除元素，而不修改原始数组）
with()（返回替换了特定元素的数组副本）
Array.fromAsync()
Array.of()
地图()
flatMap()
减少()
reduceRight()
一些()
查找()
findIndex()
findLast()

让我分解一下每个 JavaScript 数组方法所使用的常用算法：

1. concat()

算法：线性追加/合并
时间复杂度：O(n)，其中 n 是所有数组的总长度
内部使用迭代来创建新数组并复制元素

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

登录后复制

2. 加入（）

算法：字符串连接的线性遍历
时间复杂度：O(n)
迭代数组元素并构建结果字符串

// join()
Array.prototype.myJoin = function(separator = ',') {
  let result = '';
  for (let i = 0; i < this.length; i++) {
    result += this[i];
    if (i < this.length - 1) result += separator;
  }
  return result;
};

登录后复制

3. 填充（）

算法：带赋值的线性遍历
时间复杂度：O(n)
带有赋值的简单迭代

// fill()
Array.prototype.myFill = function(value, start = 0, end = this.length) {
  for (let i = start; i < end; i++) {
    this[i] = value;
  }
  return this;
};

登录后复制

4. 包含()

算法：线性搜索
时间复杂度：O(n)
顺序扫描直到找到元素或到达结束

// includes()
Array.prototype.myIncludes = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement || (Number.isNaN(this[i]) && Number.isNaN(searchElement))) {
      return true;
    }
  }
  return false;
};

登录后复制

5.indexOf()

算法：线性搜索
时间复杂度：O(n)
从开始顺序扫描直到找到匹配

// indexOf()
Array.prototype.myIndexOf = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement) return i;
  }
  return -1;
};

登录后复制

6. 反向()

算法：两指针交换
时间复杂度：O(n/2)
从开始/结束向内移动元素

// reverse()
Array.prototype.myReverse = function() {
  let left = 0;
  let right = this.length - 1;

  while (left < right) {
    // Swap elements
    const temp = this[left];
    this[left] = this[right];
    this[right] = temp;
    left++;
    right--;
  }

  return this;
};

登录后复制

7. 排序（）

算法：通常为 TimSort（合并排序和插入排序的混合）
时间复杂度：O(n log n)
现代浏览器使用自适应排序算法

// sort()
Array.prototype.mySort = function(compareFn) {
  // Implementation of QuickSort for simplicity
  // Note: Actual JS engines typically use TimSort
  const quickSort = (arr, low, high) => {
    if (low < high) {
      const pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  };

  const partition = (arr, low, high) => {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      const compareResult = compareFn ? compareFn(arr[j], pivot) : String(arr[j]).localeCompare(String(pivot));
      if (compareResult <= 0) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  };

  quickSort(this, 0, this.length - 1);
  return this;
};

登录后复制

8. 拼接（）

算法：线性数组修改
时间复杂度：O(n)
就地移动元素并修改数组

// splice()
Array.prototype.mySplice = function(start, deleteCount, ...items) {
  const len = this.length;
  const actualStart = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  const actualDeleteCount = Math.min(Math.max(deleteCount || 0, 0), len - actualStart);

  // Store deleted elements
  const deleted = [];
  for (let i = 0; i < actualDeleteCount; i++) {
    deleted[i] = this[actualStart + i];
  }

  // Shift elements if necessary
  const itemCount = items.length;
  const shiftCount = itemCount - actualDeleteCount;

  if (shiftCount > 0) {
    // Moving elements right
    for (let i = len - 1; i >= actualStart + actualDeleteCount; i--) {
      this[i + shiftCount] = this[i];
    }
  } else if (shiftCount < 0) {
    // Moving elements left
    for (let i = actualStart + actualDeleteCount; i < len; i++) {
      this[i + shiftCount] = this[i];
    }
  }

  // Insert new items
  for (let i = 0; i < itemCount; i++) {
    this[actualStart + i] = items[i];
  }

  this.length = len + shiftCount;
  return deleted;
};

登录后复制

9. 在()

算法：直接索引访问
时间复杂度：O(1)
带有边界检查的简单数组索引

// at()
Array.prototype.myAt = function(index) {
  const actualIndex = index >= 0 ? index : this.length + index;
  return this[actualIndex];
};

登录后复制

10. 复制（）

算法：块内存复制
时间复杂度：O(n)
内存复制和移位操作

// copyWithin()
Array.prototype.myCopyWithin = function(target, start = 0, end = this.length) {
  const len = this.length;
  let to = target < 0 ? Math.max(len + target, 0) : Math.min(target, len);
  let from = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  let final = end < 0 ? Math.max(len + end, 0) : Math.min(end, len);
  const count = Math.min(final - from, len - to);

  // Copy to temporary array to handle overlapping
  const temp = new Array(count);
  for (let i = 0; i < count; i++) {
    temp[i] = this[from + i];
  }

  for (let i = 0; i < count; i++) {
    this[to + i] = temp[i];
  }

  return this;
};

登录后复制

11. 平（）

算法：递归深度优先遍历
时间复杂度：单层为 O(n)，深度 d 为 O(d*n)
递归展平嵌套数组

// flat()
Array.prototype.myFlat = function(depth = 1) {
  const flatten = (arr, currentDepth) => {
    const result = [];
    for (const item of arr) {
      if (Array.isArray(item) && currentDepth < depth) {
        result.push(...flatten(item, currentDepth + 1));
      } else {
        result.push(item);
      }
    }
    return result;
  };

  return flatten(this, 0);
};

登录后复制

12. 数组.from()

算法：迭代和复制
时间复杂度：O(n)
从可迭代创建新数组

// Array.from()
Array.myFrom = function(arrayLike, mapFn) {
  const result = [];
  for (let i = 0; i < arrayLike.length; i++) {
    result[i] = mapFn ? mapFn(arrayLike[i], i) : arrayLike[i];
  }
  return result;
};

登录后复制

13. 查找最后一个索引()

算法：反向线性搜索
时间复杂度：O(n)
从末尾开始顺序扫描直到找到匹配项

// findLastIndex()
Array.prototype.myFindLastIndex = function(predicate) {
  for (let i = this.length - 1; i >= 0; i--) {
    if (predicate(this[i], i, this)) return i;
  }
  return -1;
};

登录后复制

14. forEach()

算法：线性迭代
时间复杂度：O(n)
带有回调执行的简单迭代

// forEach()
Array.prototype.myForEach = function(callback) {
  for (let i = 0; i < this.length; i++) {
    if (i in this) {  // Skip holes in sparse arrays
      callback(this[i], i, this);
    }
  }
};

登录后复制

15. 每个（）

算法：短路线性扫描
时间复杂度：O(n)
在第一个错误条件下停止

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

登录后复制

16. 条目()

算法：迭代器协议实现
时间复杂度：创建 O(1)，完整迭代 O(n)
创建迭代器对象

// join()
Array.prototype.myJoin = function(separator = ',') {
  let result = '';
  for (let i = 0; i < this.length; i++) {
    result += this[i];
    if (i < this.length - 1) result += separator;
  }
  return result;
};

登录后复制

17. 值（）

算法：迭代器协议实现
时间复杂度：创建 O(1)，完整迭代 O(n)
为值创建迭代器

// fill()
Array.prototype.myFill = function(value, start = 0, end = this.length) {
  for (let i = start; i < end; i++) {
    this[i] = value;
  }
  return this;
};

登录后复制

18. toReversed()

算法：反向迭代复制
时间复杂度：O(n)
创建新的反转数组

// includes()
Array.prototype.myIncludes = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement || (Number.isNaN(this[i]) && Number.isNaN(searchElement))) {
      return true;
    }
  }
  return false;
};

登录后复制

19. toSorted()

算法：复制然后 TimSort
时间复杂度：O(n log n)
使用标准排序创建排序副本

// indexOf()
Array.prototype.myIndexOf = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement) return i;
  }
  return -1;
};

登录后复制

20. toSpliced()

算法：修改复制
时间复杂度：O(n)
创建修改后的副本

// reverse()
Array.prototype.myReverse = function() {
  let left = 0;
  let right = this.length - 1;

  while (left < right) {
    // Swap elements
    const temp = this[left];
    this[left] = this[right];
    this[right] = temp;
    left++;
    right--;
  }

  return this;
};

登录后复制

21. 与()

算法：单次修改的浅拷贝
时间复杂度：O(n)
创建更改了一个元素的副本

// sort()
Array.prototype.mySort = function(compareFn) {
  // Implementation of QuickSort for simplicity
  // Note: Actual JS engines typically use TimSort
  const quickSort = (arr, low, high) => {
    if (low < high) {
      const pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  };

  const partition = (arr, low, high) => {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      const compareResult = compareFn ? compareFn(arr[j], pivot) : String(arr[j]).localeCompare(String(pivot));
      if (compareResult <= 0) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  };

  quickSort(this, 0, this.length - 1);
  return this;
};

登录后复制

22. Array.fromAsync()

算法：异步迭代和收集
时间复杂度：O(n) 异步操作
处理承诺和异步迭代

// splice()
Array.prototype.mySplice = function(start, deleteCount, ...items) {
  const len = this.length;
  const actualStart = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  const actualDeleteCount = Math.min(Math.max(deleteCount || 0, 0), len - actualStart);

  // Store deleted elements
  const deleted = [];
  for (let i = 0; i < actualDeleteCount; i++) {
    deleted[i] = this[actualStart + i];
  }

  // Shift elements if necessary
  const itemCount = items.length;
  const shiftCount = itemCount - actualDeleteCount;

  if (shiftCount > 0) {
    // Moving elements right
    for (let i = len - 1; i >= actualStart + actualDeleteCount; i--) {
      this[i + shiftCount] = this[i];
    }
  } else if (shiftCount < 0) {
    // Moving elements left
    for (let i = actualStart + actualDeleteCount; i < len; i++) {
      this[i + shiftCount] = this[i];
    }
  }

  // Insert new items
  for (let i = 0; i < itemCount; i++) {
    this[actualStart + i] = items[i];
  }

  this.length = len + shiftCount;
  return deleted;
};

登录后复制

23. 数组.of()

算法：直接创建数组
时间复杂度：O(n)
从参数创建数组

// at()
Array.prototype.myAt = function(index) {
  const actualIndex = index >= 0 ? index : this.length + index;
  return this[actualIndex];
};

登录后复制

24. 地图（）

算法：变换迭代
时间复杂度：O(n)
使用转换后的元素创建新数组

// copyWithin()
Array.prototype.myCopyWithin = function(target, start = 0, end = this.length) {
  const len = this.length;
  let to = target < 0 ? Math.max(len + target, 0) : Math.min(target, len);
  let from = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  let final = end < 0 ? Math.max(len + end, 0) : Math.min(end, len);
  const count = Math.min(final - from, len - to);

  // Copy to temporary array to handle overlapping
  const temp = new Array(count);
  for (let i = 0; i < count; i++) {
    temp[i] = this[from + i];
  }

  for (let i = 0; i < count; i++) {
    this[to + i] = temp[i];
  }

  return this;
};

登录后复制

25. 平面地图()

算法：地图展平
时间复杂度：O(n*m)，其中 m 是平均映射数组大小
结合了映射和展平

// flat()
Array.prototype.myFlat = function(depth = 1) {
  const flatten = (arr, currentDepth) => {
    const result = [];
    for (const item of arr) {
      if (Array.isArray(item) && currentDepth < depth) {
        result.push(...flatten(item, currentDepth + 1));
      } else {
        result.push(item);
      }
    }
    return result;
  };

  return flatten(this, 0);
};

登录后复制

26. 减少（）

算法：线性累加
时间复杂度：O(n)
带回调的顺序累加

// Array.from()
Array.myFrom = function(arrayLike, mapFn) {
  const result = [];
  for (let i = 0; i < arrayLike.length; i++) {
    result[i] = mapFn ? mapFn(arrayLike[i], i) : arrayLike[i];
  }
  return result;
};

登录后复制

27.reduceRight()

算法：反向线性累加
时间复杂度：O(n)
从右到左累积

// findLastIndex()
Array.prototype.myFindLastIndex = function(predicate) {
  for (let i = this.length - 1; i >= 0; i--) {
    if (predicate(this[i], i, this)) return i;
  }
  return -1;
};

登录后复制

28. 一些（）

算法：短路线性扫描
时间复杂度：O(n)
在第一个真实条件下停止

// forEach()
Array.prototype.myForEach = function(callback) {
  for (let i = 0; i < this.length; i++) {
    if (i in this) {  // Skip holes in sparse arrays
      callback(this[i], i, this);
    }
  }
};

登录后复制

29. 查找（）

算法：线性搜索
时间复杂度：O(n)
顺序扫描直到条件满足

// every()
Array.prototype.myEvery = function(predicate) {
  for (let i = 0; i < this.length; i++) {
    if (i in this && !predicate(this[i], i, this)) {
      return false;
    }
  }
  return true;
};

登录后复制

30. 查找索引()

算法：线性搜索
时间复杂度：O(n)
顺序扫描匹配条件

// entries()
Array.prototype.myEntries = function() {
  let index = 0;
  const array = this;

  return {
    [Symbol.iterator]() {
      return this;
    },
    next() {
      if (index < array.length) {
        return { value: [index, array[index++]], done: false };
      }
      return { done: true };
    }
  };
};

登录后复制

31. 查找最后一个()

算法：反向线性搜索
时间复杂度：O(n)
从末尾开始顺序扫描

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

登录后复制

我已经提供了您请求的所有 31 种数组方法的完整实现。