在TypeScript中如何比对不同字段实现对象数组排序

实现思路 #

• 先构建name到对应对象的映射表，将父节点查询的时间复杂度降到O(1)
• 为每个节点递归生成排序键：如果父节点存在于当前数组中，排序键为「父节点排序键 + 分隔符 + 当前节点name」；如果父节点不存在，直接用当前节点name作为排序键
• 按排序键的字典序排序，天然保证父节点排序在前，子节点紧跟在后，二者相邻

完整代码实现 #

function sortByParentAdjacent(arr) {
  // 建立name到对象的映射
  const nameToItemMap = new Map(arr.map(item => [item.name, item]));
  // 缓存排序键避免重复计算
  const sortKeyCache = new Map();

  // 递归生成排序键
  const getSortKey = (item) => {
    if (sortKeyCache.has(item.name)) return sortKeyCache.get(item.name);
    
    const parentItem = nameToItemMap.get(item.parent);
    const key = parentItem ? `${getSortKey(parentItem)}/${item.name}` : item.name;
    sortKeyCache.set(item.name, key);
    return key;
  };

  // 按排序键字典序排序，这里用展开运算符避免修改原数组
  return [...arr].sort((a, b) => getSortKey(a).localeCompare(getSortKey(b)));
}

效果验证 #

传入你提供的示例数组测试：

const originArr = [
  {
    "name": "Bob",
    "parent": "Linda"
  },
  {
    "name": "Charlie",
    "parent": "Gregory"
  },
  {
    "name": "Linda",
    "parent": "Stacy"
  },
  {
    "name": "Andrew",
    "parent": "Gabriel"
  },
  {
    "name": "Gregory",
    "parent": "Thomas"
  }
];

const sortedArr = sortByParentAdjacent(originArr);
console.log(sortedArr);

输出结果如下，符合父子相邻的要求：

[
  { name: 'Andrew', parent: 'Gabriel' },
  { name: 'Linda', parent: 'Stacy' },
  { name: 'Bob', parent: 'Linda' },
  { name: 'Gregory', parent: 'Thomas' },
  { name: 'Charlie', parent: 'Gregory' }
]

如果需要子节点排在父节点前面，只需将sort回调的返回值取反即可：

return [...arr].sort((a, b) => getSortKey(b).localeCompare(getSortKey(a)));

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