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

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

提问by Amit Modi

In this program merged two array and then sorted using temp.but this not correct method.because two array are sorted ,so method should be unique i.e. merging of two sorted in sorted form should be unique.

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

Example:

例子：

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

• 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]));

回答by Dovev Hefetz

Based on Eric Lundgren's answer above, but this fixes a couple of major bugs and is more efficient. Worked for me in production. I included using a sort function for more complex solutions - for this simple case you can just test for a > b as in Eric's answer if you want.

基于上面 Eric Lundgren 的回答，但这修复了几个主要错误并且效率更高。在生产中对我来说有效。我包括对更复杂的解决方案使用排序函数 - 对于这个简单的情况，如果你愿意，你可以像 Eric 的答案一样测试 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]));

回答by Erik Inkap??l

How about something like this?

这样的事情怎么样？

Since a and b are both sorted we only need to consider the top or first item of each array when adding. Note that this method will modify both a and b during execution, this may not be what you want, in which case you can add this code at the start:

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

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

This will make copies of the array which you can then use instead of aand bin the function below:

这将制作数组的副本，然后您可以在下面的函数中使用它来代替a和b：

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

Without using splice at all, try something like this:

根本不使用 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]));

回答by David Lac

Hey I ran everyone's code from above against a simple .concat() and .sort() method. With both large and small arrays, the .concat() and .sort() completes in less time, significantly.

嘿，我从上面针对简单的 .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

With arrays of 10,000 size, the difference is even larger with the concat and sort running even faster than before (4.831 ms vs .008 ms).

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

What's happening in javascript's sort that makes it faster?

javascript 排序中发生了什么使其更快？

回答by Ashok R

Merge two arrays and create new array.

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

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

回答by Ashok R

Merge two sorted arrays - Answer with comments

合并两个已排序的数组 - 用注释回答

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

回答by user3717718

Merging two sorted arrays.

合并两个已排序的数组。

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

More compact code:

更紧凑的代码：

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

回答by Max Leizerovich

The issue I see with most solutions here is that they don't precreate the array, just pushing into an array when you know the end game size is a little bit wasteful.

我在这里看到的大多数解决方案的问题是，它们不预先创建数组，只是在您知道最终游戏大小有点浪费时才推入数组。

This is my suggestion, we can make it a little more efficient but it will make it less readable:

这是我的建议，我们可以让它更有效率，但它会降低可读性：

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]))

回答by akshay bagade

can do with es6 spread operator

可以使用 es6 扩展运算符

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

let newArray=[...a,...b].sort()
console.log(newArray)

回答by Oliver

I needed it so implemented my ownn

我需要它所以实现了我自己的

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++];
}

回答by Darkpiece

ShortestMerge Sorted arrays without sort() plus, without using third temp array.

没有 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])