按照另一个数组的顺序对数组进行排序

Question

我有一个从数据库返回的对象，格式如下：[{id:1},{id:2},{id:3}]。我还有另一个数组，指定第一个数组应该按照什么顺序排序，格式如下：[2,3,1]。

我正在寻找一种方法或算法，可以接收这两个数组并返回[{id:2},{id:3},{id:1}]。最好是高效的，不要是n平方的。

- Alexis

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

- georg

Answer 2

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

- Barmar

Answer 3

在你的例子中，对象最初按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 />');
}

- Michael Laszlo

Answer 4

据我理解，在您的例子中，排序并不是必要的；可以通过以下方式在线性时间内生成所需的结果数组。

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

这里的Result是期望输出，Input是你的第一个数组，Order是包含所需位置的数组。

- Codor

---

这假设原始数组已按id值排序且它们是连续的。 - Barmar

你说得没错，但是提供的例子同时具备这两个属性，并且没有其他地方说明它们可能被违反。 - Codor

Answer 5

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

- Chirag Bhatia - chirag64

---

对象数组无法按排序顺序进行索引。 - Alexis

我的错误。我以为问题是第二个数组有排序的位置，而不是ID值。 - Chirag Bhatia - chirag64

Answer 6

为什么不直接创建一个新数组，然后将第二个数组中的值推入其中呢？如果我错了，请纠正我。

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

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

- yk1007