合并已排序数组的 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 个索引处。在此步骤之后，它将增加指针并再次比较下一个数字，并将其添加到下一个索引处。

我们将在其中遵循自上而下方法的贪婪方法中使用贪婪算法。数据结构中的贪婪方法基本上是通过选择在特定时刻可用的最佳选项来解决问题的。为了更好地理解，让我们看下面的例子

算法

要将两个给定的已排序数组合并到一个已排序数组中，我们可以使用此算法。因此，分步过程如下

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

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

步骤 3：使用给定的 mergedArray 创建一个空结果数组，以将合并的数组存储在其中。

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

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

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

步骤 7：使用索引“a”和“b”比较 unmerge1 和 unmerge2 的值。如果 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 初始化为空数组以存储结果排序数组。

然后将 3 个变量 a、b 和 current 初始化为 0，它们将作为 array1 和 array2 以及 mergedArray 的索引值。然后我们初始化了一个 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 的长度。

结论

通过此实现，我们学习了如何使用贪心算法对两个已排序数组进行排序。贪心算法基本上遵循自上而下的方法。此技术称为合并排序，因为它将两个数组合并到一个已排序数组中。并且我们学习了如何计算该算法的时间复杂度，即 O(n+k) 或 O(N)。