使用归并排序递归排序 JavaScript 数组


在本问题陈述中,我们的目标是使用归并排序递归排序数组并借助 Javascript 实现代码。因此,在下面我们将讨论归并排序及其实现。

理解问题陈述

问题陈述是编写一个 Javascript 中归并排序的函数,该函数将有助于将给定的输入数组排序为升序或降序。并且我们必须创建一个将递归排序元素的函数。

什么是递归排序技术?

递归是一种函数调用自身来解决问题的方法。当一个函数调用自身时,它会在栈上创建一个新的函数实例,并且函数会继续执行,直到找到所需的结果。此结果是停止递归并允许函数给出结果的条件。

因此,递归是一种强大的技术,它可以简化复杂的问题,并使代码更简单、更简洁。因此,务必谨慎使用递归,因为如果实现不正确,它会导致堆栈溢出错误。

什么是归并排序算法?

在归并排序中,该算法通过将数组递归分解成更小的子数组来排序数组,直到每个子数组包含一个元素。然后,该算法将相邻的子数组对合并成更大且排序的子数组。此过程递归运行,直到数组的整个元素未排序。

递归步骤包括在数组的左右部分上调用归并排序函数。这些部分本身就是数组。此调用通过将其分解成更小的子数组来对数组的每一半部分进行排序。一旦它分离了所有元素,算法就开始将排序后的子数组合并回一起,以创建最终的排序数组。

给定问题的逻辑

对于代码,我们将创建一个函数来执行归并排序。并且在函数内部,我们将数组划分为更小的子数组,递归排序这些子数组,然后将它们合并回一起以生成一个完全排序的数组。该函数的关键操作是合并步骤,其中两个排序的子数组合并成一个排序的数组。

算法

步骤 1 - 声明一个名为 mergeSort 的函数,该函数使用数组参数。

步骤 2 - 在函数内部,我们将检查数组的长度是否为 1 或小于 1,它已经排序,因此只需返回数组。

步骤 3 - 否则,我们将数组划分为两个子数组 left 和 right,并使用 mergeSort 递归排序每一半部分。

步骤 4 - 并且一旦递归调用返回,我们将使用 merge 函数将排序后的 left 和 right 部分合并在一起。

步骤 5 - merge 函数将获取两个排序的数组 left 和 right,并将它们合并成一个排序的数组作为结果。

算法代码

//function to sort the given array
function mergeSort(arr) {
   if (arr.length <= 1) {
      return arr;
   }
   const mid = Math.floor(arr.length / 2);
   const left = arr.slice(0, mid);
   const right = arr.slice(mid);
   return merge(mergeSort(left), mergeSort(right));
}
 
//function to merge the left and right elements
function merge(left, right) {
   const result = [];
    
   while (left.length && right.length) {
      if (left[0] < right[0]) {
         result.push(left.shift());
      } else {
         result.push(right.shift());
      }
   }
    
   return [...result, ...left, ...right];
}
const arr = [4, 1, 5, 2, 6, 3, 7, 8];
console.log(mergeSort(arr));

复杂度

mergeSort 函数花费的时间为 O(n log n),因为我们已实现归并排序,它需要 O(n log n) 时间来对项目进行排序。而 n 是给定数组的大小。并且代码使用的空间也是 O(n),因为它将结果存储为排序数组。因此,此技术使其成为大型数据集的有效排序算法。

结论

因此,上面创建的函数可用于对大小为 n 的给定数组进行排序,时间复杂度为 O(n log n)。这是一种可靠且高效的排序算法。

更新于: 2023年5月18日

2K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告