javascript - 为类似数据结构的区 block 链对象数组排序

Question

我有一个对象数组，如下所示:

var arr = [
  { id: 1, prev: 0 },
  { id: 4, prev: 3 },
  { id: 3, prev: 2 },
  { id: 8, prev: 7 }
  { id: 5, prev: 4 },
  { id: 7, prev: 6 },
  { id: 6, prev: 5 },
  { id: 2, prev: 1 }
]

我正在从服务器获取此数组，但无法保证顺序。我想对数组进行排序，使每个对象后跟 prev 的对象属性与 id 相同前一个对象的属性。

例如，

// Given the following array
var arr = [
  { id: 1, prev: 0 },
  { id: 4, prev: 3 },
  { id: 3, prev: 2 },
  { id: 8, prev: 7 }
  { id: 5, prev: 4 },
  { id: 7, prev: 6 },
  { id: 6, prev: 5 },
  { id: 2, prev: 1 }
]

function compareFn(a, b) {
}

var sortedArray = arr.sort( compareFn );

console.log(sortedArray);
/* Should be
[
  { id: 1, prev: 0 },
  { id: 2, prev: 1 },
  { id: 3, prev: 2 },
  { id: 4, prev: 3 }
  { id: 5, prev: 4 },
  { id: 6, prev: 5 },
  { id: 7, prev: 6 },
  { id: 8, prev: 7 }
]
*/

我尝试了以下 compareFn()

function compareFn(a, b) {
  return a.id === b.prev ? 1 : -1
}

但是这会导致:

[
  { 'id': 1, 'prev': 0 },
  { 'id': 3, 'prev': 2 },
  { 'id': 4, 'prev': 3 },
  { 'id': 8, 'prev': 7 },
  { 'id': 5, 'prev': 4 },
  { 'id': 6, 'prev': 5 },
  { 'id': 7, 'prev': 6 },
  { 'id': 2, 'prev': 1 }
]

我很确定这是因为排序函数中的相等性而不是通常的 >/</<=/>=但我不知道问题出在哪里。

我可以使用循环进行排序，但我想更好地理解 .sort 是如何排序的方法有效。

任何帮助都会很棒。

谢谢

Answer 1

假设 prev 值的顺序不可靠(毕竟它是区 block 链):

我不会为此使用内置的 sort - 它需要一致的比较功能，但每个项目的位置取决于 最后 排序项目的位置。为此使用 .sort 会很复杂。相反，首先创建一个查找表(由 prev 索引的对象)，然后从 0 的 prev 开始迭代，在查找表中找到合适的对象，直到所有对象都在新数组中:

var arr = [
  { id: 1, prev: 0 },
  { id: 4, prev: 3 },
  { id: 3, prev: 2 },
  { id: 8, prev: 7 },
  { id: 5, prev: 4 },
  { id: 7, prev: 6 },
  { id: 6, prev: 5 },
  { id: 2, prev: 1 }
];

const itemsByPrev = arr.reduce((a, item) => {
  a[item.prev] = item;
  return a;
}, {});

const sorted = [];
let lastId = 0;
const { length } = arr;
while (sorted.length < length) {
  const obj = itemsByPrev[lastId];
  sorted.push(obj);
  lastId = obj.id;
}
console.log(sorted);

使用此方法的另一个好处是它具有 O(n) 的复杂性，而 .sort 的复杂性为 O(n log n) 复杂度。