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

目錄

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

什麼是歸併排序演算法？

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

1. 除：首先，歸併排序?qū)㈥嚵蟹殖蓛砂?/li>
2. 征服：其次，它遞歸地對(duì)每一半進(jìn)行排序
3. 合併：最後，它將排序的兩半重新合併在一起

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

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

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

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

第一步：劃分

歸併排序的第一步是將數(shù)組分成子數(shù)組，然後將每個(gè)子數(shù)組劃分為子數(shù)組，然後將子數(shù)組劃分為子數(shù)組，直到所有子數(shù)組中只剩下一項(xiàng)。

第二步：合併（征服）

第二步是開始從頭開始對(duì)這些子陣列進(jìn)行排序。

時(shí)間複雜度

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

原因如下：

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

將此與：

進(jìn)行比較

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

對(duì)於 1,000 個(gè)元素的陣列：

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

空間複雜度

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

JavaScript 中的實(shí)作

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

• 建立一個(gè)空數(shù)組來儲(chǔ)存合併結(jié)果
• 初始化兩個(gè)輸入陣列的指標(biāo)
• 將這些指標(biāo)想像成手指，追蹤我們在每個(gè)陣列中的位置

1. 主要合併邏輯：

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

• 比較兩個(gè)陣列中的元素
• 取得較小的元素並將其加到結(jié)果
• 在我們?nèi)〉玫年嚵兄邢蚯耙苿?dòng)指標(biāo)
• 就像排序一副牌時(shí)選擇兩張牌中較小的一張

1. 清理階段：

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

• 加入任何剩餘元素
• 這是必要的，因?yàn)橐粋€(gè)陣列可能比另一個(gè)陣列長
• 就像比較後收集剩餘的卡片

主歸併排序函數(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 的陣列
• 這些已按定義排序
• 充當(dāng)我們的遞歸停止點(diǎn)

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));

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

範(fàn)例演練

讓我們看看它是如何排序的 [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é)論

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

重點(diǎn)：

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

---

---

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

確保您不會(huì)錯(cuò)過本系列的任何部分，並與我聯(lián)繫以進(jìn)行更深入的了解
關(guān)於軟體開發(fā)（Web、伺服器、行動(dòng)或抓取/自動(dòng)化）、資料的討論
結(jié)構(gòu)和演算法，以及其他令人興奮的技術(shù)主題，請(qǐng)關(guān)注我：

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

敬請(qǐng)期待並祝您編碼愉快?????

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