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

Question

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

例：

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

Answer 1

这样的事情怎么样？

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

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

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

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

根本不使用 splice，试试这样的：

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

Answer 2

基于上面 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]));

Answer 3

嘿，我从上面针对简单的 .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 排序中发生了什么使其更快？