了解合併排序演算法：掌握排序演算法的初學者指南

在先前的文章中，我們學習了相當多的排序演算法，例如冒泡排序、選擇排序以及插入排序。我們了解到，雖然這些排序演算法非常容易實現，但它們對於大型資料集來說效率不高，這意味著我們需要一種更有效的演算法來處理大型資料集的排序，因此需要合併排序。在本系列中，我們將介紹合併排序的工作原理以及如何在 JavaScript 中實現它。你準備好了嗎？

目錄

1. 什麼是歸併排序演算法？
2. 合併排序演算法的工作原理
   • 時間複雜度
   • 空間複雜度
3. JavaScript 實作
4. 結論

什麼是歸併排序演算法？

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

1. 除：首先，歸併排序將陣列分成兩半
2. 征服：其次，它遞歸地對每一半進行排序
3. 合併：最後，它將排序的兩半重新合併在一起

在處理較大的資料集時，這種方法始終優於更簡單的 O(n²) 演算法，例如選擇排序和冒泡排序。

合併排序演算法的工作原理

我們已經看到合併排序是透過使用流行的分而治之方法來工作的。下面是其工作原理的直觀表示。

現在我們已經看到了它的魔力，讓我們透過使用上述方法手動排序這個陣列：[38, 27, 43, 3, 9, 82, 10]來了解合併排序演算法的工作原理。

第一步：劃分

歸併排序的第一步是將數組分成子數組，然後將每個子數組劃分為子數組，然後將子數組劃分為子數組，直到所有子數組中只剩下一項。

第二步：合併（征服）

第二步是開始從頭開始對這些子陣列進行排序。

時間複雜度

歸併排序在所有情況下（最佳、平均和最差）都實現了 O(n log n) 時間複雜度，使其比處理較大資料集的 O(n²) 演算法更有效率。

原因如下：

• 除法：陣列被除log n 次（每次除法將大小減半）
• 合併：每一級合併需要n次操作
• 總計：n 次運算 × log n 等級 = O(n log n)

將此與：

• 冒泡排序：O(n²)
• 選擇排序：O(n²)
• 歸併排序：O(n log n)

對於 1,000 個元素的陣列：

• O(n²) ≈ 1,000,000 次操作
• O(n log n) ≈ 10,000 次運算

空間複雜度

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

JavaScript 中的實作

// 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++;
     }
   }

• 比較兩個陣列中的元素
• 取得較小的元素並將其加到結果
• 在我們取得的陣列中向前移動指標
• 就像排序一副牌時選擇兩張牌中較小的一張

1. 清理階段：

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

• 加入任何剩餘元素
• 這是必要的，因為一個陣列可能比另一個陣列長
• 就像比較後收集剩餘的卡片

主歸併排序函數

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 的陣列
• 這些已按定義排序
• 充當我們的遞歸停止點

1. 劃分階段：

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

• 將陣列分成兩半
• slice() 建立新陣列而不修改原始陣列
• 就像將一副紙牌切成兩半

1. 遞歸排序與合併：

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

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

範例演練

讓我們看看它是如何排序的 [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++;
     }
   }

結論

合併排序作為一種高效的排序演算法脫穎而出，在大型資料集上始終表現良好。雖然與更簡單的排序演算法相比，它需要額外的空間，但其 O(n log n) 時間複雜度使其成為許多效能至關重要的實際應用程式的首選。

重點：

• 使用分而治之的策略
• 所有情況下的時間複雜度均為 O(n log n)
• 需要 O(n) 額外空間
• 穩定的排序演算法
• 非常適合大型資料集

保持更新和聯繫

確保您不會錯過本系列的任何部分，並與我聯繫以進行更深入的了解
關於軟體開發（Web、伺服器、行動或抓取/自動化）、資料的討論
結構和演算法，以及其他令人興奮的技術主題，請關注我：

伊曼紐爾·艾因德關注

軟體工程師|技術撰稿人 |後端、網路和行動開發人員？ |熱衷於打造高效且可擴充的軟體解決方案。 #讓連線？

• GitHub
• 領英
• X（推特）

敬請期待並祝您編碼愉快??‍??

以上是了解合併排序演算法：掌握排序演算法的初學者指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！