了解合并排序算法：掌握排序算法的初学者指南-js教程-PHP中文网

在之前的文章中，我们学习了相当多的排序算法，例如冒泡排序、选择排序以及插入排序。我们了解到，虽然这些排序算法非常容易实现，但它们对于大型数据集来说效率不高，这意味着我们需要一种更有效的算法来处理大型数据集的排序，因此需要合并排序。在本系列中，我们将介绍合并排序的工作原理以及如何在 JavaScript 中实现它。你准备好了吗？

Understanding merge sort algorithm: Beginner

什么是归并排序算法？

合并排序算法是一种遵循分治原则的优秀排序算法。与选择排序和冒泡排序等更简单的算法不同，这些算法多次遍历数组来比较相邻元素，合并排序采用了更具策略性的方法：

除：首先，归并排序将数组分成两半
征服：其次，它递归地对每一半进行排序
合并：最后，它将排序的两半重新合并在一起

在处理较大的数据集时，这种方法始终优于更简单的 O(n²) 算法，例如选择排序和冒泡排序。

合并排序算法的工作原理

我们已经看到合并排序是通过使用流行的分而治之方法来工作的。下面是其工作原理的直观表示。

Understanding merge sort algorithm: Beginner

现在我们已经看到了它的魔力，让我们通过使用上述方法手动排序这个数组：[38, 27, 43, 3, 9, 82, 10]来了解合并排序算法的工作原理。

第一步：划分

归并排序的第一步是将数组划分为子数组，然后将每个子数组划分为子数组，再将子数组划分为子数组，直到所有子数组中只剩下一项。

Understanding merge sort algorithm: Beginner

第二步：合并（征服）

第二步是开始从头开始对这些子数组进行排序。

Understanding merge sort algorithm: Beginner

时间复杂度

归并排序在所有情况下（最佳、平均和最差）都实现了 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;
}

登录后复制

分解合并功能：

功能设置：

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

登录后复制

比较两个数组中的元素
获取较小的元素并将其添加到结果
在我们获取的数组中向前移动指针
就像排序一副牌时选择两张牌中较小的一张

清理阶段：

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

登录后复制

分解归并排序：

基本案例：

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

登录后复制

处理长度为 0 或 1 的数组
这些已按定义排序
充当我们的递归停止点

划分阶段：

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

登录后复制

将数组分成两半
slice() 创建新数组而不修改原始数组
就像将一副纸牌切成两半

递归排序和合并：

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

登录后复制

对每一半进行递归排序
使用合并函数合并排序的两半
就像在组合之前对较小的一堆卡片进行排序

示例演练

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

第一次分裂：

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

登录后复制

第二次分裂：

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

登录后复制