如何在JavaScript中按startAfter属性构建对象数组的依赖链式排序？

现有未排序的对象数组：

const unsortedArr =  [
  {
    id: "test13",
    startAfter: "test15"
  },
  {
    id: "test20",
    startAfter: "test5"
  },
  { 
    id: "test5",
    startAfter: "test1"
  },
  {
    id: "test15",
    startAfter: "test20"
  },
]

已知起始ID：

const startId = "test1";

需要以startId为起点，根据每个对象的startAfter属性构建时序链，将数组排序为如下结果：

const sortedArr =  [
    {
      id: "test5",
      startAfter: "test1"
    },
    {
      id: "test20",
      startAfter: "test5"
    },
    {
      id: "test15",
      startAfter: "test20"
    },
    {
      id: "test13",
      startAfter: "test15"
    },
]

最简实现代码 #

function sortBySequence(arr, startId) {
  const startMap = new Map();
  arr.forEach(item => startMap.set(item.startAfter, item));

  const sorted = [];
  let current = startId;
  while (startMap.has(current)) {
    const nextItem = startMap.get(current);
    sorted.push(nextItem);
    current = nextItem.id;
  }
  return sorted;
}

// 调用得到排序后的数组
const sortedArr = sortBySequence(unsortedArr, startId);

说明 #

这种方法时间复杂度为O(n)，比常规排序更高效：

1. 先遍历一次数组，用Map构建「startAfter值对应对象」的映射，后续查找下一个节点仅需常数时间
2. 从起始ID开始，顺着映射表依次取出对应对象加入结果数组，直到链条上没有下一个节点为止
3. 逻辑直观简洁，完全贴合时序链的需求，不需要额外的排序对比逻辑

内容的提问来源于stack exchange，提问作者1zz0