Как объединить отсортированные массивы в JavaScript

У меня есть три отсортированных массива, например ниже

[{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. Это лучший подход?

Ответ 1

Обновление:

Увидев, что это 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/

Ответ 2

Стандартный и самый понятный код, который я считаю.

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

Ответ 3

Отредактировано, чтобы отразить это оригинальное решение Exception, расширенное, называя его как mergeSorted(mergeSorted(a,b),c) быстрее, чем мое решение здесь.

Javascript builtin sort [недостаточно], чтобы вы могли просто объединить все массивы вместе и отсортировать всю вещь за один раз. Javascript ~~not~~ хорош для повторной реализации вещей, которые должны выполняться на более низком уровне.

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

a1.concat(a2,a3).sort(function(a,b){return (a.name>b.name)-(a.name<b.name)})
// [{name:"a"}, {name:"a"}, {name:"b"}, {name:"e"}, {name:"h"}, {name:"i"}, {name:"g"}, {name:"m"}, {name:"m"}, {name:"n"}, {name:"o"}, {name:"x"}]

Ответ 4

Нативные реализации не всегда бывают самыми быстрыми (как вы могли заметить), и исторически они были несколько вялыми из-за обширной проверки ошибок. Тем не менее, в будущем могут быть улучшения производительности благодаря более надежной интеграции с аппаратными средствами или программами, специально созданными для оптимизации определенных задач. Если вы напишете свой собственный код, ваше приложение не сможет воспользоваться преимуществами повышения производительности после их реализации. Вам решать, где лежат преимущества и каковы риски.

Во всяком случае, я написал более красивую версию вашего оптимизированного кода для funsies:

function mergeSorted(a,b){
    var alen = a.length
      , blen = b.length
      , i, j, k = j = i = 0
      , answer = new Array(alen + blen)
    ;//var

    while(i < alen && j < blen)
                    answer[k++] = a[i].name < b[j].name ? a[i++] : b[j++];
    while(i < alen) answer[k++] = a[i++];
    while(j < blen) answer[k++] = b[j++];

    return answer;
}

Ответ 5

Быстрее, слияния всего за 1 проход, с большей гибкостью (keepDuplicates, пользовательский компаратор):

/*  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 is only 1 array left with 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;
}

Слияние за 1 проход устраняет создание промежуточных массивов, требующих времени и памяти. Кроме того, количество сравнений красиво уменьшается путем сохранения отсортированного списка следующего элемента из каждого массива (см. Массив next). И когда размеры массива известны, они предварительно выделены для предотвращения динамических перераспределений (хотя это будет зависеть от вашего механизма javascript).

В вашем случае я бы назвал это следующим образом:

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

Примечание. Если у вас есть большое количество массивов, вы можете использовать двоичный поиск вместо линейного поиска в insertNextIndex(). Или использовать Binary Heap для next.