如何合并排序数组在JavaScript

Question

我有三个排序数组，如下所示

[{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}]
[{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}]
[{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}]

这些数组根据数组中每个对象的名称属性进行排序。下面是我从Java转换为合并两个排序数组的方法

function mergeSorted(a, b) {
  var answer = new Array(a.length + b.length), i = 0, j = 0, k = 0;
  while (i < a.length && j < b.length) {
    if (a[i].name < b[j].name) {
        answer[k] = a[i];
        i++;
    }else {
        answer[k] = b[j];
        j++;
    }
    k++;
  }
  while (i < a.length) {
    answer[k] = a[i];
    i++;
    k++;
  }
  while (j < b.length) {
    answer[k] = b[j];
    j++;
    k++;
  }
  return answer;
}

这里是两个数组的工作小提琴http://jsfiddle.net/euRn5/.什么是最好的方法来实现相同的n个数组，我目前的想法是一个接一个，合并它与以前合并到最后项目，像n=i的东西。这是最好的方法吗？

Answer 1

更快，只合并1次，更灵活（保留重复，自定义比较器）：

/*  mergeSortedArrays(arrays[, keepDuplicates[, comparator[, thisArg]]])
    Merges multiple sorted arrays into a new sorted array.
    Arguments:
        - arrays: array of sorted arrays to be merged
        - keepDuplicates (optional): (true/false) whether to keep duplicate values
            Default: false
        - comparator (optional): function used to compare values
            Default: sort numbers in ascending order
            Example comparator: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
        - thisArg (optional): comparator is bound to thisArg when invoked
    Returns: a new sorted array containing all the values from the arrays
*/
function mergeSortedArrays(arrays, keepDuplicates, comparator, thisArg) {
    // Coerce to boolean to speed up testings in some javascript engines:
    keepDuplicates = !!keepDuplicates;

    // By default, sort numbers in ascending order:
    if(!comparator) comparator = function(a, b) { return a - b; };

    var nb = arrays.length,     // Number of arrays to be merged
        iter = new Array(nb),   // Current position of iteration of each array
        next = [],              // Keep each array sorted by the value of their next element
        length = 0;             // The combined length of all arrays

    // Populate iter and next:
    for(var i = 0, arr; i < nb; i++) {
        arr = arrays[i];
        iter[i] = 0;
        if(arr.length > 0) {
            insertNextIndex(next, i, arr[0], comparator, thisArg);
        }
        length += arr.length;
    }

    // Insert index of array into next:
    function insertNextIndex(next, index, val, comparator, thisArg) {
        var i = next.length;
        while(i--) {    // Reverse loop...
            var j = next[i];
            if(comparator.call(thisArg, arrays[j][iter[j]], val) >= 0) {    // ...until we find a greater value
                break;
            }
        }
        next.splice(i + 1, 0, index);
    }


    var merged = keepDuplicates ? new Array(length) : [],
        k = 0,  // Iterate over merged
        min, val, lastVal;

    // First iteration to get a value for lastVal (for duplicate checks):
    if(!keepDuplicates && next.length > 0) {
        min = next.pop();
        arr = arrays[min];
        i = iter[min]++;
        val = arr[i];
        merged[k++] = val;
        lastVal = val;
        if(++i < arr.length) {  // If available, insert next value in next:
            insertNextIndex(next, min, arr[i], comparator, thisArg);
        }
    }

    // Merge multiple arrays:
    while(next.length > 1) {    // While there is still multiple arrays to be merged
        min = next.pop();
        arr = arrays[min];
        i = iter[min]++;
        val = arr[i];
        if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
            merged[k++] = val;
            lastVal = val;
        }
        if(++i < arr.length) {  // If available, insert next value in next:
            insertNextIndex(next, min, arr[i], comparator, thisArg);
        }
    }

    // When there remain only 1 array with unmerged values, use a faster loop:
    if(next.length > 0) {
        arr = arrays[next[0]];
        i = iter[next[0]];
        length = arr.length;

        while(i < length) { // To the end
            val = arr[i++];
            if(keepDuplicates || comparator.call(thisArg, lastVal, val) !== 0) {
                merged[k++] = val;
                lastVal = val;
            }
        }
    }

    return merged;
}

一次合并消除了创建中间数组的过程，这需要时间和内存。此外，通过保留每个数组中下一个元素的排序列表（请参见nextarray），可以很好地减少比较次数。当数组大小已知时，会预先分配它们以防止动态重新分配（尽管这取决于javascript引擎）。

对于你的情况，我会这样称呼它：

mergeSortedArrays(arrays, true, function(a, b) {
    return a.name < b.name ? -1 : 1;
});

注意：如果你有大量的数组，你可能会受益于使用二进制搜索，而不是线性搜索中的插入NextIndex（）。或者从使用二进制堆的下一个。

Answer 2

鉴于它是current_year，现在将是：

const mergeAll = (...arrays) => arrays.reduce(mergeSorted);

如果你觉得功能这是一个完美的地方使用减少。

var mergeAll = function(){
    return Array.prototype.slice.call(arguments).reduce(mergeSorted);
};

例子：

var a = [{name:"a"}, {name:"b"}, {name:"m"}, {name:"x"}];
var b = [{name:"a"}, {name:"e"}, {name:"i"}, {name:"o"}];
var c = [{name:"g"}, {name:"h"}, {name:"m"}, {name:"n"}];

console.log(mergeAll(a,b,c).map(function(x){return x.name;}));

jsfiddle：http://jsfiddle.net/FeT6m/

Answer 3

我相信这是最标准、最容易理解的代码。。

function mergeArray(arr1, arr2) {
 var new_array = [];
 var i = 0,
     j = 0,
     index = 0;

 while (new_array.length != (arr1.length + arr2.length) - 1) {
     if (arr1[i] < arr2[j]) {
         new_array.push(arr1[i]);
         i++;
     } else {
         new_array.push(arr2[j]);
         j++;
     }
 }
 return new_array;
}

函数调用：

var merged_array = mergeArray([1,6,9,95], [2,7,10,11,14,18]);