求实现JavaScript排序算法：按after字段将元素置于指定元素后

解决方案思路 #

• 先构建元素ID到元素的映射表，避免反复遍历数组查找元素，提升效率
• 提取所有after为null的元素，严格保留它们在原始数组中的顺序，作为排序后的初始列表
• 对每个元素，递归查找并添加所有以该元素ID为after值的后续元素，后续元素的顺序同样遵循它们在原始数组中的出现顺序
• 递归处理每个后续元素的子节点，确保层级嵌套的元素能紧跟在父元素之后

代码实现（JavaScript） #

function sortByAfterField(elements) {
    // 建立ID到元素的映射，方便快速查找
    const elementMap = new Map();
    elements.forEach(el => elementMap.set(el.id, el));

    // 建立after值到对应元素列表的映射，按原始顺序存储
    const afterMap = new Map();
    elements.forEach(el => {
        if (el.after !== null) {
            if (!afterMap.has(el.after)) {
                afterMap.set(el.after, []);
            }
            afterMap.get(el.after).push(el);
        }
    });

    // 递归添加当前元素的所有后续元素
    function addChildren(element, result) {
        result.push(element);
        // 获取当前元素的所有子元素（after指向当前元素id的元素）
        const children = afterMap.get(element.id) || [];
        // 遍历子元素，递归添加它们和它们的子元素
        children.forEach(child => addChildren(child, result));
    }

    const sortedResult = [];
    // 先处理所有after为null的元素，按原始顺序
    elements.forEach(el => {
        if (el.after === null) {
            addChildren(el, sortedResult);
        }
    });

    return sortedResult;
}

// 测试用例
const input = [
    {"id": 1871, "after": null},
    {"id": 1872, "after": null},
    {"id": 1873, "after": 1872},
    {"id": 1874, "after": 1872},
    {"id": 1875, "after": 1873},
    {"id": 1876, "after": 1875},
    {"id": 1877, "after": 1876},
    {"id": 1878, "after": 1877},
    {"id": 1879, "after": null},
    {"id": 1880, "after": 1874}
];

const sorted = sortByAfterField(input);
console.log(JSON.stringify(sorted, null, 2));

验证结果 #

运行上述代码后，输出结果与题目要求的排序结果完全一致：

[
  {
    "id": 1871,
    "after": null
  },
  {
    "id": 1872,
    "after": null
  },
  {
    "id": 1873,
    "after": 1872
  },
  {
    "id": 1875,
    "after": 1873
  },
  {
    "id": 1876,
    "after": 1875
  },
  {
    "id": 1877,
    "after": 1876
  },
  {
    "id": 1878,
    "after": 1877
  },
  {
    "id": 1874,
    "after": 1872
  },
  {
    "id": 1880,
    "after": 1874
  },
  {
    "id": 1879,
    "after": null
  }
]

说明 #

• 该算法时间复杂度为O(n)，因为每个元素只会被访问两次（一次构建映射，一次递归添加）
• 严格保留了after为null的元素的原始顺序，以及同一after指向的元素的原始顺序
• 递归处理确保了嵌套层级的元素能正确紧跟在父元素之后，符合题目要求

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