JavaScript 數(shù)組方法背后的算法。

JavaScript 數(shù)組帶有各種內(nèi)置方法，允許操作和檢索數(shù)組中的數(shù)據(jù)。以下是從大綱中提取的數(shù)組方法列表：

1. concat()
2. 加入()
3. 填充()
4. 包括()
5. indexOf()
6. 反向()
7. 排序()
8. 拼接()
9. 在()
10. copyWithin()
11. 平()
12. Array.from()
13. findLastIndex()
14. forEach()
15. 每個()
16. 條目()
17. 值()
18. toReversed()（創(chuàng)建數(shù)組的反向副本而不修改原始數(shù)組）
19. toSorted()（創(chuàng)建數(shù)組的排序副本而不修改原始數(shù)組）
20. toSpliced()（創(chuàng)建一個新數(shù)組，添加或刪除元素，而不修改原始數(shù)組）
21. with()（返回替換了特定元素的數(shù)組副本）
22. Array.fromAsync()
23. Array.of()
24. 地圖()
25. flatMap()
26. 減少()
27. reduceRight()
28. 一些()
29. 查找()
30. findIndex()
31. findLast()

讓我分解一下每個 JavaScript 數(shù)組方法所使用的常用算法：

1. concat()

• 算法：線性追加/合并
• 時間復(fù)雜度：O(n)，其中 n 是所有數(shù)組的總長度
• 內(nèi)部使用迭代來創(chuàng)建新數(shù)組并復(fù)制元素

// 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. 加入（）

• 算法：字符串連接的線性遍歷
• 時間復(fù)雜度：O(n)
• 迭代數(shù)組元素并構(gòu)建結(jié)果字符串

// 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. 填充（）

• 算法：帶賦值的線性遍歷
• 時間復(fù)雜度：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. 包含()

• 算法：線性搜索
• 時間復(fù)雜度：O(n)
• 順序掃描直到找到元素或到達結(jié)束

// 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()

• 算法：線性搜索
• 時間復(fù)雜度：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. 反向()

• 算法：兩指針交換
• 時間復(fù)雜度：O(n/2)
• 從開始/結(jié)束向內(nèi)移動元素

// 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（合并排序和插入排序的混合）
• 時間復(fù)雜度：O(n log n)
• 現(xiàn)代瀏覽器使用自適應(yīng)排序算法

// 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. 拼接（）

• 算法：線性數(shù)組修改
• 時間復(fù)雜度：O(n)
• 就地移動元素并修改數(shù)組

// 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. 在()

• 算法：直接索引訪問
• 時間復(fù)雜度：O(1)
• 帶有邊界檢查的簡單數(shù)組索引

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

10. 復(fù)制（）

• 算法：塊內(nèi)存復(fù)制
• 時間復(fù)雜度：O(n)
• 內(nèi)存復(fù)制和移位操作

// 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. 平（）

• 算法：遞歸深度優(yōu)先遍歷
• 時間復(fù)雜度：單層為 O(n)，深度 d 為 O(d*n)
• 遞歸展平嵌套數(shù)組

// 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. 數(shù)組.from()

• 算法：迭代和復(fù)制
• 時間復(fù)雜度：O(n)
• 從可迭代創(chuàng)建新數(shù)組

// 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. 查找最后一個索引()

• 算法：反向線性搜索
• 時間復(fù)雜度：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()

• 算法：線性迭代
• 時間復(fù)雜度：O(n)
• 帶有回調(diào)執(zhí)行的簡單迭代

// 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. 每個（）

算法：短路線性掃描
時間復(fù)雜度：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. 條目()

• 算法：迭代器協(xié)議實現(xiàn)
• 時間復(fù)雜度：創(chuàng)建 O(1)，完整迭代 O(n)
• 創(chuàng)建迭代器對象

// 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. 值（）

• 算法：迭代器協(xié)議實現(xiàn)
• 時間復(fù)雜度：創(chuàng)建 O(1)，完整迭代 O(n)
• 為值創(chuàng)建迭代器

// 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()

• 算法：反向迭代復(fù)制
• 時間復(fù)雜度：O(n)
• 創(chuàng)建新的反轉(zhuǎn)數(shù)組

// 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()

• 算法：復(fù)制然后 TimSort
• 時間復(fù)雜度：O(n log n)
• 使用標(biāo)準(zhǔn)排序創(chuàng)建排序副本

// 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()

• 算法：修改復(fù)制
• 時間復(fù)雜度：O(n)
• 創(chuàng)建修改后的副本

// 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. 與()

• 算法：單次修改的淺拷貝
• 時間復(fù)雜度：O(n)
• 創(chuàng)建更改了一個元素的副本

// 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()

• 算法：異步迭代和收集
• 時間復(fù)雜度：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. 數(shù)組.of()

• 算法：直接創(chuàng)建數(shù)組
• 時間復(fù)雜度：O(n)
• 從參數(shù)創(chuàng)建數(shù)組

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

24. 地圖（）

• 算法：變換迭代
• 時間復(fù)雜度：O(n)
• 使用轉(zhuǎn)換后的元素創(chuàng)建新數(shù)組

// 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. 平面地圖()

• 算法：地圖展平
• 時間復(fù)雜度：O(n*m)，其中 m 是平均映射數(shù)組大小
• 結(jié)合了映射和展平

// 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. 減少（）

• 算法：線性累加
• 時間復(fù)雜度：O(n)
• 帶回調(diào)的順序累加

// 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()

• 算法：反向線性累加
• 時間復(fù)雜度：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. 一些（）

• 算法：短路線性掃描
• 時間復(fù)雜度：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. 查找（）

• 算法：線性搜索
• 時間復(fù)雜度：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. 查找索引()

• 算法：線性搜索
• 時間復(fù)雜度：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. 查找最后一個()

• 算法：反向線性搜索
• 時間復(fù)雜度：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;
};

我已經(jīng)提供了您請求的所有 31 種數(shù)組方法的完整實現(xiàn)。

？在 LinkedIn 上與我聯(lián)系：

讓我們一起深入了解軟件工程的世界！我定期分享有關(guān) JavaScript、TypeScript、Node.js、React、Next.js、數(shù)據(jù)結(jié)構(gòu)、算法、Web 開發(fā)等方面的見解。無論您是想提高自己的技能還是在令人興奮的主題上進行合作，我都樂意與您聯(lián)系并與您一起成長。

跟我來：Nozibul Islam

以上是JavaScript 數(shù)組方法背后的算法的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！