如何在JavaScript中实现归并排序？

归并排序

归并排序算法，我们可以按特定顺序对元素进行排序。该算法也被认为是分治策略的一个例子。在归并排序算法中，首先将数组分成两部分，然后以特定排序的方式组合。

数组将被分成两半，直到无法再分割。这意味着如果数组完全分割并且无法进一步分割，则停止分割。我们将数组分成两半，并在每一半上实现归并排序。该算法是一个将两个较小的分割数组组合成较大的数组的过程。

输入输出场景

考虑一个数组，其中包含一些未排序的随机顺序的元素，我们可以通过执行归并排序来对这些元素进行排序。让我们检查下面的场景。

Input = [12, 34, 11, 1, 54, 25, 67, 45]; 
Output = 1, 11, 12, 25, 34, 45, 54, 67

正如我们在输出中看到的，元素已经按升序排序。

归并排序是如何工作的？

要了解归并排序的工作方式，让我们假设一个数组arr= [30, 20, 40, 0, 10, 80, 11]。

  • 首先，我们需要检查数组的左索引是否小于数组的右索引，如果数组满足条件，则计算数组的中点。


  • 现在我们需要将包含 7 个元素的数组分成两个大小分别为 4 和 3 的数组。

  • 将数组分成两半后，它将如下所示。


  • 将数组继续分成两半，直到数组不能再分割。


  • 将所有元素分成最小单元后，现在根据元素的大小比较元素。

  • 首先比较每个列表中数组的元素，然后对其进行排序并将其合并到另一个列表中。


  • 执行所有合并后，将得到以下列表。


算法

让我们看看算法：

  • 声明一个数组、左索引、右索引和中间变量。

  • 执行归并排序。

    mergesort(array, left index, right index)

    如果左索引 > 右索引

    返回

    mid= (左索引 + 右索引) / 2

    mergesort(array, 左索引, mid) // 上半部分

    mergesort(array, mid+1, 右索引) // 下半部分

    merge(array, 左索引, mid, 右索引) // 合并上述步骤中排序的两半

示例

在下面的示例中，为了执行归并排序，我们创建了一个包含随机顺序元素的数组。并使用归并排序算法将数组元素按升序排序。

<!DOCTYPE html> 
<html> 
   <title>Merge Sort</title> 
<head> 
   <script> 
      function merge_Arrays(left_sub_array, right_sub_array) {
         let array = []
         while (left_sub_array.length && right_sub_array.length) {
            if (left_sub_array[0] < right_sub_array[0]) {
               array.push(left_sub_array.shift())
            } else {
               array.push(right_sub_array.shift())
            }
         }
         return [ ...array, ...left_sub_array, ...right_sub_array ]
      }
      function merge_sort(unsorted_Array) {
         const middle_index = unsorted_Array.length / 2
         if(unsorted_Array.length < 2) {
            return unsorted_Array
         }
         const left_sub_array = unsorted_Array.splice(0, middle_index)
         return merge_Arrays(merge_sort(left_sub_array),merge_sort(unsorted_Array))
      }
      unsorted_Array = [39, 28, 44, 4, 10, 83, 11];
      document.write("The sorted array will be: ",merge_sort(unsorted_Array));
   </script> 
</head>  
<body> 
</body> 
</html>

注意

  • 与其他排序算法相比，归并排序算法的执行速度较慢。

  • 即使数组已排序，它也会遍历整个排序过程。

  • 此算法还需要 0(n) 的额外内存空间用于临时数组。

更新于： 2022年9月23日

9K+ 浏览量

启动您的职业生涯

完成课程获得认证

开始学习
广告