JavaScript 合并排序的数组

在JavaScript中，可以使用数据结构中提供的排序技术来将排序的数组合并在一起。在这个问题中，我们将会给出两个排序的数组，我们需要将它们合并在一起。在合并后，返回一个也是排序形式的单一数组。

为了解决这个问题，我们将使用贪心算法。

什么是排序的数组

在JavaScript中，数组是具有相似数据类型的集合，我们可以在运行时调整数组的大小。排序的数组是一个数组的项目的顺序形式。它们的顺序应该是升序的。在JavaScript中，有一个预定义的方法称为sort()，用来对数组中的元素进行排序。默认情况下，sort()方法将元素按升序排列。

// array before sorting
var arr = [2, 5, 1, 3, 6, 9, 7]

//array after sorting
var arr = [1, 2, 3, 5, 6, 7, 9]

理解问题

为了解决这个问题，我们将创建一个函数，该函数以两个数组作为参数。这些数组已经按排序形式排列。我们需要将它们合并为一个单独的数组。

在函数的第一步中，它将比较两个排序数组的元素，并将最小的元素添加到新创建的数组的第0个索引位置。完成此步骤后，它将增加指针并再次比较下一个数字，并将其添加到下个索引位置。

我们将采用贪心方法，即自上而下的方法。在数据结构中，贪心方法基本上是选择在特定时刻解决问题的最佳选择。为了更好地理解，让我们看下面的示例：

JavaScript 合并排序的数组

步骤

要将两个给定的排序数组合并为一个排序数组，可以使用此算法。具体步骤如下：

步骤1 ：在第一步中，定义两个已排序的数组。

步骤2 ：定义一个名为merge2Arrays的函数，并向其中传递两个变量。

步骤3 ：创建一个空的结果数组，以存储合并后的数组。

步骤4 ：在这一步中，我们将初始化指针a、b和current，以了解数组中每个元素的位置。这里，a是第一个数组的索引位置，b是第二个数组的索引值，current是新合并数组的索引值。

步骤5 ：在这一步中，我们将初始化一个while循环。它将运行到两个数组的长度。

步骤6 ：现在初始化两个变量，并将它们命名为unmerge1和unmerge2。这些变量将存储前面定义的每个数组的跟踪项。

步骤7 ：将unmerge1和unmerge2的值与索引a和b进行比较。如果unmerge1的值小于unmerge2，则将unmerge1添加到mergedArray[current]中，并将a的计数增加1。

步骤8 ：现在，在else部分中，如果unmerge2的值小于unmerge1，则将unmerge2添加到mergedArray[current]中，并将b的计数增加1。

步骤9 ：在if-else块之外，将current的计数增加1。

步骤10 ：在这一步中返回mergedArray的值。

步骤11 ：然后调用步骤2中定义的函数，并将输出打印到控制台以查看结果。

示例

// Declaration of two sorted arrays
var array1 = [12, 16, 17, 11, 13];
var array2 = [10, 13, 15, 29, 25];


//define function to merge arrays
function merge2Arrays(array1, array2) {
  let mergedArray = [];
  let a = 0;
  let b = 0;
  let current = 0;

//running a while loop until all elements get sorted
  while (current < ( array1.length + array2.length )) {
     let unmerge1 = array1[a];
     let unmerge2 = array2[b];

     // if next element comes from array1
     if (unmerge1 < unmerge2) {
        mergedArray[current] = unmerge1;
        a++;

     // if next element comes from array2
     } else {
        mergedArray[current] = unmerge2;
        b++;
     }

     current++;
  }

  // return merged array
  return mergedArray;
}

//calling merge2Array function
merge2Arrays(array1, array2);

console.log("Before Merging:")
console.log(array1);
console.log(array2);
console.log("After Merging")
console.log (merge2Arrays(array1, array2));

在上面的代码中，首先我们定义了两个已排序数组array1和array2。然后我们定义了一个叫做merge2Arrays的函数，它接受这两个已定义的数组作为参数。之后，我们初始化了一个空数组mergeArray来存储结果排序的数组。

然后我们初始化了三个变量a、b和current为0，它们将作为array1和array2以及mergeArray的索引值。然后我们初始化了一个while循环来检查最小的元素。循环将一直运行，直到所有元素都排序完成。最后，返回排序后的数组的值。

输出

Before:
[ 12, 16, 17, 11, 13 ]
[ 10, 13, 15, 29, 25 ]
After:
[ 10, 12, 13, 15, 16, 17, 11, 13, 29, 25]

时间复杂度

在while循环的每次迭代中，程序使用unmerge1和unmerge2来比较两个输入数组中当前元素的值，然后选择较小的值添加到mergedArray中。然后在需要时递增每个计数器值。

while循环迭代的次数为array1的长度和array2的长度之和。由于循环的每次迭代将一个元素添加到mergedArray中，并且该数组包含array1和array2元素的总数，循环中的比较和指针递增需要恒定的时间量，因此该算法的时间复杂度为O(N)，其中N是n和m的和。这里n是array1的长度，m是array2的长度。