Каков наиболее эффективный способ объединения нескольких массивов отсортированных объектов в JavaScript?

Question

Рассмотрим четыре массива объектов все отсортированные по отдельности по дате

Объект: { id: userId, date : date }

Использование JavaScript, как я должен сортировать эти списки в один сводный список по дате?

Вот fiddle с четырьмя списками, индивидуально предварительно разобранными.

Answer 1

Потому что у меня есть что-то трудное и нужно откладывать :-) вот функция «mergeSortedArrays».

Он может принимать любое количество параметров, так что вы называете его как:

var resultSorted = mergeSortedArrays(resultA, resultB, resultC, resultD); 

Это не так хорошо, как это могло быть, потому что она объединяет только два массива одновременно. Возможно, лучшая реализация одновременно объединит все массивы. (Я не уверен, как это было бы сравнить хотя)

Реализация:

function mergeSortedArrays() { 
    function merge(arrayOne, arrayTwo) {   
     var totalLength = arrayOne.length + arrayTwo.length; 
     var returnArray = new Array(totalLength); 
     var iResult = 0; 
     var iOne = 0; 
     var iTwo = 0; 
     for(var i = 0; i < totalLength; ++i) { 
      if(iTwo < arrayTwo.length) { 
       if(iOne >= arrayOne.length) { 
        returnArray[i] = arrayTwo[iTwo++];      
       } else if (arrayOne[iOne].date < arrayTwo[iTwo].date) { 
        returnArray[i] = arrayOne[iOne++]; 
       } else { 
        returnArray[i] = arrayTwo[iTwo++]; 
       } 
      } else { 
       returnArray[i] = arrayOne[iOne++]; 
      } 
     } 
     return returnArray; 
    } 
    var sortedArray = []; 
    for(var i = 0; i < arguments.length; ++i) { 
     sortedArray = merge(sortedArray, arguments[i]); 
    } 
    return sortedArray; 
} 

Вот jsFiddle

Answer 2

Если у вас определенно пройденные вами массивы, наиболее эффективная вещь, о которой я могу думать, это сделать свой собственный алгоритм слияния. Это было бы примерно так:

var merged = []; 
var arrIndex1 = 0; 
var arrIndex2 = 0; 
var arrIndex3 = 0; 
var arrIndex4 = 0; 

while (arrIndex1 < arr1.length || arrIndex2 < arr2.length || arrIndex3 < arr3.length || arrIndex4 < arr4.length) { 
    var val1 = arrIndex1 < arr1.length ? arr1[arrIndex1].date : Number.POSITIVE_INFINITY; 
    var val2 = arrIndex2 < arr1.length ? arr2[arrIndex2].date : Number.POSITIVE_INFINITY; 
    var val3 = arrIndex3 < arr1.length ? arr3[arrIndex3].date : Number.POSITIVE_INFINITY; 
    var val4 = arrIndex4 < arr1.length ? arr4[arrIndex4].date : Number.POSITIVE_INFINITY; 

    if (val1 < val2 && val1 < val3 && val1 < val4) { 
      merged.push(arr1[arrIndex1++]); 
    } else if (val2 < val2 && val1 < val3 && val1 < val4) { 
      merged.push(arr2[arrIndex2++]); 
    } else if (val3 < val2 && val1 < val3 && val1 < val4) { 
      merged.push(arr3[arrIndex3++]); 
    } else { 
      merged.push(arr4[arrIndex4++]); 
    } 
} 

Это был бы самый быстрый способ. Тем не менее, самый простой способ закодировать его - если вы не обеспокоены тем, что он был самым быстрым - это просто четыре массива вместе и запустить их через функцию activites.sort().