JavaScript 使用归并排序递归地对数组进行排序

在这个问题陈述中，我们的目标是使用归并排序递归地对数组进行排序，并借助JavaScript实现代码。因此，下面我们将讨论归并排序及其实现。

理解问题陈述

问题陈述是在Javascript中编写一个归并排序函数，用于将给定的输入数组按升序或降序排序。我们需要创建一个函数来递归地对元素进行排序。

什么是递归排序技术

递归是一种技术，其中一个函数调用自身以解决一个问题。当一个函数调用自己时，它在堆栈上创建自身的新实例，并且该函数继续执行，直到找到所需的结果。这个结果是停止递归的条件，并允许函数给出结果。

因此，递归是一种强大的技术，可以简化复杂的问题，并且使代码更简单和简洁。因此，需要谨慎使用递归，因为如果没有正确实现递归，会导致堆栈溢出错误。

什么是归并排序算法

在归并排序中，算法通过将数组递归地分解为更小的子数组来对其进行排序，直到每个子数组只包含一个元素为止。然后，算法将相邻的子数组组合成更大且排序的子数组。此过程递归地运行，直到整个数组的所有元素都被排序。

递归步骤涉及对左侧和右侧部分的数组调用归并排序函数。这些部分本身就是数组。此调用通过将其分解为更小的子数组来对数组的每一半部分进行排序。一旦分隔了所有元素，算法开始合并排序后的子数组，以创建结果排序后的数组。

JavaScript 使用归并排序递归地对数组进行排序

给定问题的逻辑

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

步骤

步骤1 - 声明一个名为mergeSort的函数，它使用一个数组作为参数。

步骤2 - 在函数内部，我们将检查数组的长度是否为1或小于1，如果是，则已经排序好，只需返回数组。

步骤3 - 否则，我们将把数组分成左侧和右侧两个半数组，并使用mergeSort递归地对每个半部分进行排序。

步骤4 - 一旦递归调用返回，我们将使用merge函数将排序好的左侧和右侧部分合并在一起。

步骤5 - merge函数将取两个已排序的数组左侧和右侧，并将它们合并成一个排序好的数组作为结果。

算法的代码

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