如何按父级优先子级紧随的层级结构排序含ParentId的数组

我有一组包含父子关系的数据数组，每个元素包含Id、Name、ParentId字段：

• ParentId为null的是父级元素
• 其余元素是对应父级的子级

希望将数组排序为父级元素在前，紧接着展示其子级元素的结构，原数组与期望排序后的数组如下：

原数组 #

[
    {
        "Id": 40,
        "Name": "Version 1",
        "ParentId": null
    },
    {
        "Id": 45,
        "Name": "Version 3",
        "ParentId": null
    },
    {
        "Id": 50,
        "Name": "Version 1.1",
        "ParentId": 40
    },
    {
        "Id": 56,
        "Name": "Version 2",
        "ParentId": null
    },
    {
        "Id": 57,
        "Name": "Version 3.1",
        "ParentId": 45
    },
    {
        "Id": 59,
        "Name": "Version 2.1",
        "ParentId": 56
    },
    {
        "Id": 77,
        "Name": "Version 3.2",
        "ParentId": 45
    }
]

期望排序后数组 #

[
    {
        "Id": 40,
        "Name": "Version 1",
        "ParentId": null
    },
    {
        "Id": 50,
        "Name": "Version 1.1",
        "ParentId": 40
    },
    {
        "Id": 56,
        "Name": "Version 2",
        "ParentId": null
    },
    {
        "Id": 59,
        "Name": "Version 2.1",
        "ParentId": 56
    },
    {
        "Id": 45,
        "Name": "Version 3",
        "ParentId": null
    },
    {
        "Id": 57,
        "Name": "Version 3.1",
        "ParentId": 45
    },
    {
        "Id": 77,
        "Name": "Version 3.2",
        "ParentId": 45
    }
]

可以通过以下步骤实现：

1. 先将子级元素按父级Id分组，建立父级Id到子级数组的映射
2. 筛选出所有父级元素，按Name中的版本号排序
3. 遍历排序后的父级数组，依次将父级元素和其对应的子级元素（同样按版本号排序）加入结果数组

代码示例（JavaScript） #

const data = [
    { "Id": 40, "Name": "Version 1", "ParentId": null },
    { "Id": 45, "Name": "Version 3", "ParentId": null },
    { "Id": 50, "Name": "Version 1.1", "ParentId": 40 },
    { "Id": 56, "Name": "Version 2", "ParentId": null },
    { "Id": 57, "Name": "Version 3.1", "ParentId": 45 },
    { "Id": 59, "Name": "Version 2.1", "ParentId": 56 },
    { "Id": 77, "Name": "Version 3.2", "ParentId": 45 }
];

// 1. 建立父级Id到子级数组的映射
const childrenMap = {};
data.forEach(item => {
    if (item.ParentId !== null) {
        if (!childrenMap[item.ParentId]) {
            childrenMap[item.ParentId] = [];
        }
        childrenMap[item.ParentId].push(item);
    }
});

// 2. 筛选父级并按版本号自然排序
const parents = data.filter(item => item.ParentId === null).sort((a, b) => {
    const parseVersion = name => name.split(' ')[1].split('.').map(Number);
    const aVersion = parseVersion(a.Name);
    const bVersion = parseVersion(b.Name);
    
    for (let i = 0; i < Math.max(aVersion.length, bVersion.length); i++) {
        const aNum = aVersion[i] || 0;
        const bNum = bVersion[i] || 0;
        if (aNum !== bNum) return aNum - bNum;
    }
    return 0;
});

// 3. 组合父级和子级，子级同样按版本号排序
const sortedResult = [];
parents.forEach(parent => {
    sortedResult.push(parent);
    const children = childrenMap[parent.Id] || [];
    children.sort((a, b) => {
        const parseVersion = name => name.split(' ')[1].split('.').map(Number);
        const aVersion = parseVersion(a.Name);
        const bVersion = parseVersion(b.Name);
        
        for (let i = 0; i < Math.max(aVersion.length, bVersion.length); i++) {
            const aNum = aVersion[i] || 0;
            const bNum = bVersion[i] || 0;
            if (aNum !== bNum) return aNum - bNum;
        }
        return 0;
    });
    sortedResult.push(...children);
});

console.log(sortedResult);

代码说明 #

• 分组映射：遍历数组将子级元素归类到对应父级Id的数组中，后续可快速查找父级对应的所有子级
• 版本号排序：解析Name中的版本号为数字数组，实现自然排序（比如Version 1 < Version 2 < Version 3，子级同理）
• 结果组合：按排序后的父级顺序，依次添加父级和其对应的子级，最终得到父级紧跟子级的结构

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