将排序数组合并在一起 JavaScript

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/12/20 4:28:17

在 javascript 中，可以使用数据结构中可用的排序技术将排序数组合并在一起。在这个问题中，我们将得到两个排序数组，我们必须合并它们。合并后，返回一个也是排序形式的数组。

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

什么是排序数组?

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

// 排序前的数组
var arr = [2, 5, 1, 3, 6, 9, 7]

//排序后的数组
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:将 unmerge1 和 unmerge2 的值与索引"a"和"b"进行比较。如果 unmerge1 的值小于 unmerge2，则将 unmerge1 添加到 mergedArray[current] 中。并将"a"的计数增加 1。

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

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

步骤 10:在此步骤中返回 mergedArray 值。

步骤 11:然后调用步骤 2 中定义的函数并控制台输出以查看。

示例

// 声明两个排序数组
var array1 = [12, 16, 17, 11, 13];
var array2 = [10, 13, 15, 29, 25];

//定义函数来合并数组
function merge2Arrays(array1, array2) {
  let mergedArray = [];
  let a = 0;
  let b = 0;
  let current = 0;

//运行 while 循环，直到所有元素都排序完毕
  while (current < ( array1.length + array2.length )) {
     let unmerge1 = array1[a];
     let unmerge2 = array2[b];

     // 如果下一个元素来自 array1
     if (unmerge1 < unmerge2) {
        mergedArray[current] = unmerge1;
        a++;

     // 如果下一个元素来自 array2
     } else {
        mergedArray[current] = unmerge2;
        b++;
     }

     current++;
  }

  // 返回合并数组
  return mergedArray;
}

//调用merge2Array函数
merge2Arrays(array1, array2);

console.log("合并前:")
console.log(array1);
console.log(array2);
console.log("合并后")
console.log (merge2Arrays(array1, array2));

在上面的代码中，我们首先按排序顺序定义了两个数组，分别名为array1和array2。然后，我们定义了一个名为merge2Arrays的函数，它将两个定义的数组作为参数。之后，mergeArray被初始化为一个空数组，以存储结果排序数组。

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

输出

之前:
[ 12, 16, 17, 11, 13 ]
[ 10, 13, 15, 29, 25 ]
之后:
[ 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 的长度。