在之前的文章中，我們學(xué)習(xí)了相當多的排序算法，例如冒泡排序、選擇排序以及插入排序。我們了解到，雖然這些排序算法非常容易實現(xiàn)，但它們對于大型數(shù)據(jù)集來說效率不高，這意味著我們需要一種更有效的算法來處理大型數(shù)據(jù)集的排序，因此需要合并排序。在本系列中，我們將介紹合并排序的工作原理以及如何在 JavaScript 中實現(xiàn)它。你準備好了嗎？

目錄

1. 什么是歸并排序算法？
2. 合并排序算法的工作原理
   • 時間復(fù)雜度
   • 空間復(fù)雜度
3. JavaScript 實現(xiàn)
4. 結(jié)論

什么是歸并排序算法？

合并排序算法是一種遵循分治原則的優(yōu)秀排序算法。與選擇排序和冒泡排序等更簡單的算法不同，這些算法多次遍歷數(shù)組來比較相鄰元素，合并排序采用了更具策略性的方法：

1. 除：首先，歸并排序?qū)?shù)組分成兩半
2. 征服：其次，它遞歸地對每一半進行排序
3. 合并：最后，它將排序的兩半重新合并在一起

在處理較大的數(shù)據(jù)集時，這種方法始終優(yōu)于更簡單的 O(n2) 算法，例如選擇排序和冒泡排序。

合并排序算法的工作原理

我們已經(jīng)看到合并排序是通過使用流行的分而治之方法來工作的。下面是其工作原理的直觀表示。

現(xiàn)在我們已經(jīng)看到了它的魔力，讓我們通過使用上述方法手動排序這個數(shù)組：[38, 27, 43, 3, 9, 82, 10]來了解合并排序算法的工作原理。

第一步：劃分

歸并排序的第一步是將數(shù)組劃分為子數(shù)組，然后將每個子數(shù)組劃分為子數(shù)組，再將子數(shù)組劃分為子數(shù)組，直到所有子數(shù)組中只剩下一項。

第二步：合并（征服）

第二步是開始從頭開始對這些子數(shù)組進行排序。

時間復(fù)雜度

歸并排序在所有情況下（最佳、平均和最差）都實現(xiàn)了 O(n log n) 時間復(fù)雜度，使其比處理較大數(shù)據(jù)集的 O(n2) 算法更高效。

原因如下：

• 除法：數(shù)組被除log n 次（每次除法將大小減半）
• 合并：每一級合并需要n次操作
• 總計：n 次操作 × log n 級別 = O(n log n)

將此與：

進行比較

• 冒泡排序：O(n2)
• 選擇排序：O(n2)
• 歸并排序：O(n log n)

對于 1,000 個元素的數(shù)組：

• O(n2) ≈ 1,000,000 次操作
• O(n log n) ≈ 10,000 次操作

空間復(fù)雜度

歸并排序需要 O(n) 的額外空間來存儲合并期間的臨時數(shù)組。雖然這超過了冒泡排序或選擇排序所需的 O(1) 空間，但時間效率通常使得這種權(quán)衡在實踐中是值得的。

JavaScript 中的實現(xiàn)

// The Merge Helper Function
function merge(left, right) {
  const 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++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

分解合并功能：

1. 功能設(shè)置：

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

• 創(chuàng)建一個空數(shù)組來存儲合并結(jié)果
• 初始化兩個輸入數(shù)組的指針
• 將這些指針想象成手指，跟蹤我們在每個數(shù)組中的位置

1. 主要合并邏輯：

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

• 比較兩個數(shù)組中的元素
• 獲取較小的元素并將其添加到結(jié)果
• 在我們獲取的數(shù)組中向前移動指針
• 就像排序一副牌時選擇兩張牌中較小的一張

1. 清理階段：

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

• 添加任何剩余元素
• 這是必要的，因為一個數(shù)組可能比另一個數(shù)組長
• 就像比較后收集剩余的卡片

主歸并排序函數(shù)

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

分解歸并排序：

1. 基本案例：

   if (arr.length <= 1) {
     return arr;
   }

• 處理長度為 0 或 1 的數(shù)組
• 這些已按定義排序
• 充當我們的遞歸停止點

1. 劃分階段：

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

• 將數(shù)組分成兩半
• slice() 創(chuàng)建新數(shù)組而不修改原始數(shù)組
• 就像將一副紙牌切成兩半

1. 遞歸排序和合并：

   return merge(mergeSort(left), mergeSort(right));

• 對每一半進行遞歸排序
• 使用合并函數(shù)合并排序的兩半
• 就像在組合之前對較小的一堆卡片進行排序

示例演練

讓我們看看它是如何排序的 [38, 27, 43, 3]：

1. 第一次分裂：

// The Merge Helper Function
function merge(left, right) {
  const 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++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

1. 第二次分裂：

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

1. 合并回來：

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

結(jié)論

合并排序作為一種高效的排序算法脫穎而出，在大型數(shù)據(jù)集上始終表現(xiàn)良好。雖然與更簡單的排序算法相比，它需要額外的空間，但其 O(n log n) 時間復(fù)雜度使其成為許多性能至關(guān)重要的實際應(yīng)用程序的首選。

要點：

• 使用分而治之的策略
• 所有情況下的時間復(fù)雜度均為 O(n log n)
• 需要 O(n) 額外空間
• 穩(wěn)定的排序算法
• 非常適合大型數(shù)據(jù)集

---

---

保持更新和聯(lián)系

確保您不會錯過本系列的任何部分，并與我聯(lián)系以進行更深入的了解
關(guān)于軟件開發(fā)（Web、服務(wù)器、移動或抓取/自動化）、數(shù)據(jù)的討論
結(jié)構(gòu)和算法，以及其他令人興奮的技術(shù)主題，請關(guān)注我：

• GitHub
• 領(lǐng)英
• X（推特）

敬請期待并祝您編碼愉快?????

以上是了解合并排序算法：掌握排序算法的初學(xué)者指南的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！