JavaScript 陣列方法背後的演算法。

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

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

讓我分解每個(gè) JavaScript 陣列方法所使用的常用演算法：

1. concat()

• 演算法：線(xiàn)性追加/合併
• 時(shí)間複雜度：O(n)，其中 n 是所有陣列的總長(zhǎng)度
• 內(nèi)部使用迭代來(lái)建立新數(shù)組並複製元素

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

• 演算法：字串連接的線(xiàn)性遍歷
• 時(shí)間複雜度：O(n)
• 迭代數(shù)組元素並建立結(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. 填充（）

• 演算法：帶賦值的線(xiàn)性遍歷
• 時(shí)間複雜度：O(n)
• 帶有賦值的簡(jiǎ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. 包含()

• 演算法：線(xiàn)性搜尋
• 時(shí)間複雜度：O(n)
• 順序掃描直到找到元素或到達(dá)結(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()

• 演算法：線(xiàn)性搜尋
• 時(shí)間複雜度：O(n)
• 從開(kāi)始順序掃描直到找到匹配

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

• 演算法：兩個(gè)指標(biāo)交換
• 時(shí)間複雜度：O(n/2)
• 從開(kāi)始/結(jié)束向內(nèi)移動(dò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;
};

7. 排序（）

• 演算法：通常為 TimSort（合併排序和插入排序的混合）
• 時(shí)間複雜度：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. 拼接（）

• 演算法：線(xiàn)性數(shù)組修改
• 時(shí)間複雜度：O(n)
• 就地移動(dòng)元素並修改數(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. 在()

• 演算法：直接索引存取
• 時(shí)間複雜度：O(1)
• 帶有邊界檢查的簡(jiǎn)單數(shù)組索引

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

10. 複製（）

• 演算法：區(qū)塊記憶體複製
• 時(shí)間複雜度：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. 平（）

• 演算法：遞歸深度優(yōu)先遍歷
• 時(shí)間複雜度：?jiǎn)螌訛?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()

• 演算法：迭代與複製
• 時(shí)間複雜度：O(n)
• 從可迭代建立新數(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. 找出最後一個(gè)索引()

• 演算法：反向線(xiàn)性搜尋
• 時(shí)間複雜度：O(n)
• 從末尾開(kāi)始順序掃描直到找到匹配項(xiàng)

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

• 演算法：線(xiàn)性迭代
• 時(shí)間複雜度：O(n)
• 帶有回呼執(zhí)行的簡(jiǎ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. 每個(gè)（）

演算法：短路線(xiàn)性?huà)呙?br> 時(shí)間複雜度：O(n)
在第一個(gè)錯(cuò)誤條件下停止

// 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é)定實(shí)作
• 時(shí)間複雜度：建立 O(1)，完整迭代 O(n)
• 建立迭代器對(duì)象

// 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é)定實(shí)作
• 時(shí)間複雜度：建立 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()

• 演算法：反向迭代複製
• 時(shí)間複雜度：O(n)
• 建立新的反轉(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()

• 演算法：複製然後 TimSort
• 時(shí)間複雜度：O(n log n)
• 使用標(biāo)準(zhǔ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()

• 演算法：修改複製
• 時(shí)間複雜度：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. 與()

• 演算法：?jiǎn)未涡薷牡臏\拷貝
• 時(shí)間複雜度：O(n)
• 建立更改了一個(gè)元素的副本

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

• 演算法：非同步迭代與收集
• 時(shí)間複雜度：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()

• 演算法：直接建立陣列
• 時(shí)間複雜度：O(n)
• 從參數(shù)建立數(shù)組

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

24. 地圖（）

• 演算法：變換迭代
• 時(shí)間複雜度：O(n)
• 使用轉(zhuǎn)換後的元素建立新數(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. 平面地圖()

• 演算法：地圖展平
• 時(shí)間複雜度：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. 減少（）

• 演算法：線(xiàn)性累加
• 時(shí)間複雜度：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()

• 演算法：反向線(xiàn)性累加
• 時(shí)間複雜度：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. 一些（）

• 演算法：短路線(xiàn)性?huà)呙?/li>
• 時(shí)間複雜度：O(n)
• 在第一個(gè)真實(shí)條件下停止

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

• 演算法：線(xiàn)性搜尋
• 時(shí)間複雜度：O(n)
• 順序掃描直到條件滿(mǎ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. 尋找索引()

• 演算法：線(xiàn)性搜尋
• 時(shí)間複雜度：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. 找出最後一個(gè)()

• 演算法：反向線(xiàn)性搜尋
• 時(shí)間複雜度：O(n)
• 從末尾開(kāi)始順序掃描

// 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ù)組方法的完整實(shí)作。

？在 LinkedIn 上與我聯(lián)絡(luò)：

讓我們一起深入了解軟體工程的世界！我定期分享 JavaScript、TypeScript、Node.js、React、Next.js、資料結(jié)構(gòu)、演算法、Web 開(kāi)發(fā)等方面的見(jiàn)解。無(wú)論您是想提高自己的技能還是在令人興奮的主題上合作，我都樂(lè)意與您聯(lián)繫並與您一起成長(zhǎng)。

跟我來(lái)：Nozibul Islam

以上是JavaScript 數(shù)組方法背後的演算法的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！