Сортировка по заказу в зависимости от другого массива

Question

У меня есть объект, который возвращается из базы данных следующим образом: [{id:1},{id:2},{id:3}]. У меня есть другой массив, который задал порядок, в который должен быть отсортирован первый массив, например: [2,3,1].

Я ищу метод или алгоритм, который может принимать в этих двух массивах и возвращает [{id:2},{id:3},{id:1}]. В идеале это должно быть своего рода эффективным, а не квадратным.

Answer 1

Если вы хотите линейное время, первый построить хеш-таблицу из первого массива, а затем выбрать элементы в порядке, обернув второе:

data = [{id:5},{id:2},{id:9}] 
 
order = [9,5,2] 
 

 
hash = {} 
 
data.forEach(function(x) { hash[x.id] = x }) 
 

 
sorted = order.map(function(x) { return hash[x] }) 
 

 
document.write(JSON.stringify(sorted))

Answer 2

Насколько я понимаю, сортировка не требуется; по крайней мере, в вашем примере, желаемый результирующий массив может быть сгенерирован в линейном времени следующим образом.

var Result; 
for (var i = 0; i < Input.length; i++) 
{ 
    Result[i] = Input[Order[i]-1]; 
} 

Здесь Result это желаемый результат, Input ваш первый массив и Order массив, содержащий нужные позиции.

Answer 3

function sortArrayByOrderArray(arr, orderArray) { 
 
     return arr.sort(function(e1, e2) { 
 
      return orderArray.indexOf(e1.id) - orderArray.indexOf(e2.id); 
 
     }); 
 
    } 
 

 
    console.log(sortArrayByOrderArray([{id:1},{id:2},{id:3}], [2,3,1]));

Answer 4

var objArray = [{id:1},{id:2},{id:3}]; 
var sortOrder = [2,3,1]; 

var newObjArray = []; 
for (i in sortOrder) { 
    newObjArray.push(objArray[(sortOrder[i]) - 1]) 
}; 

Answer 5

Почему бы не просто создать новый массив и нажмите значение из второго массива в ?? Поправьте меня, если я неправильно

array1 = []; 
array2 = [2,3,1]; 

for (var i = 0; i < array2 .length; i++) 
{ 
    array1.push({ 
     id : array2[i] 
    }) 
} 

Answer 6

В вашем примере, объекты сначала сортируются по id, что делает задачу довольно легко. Но если это вообще не так, вы можете сортировать объекты по линейному времени в соответствии с вашим массивом значений id.

Идея состоит в том, чтобы сначала создать индекс, который отображает каждое значение id в его положение, а затем вставлять каждый объект в нужную позицию, просматривая его значение id в индексе. Это требует итерации над двумя массивами длиной n, в результате чего общее время работы O(n) или линейное время. Нет асимптотически более быстрой работы, потому что для считывания входного массива требуется линейное время.

function objectsSortedBy(objects, keyName, sortedKeys) { 
 
    var n = objects.length, 
 
     index = new Array(n); 
 
    for (var i = 0; i < n; ++i) { // Get the position of each sorted key. 
 
    index[sortedKeys[i]] = i; 
 
    } 
 
    var sorted = new Array(n); 
 
    for (var i = 0; i < n; ++i) { // Look up each object key in the index. 
 
    sorted[index[objects[i][keyName]]] = objects[i]; 
 
    } 
 
    return sorted; 
 
} 
 

 
var objects = [{id: 'Tweety', animal: 'bird'}, 
 
       {id: 'Mickey', animal: 'mouse'}, 
 
       {id: 'Sylvester', animal: 'cat'}], 
 
    sortedIds = ['Tweety', 'Mickey', 'Sylvester']; 
 

 
var sortedObjects = objectsSortedBy(objects, 'id', sortedIds); 
 

 
// Check the result. 
 
for (var i = 0; i < sortedObjects.length; ++i) { 
 
    document.write('id: '+sortedObjects[i].id+', animal: '+sortedObjects[i].animal+'<br />'); 
 
}