如何在JavaScript中不使用sort()将两个排序数组合并为一个排序数组

how to merge two sorted array in one sorted array in JavaScript without using sort()

本文关键字:排序 数组 两个 合并 一个 JavaScript sort      更新时间:2023-09-26

在这个程序中合并了两个数组,然后使用temp进行排序,但这不是正确的方法。因为两个数组都是排序的,所以method应该是唯一的,也就是说,两个以排序形式排序的数组的合并应该是唯一的。

的例子:

  • a=[1,2,3,5,9]
  • b=[4,6,7,8]

function mergeSortdArray(a,b){
	for(var i=0;i<b.length;i++){
		a.push(b[i]);
	}
	//console.log(a);
for(i=0;i<a.length;i++)
    {
        for(j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));

基于上面Eric Lundgren的回答,但这修复了几个主要的错误,并且更有效。在生产部门为我工作。我包括使用排序函数更复杂的解决方案-对于这个简单的情况,你可以只是测试a> b在埃里克的回答,如果你想。

function mergeSortedArray(a, b) {
    var sorted = [], indexA = 0, indexB = 0;
    while (indexA < a.length && indexB < b.length) {
        if (sortFn(a[indexA], b[indexB]) > 0) {
            sorted.push(b[indexB++]);
        } else {
            sorted.push(a[indexA++]);
        }
    }
    if (indexB < b.length) {
        sorted = sorted.concat(b.slice(indexB));
    } else {
        sorted = sorted.concat(a.slice(indexA));
    }
    return sorted;
}
function sortFn(a, b) {
    return a - b;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));

这样怎么样?

由于a和b都是排序的,所以在添加时只需要考虑每个数组的顶部或第一项。注意,这个方法将在执行过程中同时修改a和b,这可能不是您想要的,在这种情况下,您可以在开始处添加以下代码:

var tempA = a.slice();
var tembB = b.slice();

这将复制数组,然后您可以在下面的函数中使用它们来代替ab:

function mergeSortedArray(a,b){
    var tempArray = [];
    while(a.length || b.length) {
        if(typeof a[0] === 'undefined') {
            tempArray.push(b[0]);
            b.splice(0,1);
        } else if(a[0] > b[0]){
            tempArray.push(b[0]);
            b.splice(0,1);
        } else {
            tempArray.push(a[0]);
            a.splice(0,1);
        }
    }
    return tempArray;
}
console.log(mergeSortedArray([4,6,7,8], [1,2,3,5,9]));

在不使用splice的情况下,尝试这样做:

function mergeSortedArray(a,b){
    var tempArray = [];
    var currentPos = {
        a: 0,
        b: 0
    }
    while(currentPos.a < a.length || currentPos.b < b.length) {
        if(typeof a[currentPos.a] === 'undefined') {
            tempArray.push(b[currentPos.b++]);
        } else if(a[currentPos.a] > b[currentPos.b]){
            tempArray.push(b[currentPos.b++]);
        } else {
            tempArray.push(a[currentPos.a++]);
        }
    }
    return tempArray;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));

嘿,我用一个简单的。concat()和。sort()方法运行了上面每个人的代码。对于大数组和小数组,.concat()和.sort()在更短的时间内完成,这一点很明显。

console.time("mergeArrays");
mergeArrays([1,2,3,5,9],[4,6,7,8])
console.timeEnd("mergeArrays");
//mergeArrays: 0.299ms
console.time("concat sort");
[1,2,3,5,9].concat([4,6,7,8]).sort();
console.timeEnd("concat sort");
//concat sort:0.018ms

对于10,000大小的数组,差异甚至更大,concat和sort的运行速度甚至比以前更快(4.831 ms vs .008 ms)。

发生了什么在javascript的排序,使它更快?

可以使用es6展开运算符

let a=[1,2,3,5,9]
let b=[4,6,7,8]
let newArray=[...a,...b].sort()
console.log(newArray)

我需要它来实现我自己的

mergesortedarray(a, b) {
  let c = new Array(a.length+b.length);
  for(let i=0, j=0, k=0; i<c.length; i++)
    c[i] = j < a.length && (k == b.length || a[j] < b[k]) ? a[j++] : b[k++];
}

最短合并排序数组,不使用sort() plus,不使用第三个临时数组。

function mergeSortedArray (a, b){
  let index = 0;
  while(b.length > 0 && a[index]) {
    if(a[index] > b[0]) {
      a.splice(index, 0, b.shift());
    }
    index++;
  }
  return [...a, ...b];
}
mergeSortedArray([1,2,3,5,9],[4,6,7,8])

现在您可以使用es6(…)扩展操作符

========================================
   using es6 (...)spread operator
========================================
let a=[1,2,3,5,9]
let b=[4,6,7,8]
let sortedArray=[...a,...b].sort()
console.log(sortedArray) 
outputy :- [1, 2, 3, 4, 5, 6, 7, 8, 9]
========================================
       2nd way 
========================================

function mergeSortedArray(a, b) {
    var sortedArray = [], indexA = 0, indexB = 0;
    while (indexA < a.length && indexB < b.length) {
        if (sortFuntion(a[indexA], b[indexB]) > 0) {
            sortedArray.push(b[indexB++]);
        } else {
            sortedArray.push(a[indexA++]);
        }
    }
    if (indexB < b.length) {
        sortedArray = sortedArray.concat(b.slice(indexB));
    } else {
        sortedArray = sortedArray.concat(a.slice(indexA));
    }
    return sortedArray;
}
function sortFuntion(a, b) {
    return a - b;
}
console.log(mergeSortedArray([1,2,3,5,9],[4,6,7,8]));
output :- 1,2,3,4,5,6,7,8,9

在JavaScript中合并两个排序数组

var SortedArrays = function(nums1, nums2) {
    let array = [];
    let leftIndex = 0, rightIndex = 0;
    while(leftIndex < nums1.length && rightIndex < nums2.length) {
        if(nums1[leftIndex] < nums2[rightIndex]) {
            array.push(nums1[leftIndex]);
            leftIndex++;
        } else {
            array.push(nums2[rightIndex]);
            rightIndex++;
        }
    }
    array = array.concat(nums1.slice(leftIndex)).concat(nums2.slice(rightIndex));
    return array;
}

我想添加一个包含初始化大小的数组的解决方案,以便在新排序的数组之外没有数组的副本。这意味着不调用slice或额外的concat:

function defaultComparator(a, b) {
    return a - b;
}
function mergeSortedArray(arrA, arrB, comparator) {
    var _comparator = (typeof comparator === 'undefined')
        ? defaultComparator
        : comparator;
    var idxA = 0, idxB = 0, idxS = 0;
    var arrSorted = new Array(arrA.length + arrB.length);
    while (idxA < arrA.length || idxB < arrB.length) {
        if (idxA >= arrA.length)
            arrSorted[idxS++] = arrB[idxB++];
        else if (idxB >= arrB.length)
            arrSorted[idxS++] = arrA[idxA++];
        else if (_comparator(arrA[idxA], arrB[idxB]) <= 0)
            arrSorted[idxS++] = arrA[idxA++];
        else
            arrSorted[idxS++] = arrB[idxB++];
    }
    return arrSorted;
}
console.log(mergeSortedArray([0,2,3,5,9],[-3,1,5,6,9.5]));
console.log(mergeSortedArray(
    [{ n: 0 }, { n: 2 }, { n: 3 }, { n: 5 }, { n: 9 }],
    [{ n: -2 }, { n: 0 }, { n: 4 }],
    function(a, b) { return a.n - b.n; }
))

让我们实现一个通用合并。假设我们不知道它们是升序还是降序排序,我们首先需要应用一个测试来派生比较函数cf。然后是一个简单的递归遍历,如下所示;

function merger(a, b){
  var cf = a[0] < a[1] || b[0] < b[1] ? (x,y) => x < y
                                      : a[0] > a[1] || b[0] > b[1] ? (x,y) => x > y
                                                                   : (x,y) => false,
      mg = ([a,...as],[b,...bs]) => a !== void 0 &&
                                    b !== void 0  ? cf(a,b) ? [a].concat(mg(as,[b,...bs]))
                                                            : [b].concat(mg([a,...as],bs))
                                                  : a === void 0 ? [b,...bs]
                                                                 : [a,...as];
  return mg(a,b);
}
var a = [1,2,3,5,9,10,11,12],
    b = [4,6,7,8,17],
    c = [9,8,7],
    d = [23,11,10,4,3,2,1];
console.log(merger(a,b));
console.log(merger(c,d));

注意:测试者决定是上升还是下降是草率的。它甚至不检查前两家的所有者权益。这只是给大家一个概念。正确实施它超出了这个问题的范围。

合并两个已排序数组

function merge(arr1, arr2) {
    const arr = [];
    while (arr1.length && arr2.length) {
        if (arr1[0] < arr2[0]) {
            arr.push(arr1.shift());
        } else {
            arr.push(arr2.shift());
        }
    }
    return [...arr, ...arr1, ...arr2];
}

*如果你想就地合并数组,克隆每个数组并在while循环中使用。

示例: clonedArr1 = [...arr1];

function mergeArrays(arr1, arr2) {
    if (!arePopulatedArrays(arr1, arr2))
        return getInvalidArraysResult(arr1, arr2);
    let arr1Index = 0;
    let arr2Index = 0;
    const totalItems = arr1.length + arr2.length;
    const mergedArray = new Array(totalItems);
    for (let i = 0; i < totalItems; i++) {
        if (hasItems(arr1, arr1Index)) {
            if (hasItems(arr2, arr2Index)) {
                if (HasSmallestItem(arr1, arr2, arr1Index, arr2Index)) {
                    mergedArray[i] = arr1[arr1Index++];
                } else {
                    mergedArray[i] = arr2[arr2Index++];
                }
            } else {
                mergedArray[i] = arr1[arr1Index++];
            }
        } else {
            mergedArray[i] = arr2[arr2Index++];
        }
    }
    return mergedArray;
}
function arePopulatedArrays(arr1, arr2) {
    if (!arr1 || arr1.length === 0)
        return false;
    if (!arr2 || arr2.length === 0)
        return false;
    return true;
}
function getInvalidArraysResult(arr1, arr2) {
    if (!arr1 && !arr2)
        return [];
    if ((!arr2 || arr2.length === 0) && (arr1 && arr1.length !== 0))
        return arr1;
    if ((!arr1 || arr1.length === 0) && (arr2 && arr2.length !== 0))
        return arr2;
    return [];
}
function hasItems(arr, index) {
    return index < arr.length;
}
function HasSmallestItem(arr1, arr2, arr1Index, arr2Index) {
    return arr1[arr1Index] <= arr2[arr2Index];
}

如果您不关心排序操作的性能,您可以使用Array.sort:

var a=[1,2,3,5,9];
var b=[4,6,7,8];
var c = a.concat(b).sort((a,b)=>a > b);
console.log(c)

当然,使用两个数组已经排序的知识可以减少运行时间。

合并两个数组并创建新数组

function merge_two_sorted_arrays(arr1, arr2) {
        let i = 0;
        let j = 0;
        let result = [];
        while(i < arr1.length && j < arr2.length) {
            if(arr1[i] <= arr2[j]) {
                result.push(arr1[i]);
                i++;
            } else {
                result.push(arr2[j]);
                j++;
            }
        }
        while(i < arr1.length ) {
            result.push(arr1[i]);
            i++;
        }
        while(j < arr2.length ) {
            result.push(arr2[j]);
            j++;
        }
        console.log(result);
    }
merge_two_sorted_arrays([15, 24, 36, 37, 88], [3, 4, 10, 11, 13, 20]);

合并两个已排序的数组-答案与注释

const mergeArrays = (arr1, arr2) => { // function to merge two sorted arrays
  if (!arr1 || !arr2) { // if only one array is passed
    return "Invalid Array" // message is returned
  }
  if (arr1.length < 1) { // if first array is empty
    if (arr2.length < 1) { // if second array is empty
      return "Both arrays are empty" // returns message
    }
    return arr2; // else returns second array
  }
  if (arr2.length < 1) { // if second array is empty
    if (arr1.length < 1) { // if both arrays are empty
      return "Both arrays are empty" // returns message
    }
    return arr1; // else returns first array
  }
  let small = []; // initializes empty array to store the smaller array
  let large = []; // initializes empty array to store the larger array
  arr1.length < arr2.length ? [small, large] = [arr1, arr2] : [small, large] = [arr2, arr1]; // stores smaller array in small and larger array in large
  const len1 = small.length; // stores length of small in len1
  const len2 = large.length; // stores length of large in len2
  let ansArr = []; // initializes an empty array to create the merged array
  let i = 0; // initializes i to 0 to iterate through small
  let j = 0; // initializes j to 0 to iterate through large
  while (small[i]!==undefined && large[j]!==undefined) { //while element in arrays at i and j position respectively exists
    if(small[i] < large[j]) { // if element from small is smaller than element in large
      ansArr.push(small[i]); // add that element to answer
      i++; // move to the next element
    } else { // if element from large is smaller than element in small
      ansArr.push(large[j]); // add that element to answer
      j++; // move to the next element
    }
  }
  if (i < len1) { // if i has not reached the end of array
    ansArr = [...ansArr, ...small.splice(i)]; // add the rest of the elements at the end of the answer
  } else { // if j has not reached the end of array
    ansArr = [...ansArr, ...large.splice(j)]; // add the rest of the elements at the end of the answer
  }
  return ansArr; // return answer
}
console.log(mergeArrays([0,1,5], [2,3,4,6,7,8,9])); // example

合并两个已排序的数组

function merge(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let k = i + j + 1; //(a.length + b.length - 1) == (i + j + 2 - 1) == (i + j + 1)
  while (k >= 0) {
    if (a[i] > b[j] || j < 0) {
      a[k] = a[i];
      i--;
    } else {
      a[k] = b[j];
      j--;
    }
    k--;
  }
  return a;
}
console.log(merge([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21], [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]));

更紧凑的代码:

function merge(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let k = i + j + 1; //(a.length + b.length - 1) == (i + j + 2 - 1) == (i + j + 1)
  while (k >= 0) {
    a[k--] = (a[i] > b[j] || j < 0) ? a[i--] : b[j--];
  }
  return a;
}
console.log(merge([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21], [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]));

我看到的大多数解决方案的问题是,他们没有预先创建数组,只是推入一个数组,当你知道最终游戏的大小有点浪费。

这是我的建议,我们可以使它更有效率,但它会使它不太好读:

function mergeSortedArrays(arr1, arr2) {
		let i1 = 0, i2 = 0;
		return [...arr1, ...arr2].map(
			() =>
				i1 === arr1.length ? arr2[i2++] :
				i2 === arr2.length ? arr1[i1++] :
				arr1[i1] < arr2[i2]? arr1[i1++] :
				arr2[i2++]
		);
}
console.log(mergeSortedArrays([1,2,3,5,9],[4,6,7,8]))

请在这里找到合并两个排序数组的实现。实际上,我们可以逐个比较数组项,将它们压入一个新的数组,当我们完全解析一个数组时,我们只连接第二个已经排序的数组的切片部分。

const merge = (arr1, arr2) => {
    let arr = [];
    let i = 0;
    let j = 0;
    while (i < arr1.length || j < arr2.length) {
        if (i === arr1.length) {
            return arr.concat(arr2.slice(j));
        }
        if (j === arr2.length) {
            return arr.concat(arr1.slice(i));
        }
        if (arr1[i] < arr2[j]) {
            arr.push(arr1[i]);
            i++
        } else {
            arr.push(arr2[j]);
            j++
        }
    }
    return arr;
}

最快的2个排序数组归并

function merge(a, b) {
  let i = 0,
    j = 0;
  let array = [];
  let counter = 0;
  while (i < a.length && j < b.length) {
    if (a[i] > b[j]) array[counter++] = b[j++];
    else if (a[i] < b[j]) array[counter++] = a[i++];
    else (array[counter++] = a[i++]), j++;
  }
  while (j < b.length) {
    array[counter++] = b[j++];
  }
  while (i < a.length) {
    array[counter++] = a[i++];
  }
  return array;
}
console.log(merge([1, 3], [2, 4, 5]));
console.log(merge([1, 3, 123, 125, 127], [2, 41, 50]));

let Array1 = [10,20,30,40];
let Array2 = [15,25,35];
let mergeArray=(arr1, arr2)=>{
    for(var i = arr2.length-1; i>= 0; i--){
        let curr1 = arr2[i]
        for(var j = arr1.length-1; j>= 0; j--){
            let curr2 = arr1[j]
            if(curr1<curr2){
                arr1[j+1]  = curr2
            }else{
                arr1[j+1]  = curr1
                break;
            }
        }
    }
    return arr1
}
mergeArray(Array1, Array2)
function mergeSortedArray(a, b){
var merged = [], 
aElm = a[0],
  bElm = b[0],
  i = 1,
  j = 1;
 if(a.length ==0)
   return b;
     if(b.length ==0)
       return a;
      while(aElm || bElm){
        if((aElm && !bElm) || aElm < bElm){
           merged.push(aElm);
              aElm = a[i++];
         }   
         else {
                merged.push(bElm);
                bElm = b[j++];
              }
      }
      return merged;
    }
    
   //check
 > mergeSortedArray([2,5,6,9], [1,2,3,29]);
 = [1, 2, 2, 3, 5, 6, 9, 29]

希望有帮助,如果我错了,请纠正我

我已经做了一段时间了,我已经找到了一个很好的解决方案。我没有想到这个算法,但我在javascript中正确地实现了它。我已经用大量的数组测试了它,并且我包含了注释,所以更容易理解。与许多其他解决方案不同,这是最有效的解决方案之一,我已经包含了一些测试。您可以运行代码来验证它是否有效。该解的时间复杂度为O(n)

function mergeTwoSortedArraay(rightArr, leftArr) {
 // I decided to call frist array "rightArr" and second array "leftArr"
  var mergedAr = [], sizeOfMergedArray = rightArr.length + leftArr.length; // so if rightArray has 3 elements and leftArr has 4, mergedArray will have 7.
   var r = 0, l =0; // r is counter of rightArr and l is for leftArr;
   for(var i =0; i< sizeOfMergedArray; ++i) {
       if(rightArr[r] >= leftArr[l] || r >= rightArr.length) { // r >= rightArr.length when r is equal to greater than length of array, if that happens we just copy the reaming 
        // items of leftArr to mergedArr
            mergedAr[i] = leftArr[l];
            l++;
       } else { 
           mergedAr[i] = rightArr[r];
           r++;
       }
   }
   return mergedAr;
}
// few tests
console.log(mergeTwoSortedArraay([ 0, 3, 4, 7, 8, 9 ],[ 0, 4, 5, 6, 9 ]));
console.log(mergeTwoSortedArraay([ 7, 13, 14, 51, 79 ],[ -356, 999 ]));
console.log(mergeTwoSortedArraay([ 7, 23, 64, 77 ],[ 18, 42, 45, 90 ]));

这可能不是最干净的方法,但请尝试一下。

function mergeSortedArrays(array1, array2){
  const mergedArray = [];
  let array1Item = array1[0];
  let array2Item = array2[0];
  let i = 1;
  let j = 1;
 
  if(array1.length === 0) {
    return array2;
  }
  if(array2.length === 0) {
    return array1;
  }
  while (array1Item || array2Item){
   if(array2Item === undefined || array1Item < array2Item){
     mergedArray.push(array1Item);
     array1Item = array1[i];
     i++;
   }   
   else {
     mergedArray.push(array2Item);
     array2Item = array2[j];
     j++;
   }
  }
  return mergedArray;
}
mergeSortedArrays([0,3,4,31], [3,4,6,30]);

// Everything fine but small mistake down there
function sortedArray(a,b){
    for(var i=0;i<b.length;i++){
        a.push(b[i]);
    }
    //console.log(a);
for(i=0;i<a.length;i++)
    {
        for(j=i+1;j<a.length;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    
    //<!--You did a mistake here you have loop through for to get array elements-->
    for(i=0;i<a.length;i++){
    return a;
    }
}
console.log(sortedArray([1,2,3,5,9],[4,6,7,8]));

如果不允许使用内置的排序方法:

function mergeSortedArrays(a, b) {
   let storage = [];
   let aLen = a.length;
   let bLen = b.length;
   let i = 0;
   let j = 0;
   while(i < aLen || j < bLen){ 
     if(a[i] < b[j]){
       storage.push(a[i]);
       i++;
     }
     else if(a[i] >= b[j]){
       storage.push(b[j]);
       j++;
     }
     else if(a[i] === undefined){
       storage.push(b[j]);
       j++;
     }
     else if(b[j] === undefined){
       storage.push(a[i]);
       i++;
     }
   }
   return storage
}

如果允许使用排序方法,这样更好:

function mergeSortedArrays(a, b){
   let result = a.concat(b);  //concat both arrays into one first
   return result.sort((a,b) => a - b)  //then sort the concated array
}

试试这个。

function mergeSortedArrays(a, b) {
    //Setting up the needed variables
    let mergedArray = [], aIndex = 0, bIndex = 0, 
        mergedIndex = 0, aCount = a.length, 
        bCount = b.length;
        
    //Loop until all items from the array merges in
    while (mergedIndex < (aCount + bCount)) {
        mergedArray[mergedIndex++] = (a[aIndex] < b[bIndex]) ? a[aIndex++] : b[bIndex++];
    }
    return mergedArray;
}
    mergeSortedArrays([1, 3, 5, 7, 9], [2, 4, 6, 8, 10, 20, 30, 40]);

下面是我实现这个目标的简单代码:

function mergeSortetArrays(array1, array2) {
const mergedArray = []; //This is const, we don't have to change the type of this array
let array1Item = array1[0];// We use let, because it will store undefined
let array2Item = array2[0];
let i = 1;
let j = 1;
//check input
if(array1.length === 0)
    return array2;
if(array2.length === 0)
    return array1;
//loop through each array, and store to the mergedArray
    while( array1Item || array2Item) {
       console.log(array1Item, array2Item);
        if (!array2Item || array1Item < array2Item) {
            mergedArray.push(array1Item);
            array1Item = array1[i]
            i++;
            } else {
                mergedArray.push(array2Item);
                array2Item = array2[j];
                j++;
         }
   }
   return mergedArray;
 }
console.log(mergeSortetArrays([0, 1, 3, 5,7,8, 8], [1, 2, 3, 4, 6, 7]))

合并N个排序数组

基于Dovev Hefetz的答案(https://stackoverflow.com/a/48147806/1167223),但支持N数组并接受sortFn作为属性

function mergeArrays(arrays, sortFn) {
  return arrays.reduce(function mergeArray(arrayA, arrayB, index) {
    // For the first iteration return the first array
    if (index === 0) {
      return arrayA;
    }
    const sorted = [];
    let indexA = 0;
    let indexB = 0;
    while (indexA < arrayA.length && indexB < arrayB.length) {
      if (sortFn(arrayA[indexA], arrayB[indexB]) > 0) {
        sorted.push(arrayB[indexB++]);
      } else {
        sorted.push(arrayA[indexA++]);
      }
    }
  
    // Add any remaining entries
    if (indexB < arrayB.length) {
      return sorted.concat(arrayB.slice(indexB));
    } else {
      return sorted.concat(arrayA.slice(indexA));
    };
  }, arrays[0]);
}

示例用

const merged = mergeArrays([
  [0, 1, 2, 3, 4, 5, 6],
  [0, 1, 2, 3, 3, 5, 5, 6],
  [0, 0, 2, 3, 4, 5, 6]
], (v1, v2) => v1 - v2);
console.log(merged);
/*
Results:
[
  0, 0, 0, 0, 1, 1, 2,
  2, 2, 3, 3, 3, 3, 4,
  4, 5, 5, 5, 5, 6, 6,
  6
]
*/

这是javascript中合并两个排序数组的代码。

class MergeSortArray {
  arr1 = [];
  arr2 = [];
  arr3 = [];
  constructor(arr1, arr2) {
    this.arr1 = arr1;
    this.arr2 = arr2;
  }
  mergeArray() {
    let n1 = this.arr1.length;
    let n2 = this.arr2.length;
    let i = 0,
      j = 0,
      k = 0;
    while (i < n1 && j < n2) {
      if (this.arr1[i] < this.arr2[j]) {
        this.arr3[k++] = this.arr1[i++];
      } else {
        this.arr3[k++] = this.arr2[j++];
      }
    }
    // Store remaining elements of first array
    while (i < n1) this.arr3[k++] = this.arr1[i++];
    // Store remaining elements of second array
    while (j < n2) this.arr3[k++] = this.arr2[j++];
    return this.arr3;
  }
}
let obj = new MergeSortArray([1, 3, 5, 7, 9, 11], [2, 4, 6, 8]);
let arr3 = obj.mergeArray();
console.log(arr3);

你可以在StackBlitz编辑器中找到代码:合并两个排序数组

时间复杂度和空间复杂度分别为 0 (n)

大多数答案是正确的,但他们忽略了等值比较

function merge(arr1, arr2) {
  let index1 = 0
  let index2 = 0
  const mergedArray = []
  while (index1 < arr1.length || index2 < arr2.length) {
    if (arr1[index1] < arr2[index2] || index2 === arr2.length) {
      mergedArray.push(arr1[index1])
      index1++
    } else if (arr1[index1] > arr2[index2] || index1 === arr1.length) {
      mergedArray.push(arr2[index2])
      index2++
    } else if (arr1[index1] === arr2[index2]) {
      mergedArray.push(arr1[index1])
      mergedArray.push(arr2[index2])
      index1++
      index2++
    }
  }
  return mergedArray
}
console.log(JSON.stringify(merge([1, 3, 5, 7, 8, 9, 10], [2, 4, 6, 11, 12])))