问题背景与挑战
在前端或后端数据处理中，我们经常会遇到需要对具有层级关系的数据进行排序的场景。例如，一个产品列表可能包含主产品和其关联的子产品，同时每个产品都有一个显示优先级。我们的目标是根据以下规则对一个扁平化数组进行重排序：
- 父子关系优先： 具有 reference_id 的项（子项）必须紧随其父项（id 与 reference_id 匹配的项）之后。
- 显示优先级排序： 在同一层级（例如，所有顶层项之间，或同一父项的所有子项之间），应根据 display_priority 字段进行升序排列。
给定以下原始数据结构：
const originalData = [
{ id: 3, name: 'hello world', reference_id: null, display_priority: 10 },
{ id: 6, name: 'hello world', reference_id: 2, display_priority: 30 },
{ id: 1, name: 'hello world', reference_id: 2, display_priority: 40 },
{ id: 4, name: 'hello world', reference_id: null, display_priority: 80 },
{ id: 2, name: 'hello world', reference_id: null, display_priority: 100 },
{ id: 5, name: 'hello world', reference_id: 3, display_priority: 110 },
];我们期望得到的输出顺序如下：
[
{ id: 3, name: 'hello world', reference_id: null, display_priority: 10 },
{ id: 5, name: 'hello world', reference_id: 3, display_priority: 110 }, // id:5 是 id:3 的子项
{ id: 4, name: 'hello world', reference_id: null, display_priority: 80 },
{ id: 2, name: 'hello world', reference_id: null, display_priority: 100 },
{ id: 6, name: 'hello world', reference_id: 2, display_priority: 30 }, // id:6 是 id:2 的子项
{ id: 1, name: 'hello world', reference_id: 2, display_priority: 40 }, // id:1 也是 id:2 的子项
];可以看到，id: 3 作为父项，其 display_priority 为 10。其子项 id: 5 紧随其后。 然后是顶层项 id: 4 (priority 80)，接着是 id: 2 (priority 100)。 id: 2 的子项 id: 6 (priority 30) 和 id: 1 (priority 40) 紧随其后，且它们之间按 display_priority 排序。
现有尝试及局限性分析
用户最初尝试使用 Array.prototype.reduce 方法来迭代并构建排序后的数组：
const reorderedArray = test.reduce((acc, current) => {
const referenceId = current.reference_id;
if (referenceId === null) {
const referencedChildIndex = acc.findIndex(item => item.reference_id === current.id);
if (referencedChildIndex !== -1) {
acc.splice(referencedChildIndex, 0, current);
} else {
acc.push(current);
}
} else {
const referencedIndex = acc.findIndex(item => item.id === referenceId);
if (referencedIndex !== -1) {
acc.splice(referencedIndex + 1, 0, current);
} else {
acc.push(current);
}
}
return acc;
}, []);这种方法的主要局限在于它高度依赖于原始数组中元素的顺序。如果父元素在原始数组中出现在其子元素之后，或者子元素在父元素之前被处理，findIndex 可能无法找到对应的父/子项，导致元素被错误地放置到数组末尾。此外，这种方法并未充分考虑 display_priority 的排序逻辑，仅侧重于父子关系的插入。对于更复杂的层级结构和多重排序条件，这种迭代插入的方式难以保证最终结果的正确性和效率。
核心思路与设计
为了可靠地解决这个问题，我们需要一个更结构化的方法，它将分三个主要阶段进行：构建ID映射表、构建层级结构、排序层级结构 和 展平层级结构。
步骤一：构建ID映射表
首先，创建一个哈希映射（Map 或对象），将每个元素的 id 作为键，元素本身作为值。这使得我们能够以 O(1) 的时间复杂度通过 id 快速查找任何元素，这在构建父子关系时非常有用。
步骤二：构建层级结构
遍历原始数组中的每个元素。对于每个元素，我们将其视为一个潜在的节点。如果一个元素的 reference_id 不为 null，则说明它是一个子节点，需要将其添加到其父节点的 children 数组中。同时，我们需要识别出所有 reference_id 为 null 的顶层节点。
步骤三：排序层级结构
一旦构建了树状的层级结构（每个父节点包含一个 children 数组），我们就需要对这些结构进行排序。这通常通过递归完成：
- 对子节点排序： 遍历每个父节点，将其 children 数组按照 display_priority 进行升序排序。
- 对顶层节点排序： 对所有 reference_id 为 null 的顶层节点数组也按照 display_priority 进行升序排序。
步骤四：展平层级结构
最后一步是将排序后的树状结构展平回一个一维数组。这可以通过深度优先遍历（DFS）的递归方式实现：
- 遍历排序后的顶层节点。
- 对于每个顶层节点，将其添加到结果数组中。
- 如果该节点有子节点，则递归地对这些子节点执行相同的操作（先添加子节点本身，再处理其子节点），确保父节点在前，子节点紧随其后。
完整实现代码
下面是使用 JavaScript 实现上述思路的完整代码：
function reorderArrayByReferenceAndPriority(data) {
// 1. 构建ID映射表，并为每个项添加一个空的children数组
const itemMap = new Map();
data.forEach(item => {
// 创建一个副本，避免直接修改原始数据，并添加children属性
itemMap.set(item.id, { ...item, children: [] });
});
const topLevelItems = [];
// 2. 构建层级结构
itemMap.forEach(item => {
if (item.reference_id === null) {
// 顶级项
topLevelItems.push(item);
} else {
// 子项，尝试找到其父项
const parent = itemMap.get(item.reference_id);
if (parent) {
parent.children.push(item);
} else {
// 如果找不到父项，将其视为顶级项（或根据业务需求处理，例如报错）
topLevelItems.push(item);
console.warn(`Item with id ${item.id} has reference_id ${item.reference_id}, but parent not found.`);
}
}
});
// 3. 排序层级结构
// 递归函数，用于对子节点进行排序
function sortChildren(node) {
if (node.children && node.children.length > 0) {
node.children.sort((a, b) => (a.display_priority || 0) - (b.display_priority || 0));
node.children.forEach(child => sortChildren(child)); // 递归排序子节点的子节点
}
}
// 对所有顶级项的子节点进行排序
topLevelItems.forEach(item => sortChildren(item));
// 对顶级项本身进行排序
topLevelItems.sort((a, b) => (a.display_priority || 0) - (b.display_priority || 0));
// 4. 展平层级结构
const reorderedFlatArray = [];
// 递归函数，用于展平树结构
function flatten(node) {
// 添加当前节点到结果数组中，但移除临时的children属性
const { children, ...itemWithoutChildren } = node;
reorderedFlatArray.push(itemWithoutChildren);
if (children && children.length > 0) {
children.forEach(child => flatten(child));
}
}
// 遍历排序后的顶级项，并展平
topLevelItems.forEach(item => flatten(item));
return reorderedFlatArray;
}
// 原始数据
const originalData = [
{ id: 3, name: 'hello world', reference_id: null, display_priority: 10 },
{ id: 6, name: 'hello world', reference_id: 2, display_priority: 30 },
{ id: 1, name: 'hello world', reference_id: 2, display_priority: 40 },
{ id: 4, name: 'hello world', reference_id: null, display_priority: 80 },
{ id: 2, name: 'hello world', reference_id: null, display_priority: 100 },
{ id: 5, name: 'hello world', reference_id: 3, display_priority: 110 },
];
const reorderedResult = reorderArrayByReferenceAndPriority(originalData);
console.log(JSON.stringify(reorderedResult, null, 2));输出结果:
[
{
"id": 3,
"name": "hello world",
"reference_id": null,
"display_priority": 10
},
{
"id": 5,
"name": "hello world",
"reference_id": 3,
"display_priority": 110
},
{
"id": 4,
"name": "hello world",
"reference_id": null,
"display_priority": 80
},
{
"id": 2,
"name": "hello world",
"reference_id": null,
"display_priority": 100
},
{
"id": 6,
"name": "hello world",
"reference_id": 2,
"display_priority": 30
},
{
"id": 1,
"name": "hello world",
"reference_id": 2,
"display_priority": 40
}
]代码详解
-
itemMap 的构建与初始化：
- itemMap = new Map()：创建了一个 Map 结构，用于存储以 id 为键、以对象为值的元素。
- data.forEach(item => itemMap.set(item.id, { ...item, children: [] }))：遍历原始数据。为了避免直接修改原始对象，我们使用 { ...item, children: [] } 创建了一个浅拷贝，并为每个对象添加了一个空的 children 数组。这个 children 数组将用于存储其子节点。
-
构建层级结构：
- topLevelItems = []：用于收集所有 reference_id 为 null 的顶层项。
- itemMap.forEach(item => { ... })：再次遍历 itemMap 中的所有项。
- if (item.reference_id === null)：如果 reference_id 为 null，说明它是顶层项，直接加入 topLevelItems 数组。
- else { const parent = itemMap.get(item.reference_id); if (parent) { parent.children.push(item); } ... }：如果 reference_id 不为 null，则通过 itemMap.get(item.reference_id) 查找其父项。如果找到，就将当前项作为子项添加到父项的 children 数组中。如果找不到父项，则将其视为一个独立的顶层项（或根据业务需求进行错误处理），并发出警告。
-
排序层级结构：
- sortChildren(node) 递归函数：
- 它首先检查当前 node 是否有 children。
- 如果有，就使用 sort 方法根据 display_priority 对 children 数组进行升序排序。a.display_priority || 0 的用法确保了即使 display_priority 字段缺失，也能有一个默认值（0）进行排序，避免 undefined 导致的问题。
- 然后，它递归地对每个子节点调用 sortChildren，确保整个子树的 children 数组都被排序。
- topLevelItems.forEach(item => sortChildren(item))：对所有顶层项调用 sortChildren，从而对整个树结构中的所有子节点进行排序。
- topLevelItems.sort((a, b) => (a.display_priority || 0) - (b.display_priority || 0))：最后，对 topLevelItems 数组本身进行排序，以确定顶层项的最终顺序。
- sortChildren(node) 递归函数：
-
展平层级结构：
- reorderedFlatArray = []：最终结果数组。
- flatten(node) 递归函数：
- const { children, ...itemWithoutChildren } = node;：使用解构赋值将 children 属性从当前节点中分离，并将剩余属性组成一个新的对象 itemWithoutChildren。这是为了在最终输出中不包含临时的 children 属性。
- reorderedFlatArray.push(itemWithoutChildren);：将当前节点（不含 children 属性）添加到结果数组。
- if (children && children.length > 0) { children.forEach(child => flatten(child)); }：如果当前节点有子节点，则递归地对每个子节点调用 flatten 函数。由于 children 数组已经排序，并且是深度优先遍历，这确保了父节点在前，其排序后的子节点紧随其后。
- topLevelItems.forEach(item => flatten(item))：遍历排序后的顶层项，并调用 flatten 函数，从而将整个排序后的树结构展平为最终的一维数组。
注意事项
- 循环引用： 当前方案不包含循环引用检测。如果数据中存在 A 引用 B，B 又引用 A 的情况，可能会导致无限递归。在实际应用中，需要根据业务需求增加循环引用检测或限制递归深度。
- reference_id 不存在： 如果某个项的 reference_id 指向了一个不存在的 id，该项会被视为顶层项并发出警告。根据具体业务场景，可能需要更严格的错误处理，例如抛出异常或将其过滤掉。
- display_priority 缺失： 代码中使用了 (a.display_priority || 0)，这意味着如果 display_priority 字段缺失或为 null/undefined，它将被视为 0 进行排序。这是一种常见的默认处理方式，但如果业务有其他要求（例如，缺失的项排在最后），则需要调整排序逻辑。
- 数据量： 对于非常庞大的数据集，构建 Map 和递归操作可能会消耗较多内存和计算资源。但在大多数常见场景下，这种方法是高效且可维护的。
- 深拷贝与浅拷贝： 在构建 itemMap 时，我们对原始对象进行了浅拷贝 ({ ...item, children: [] })。这意味着原始对象中的嵌套对象仍然是引用。如果需要修改嵌套对象而不影响原始数据，则需要进行深拷贝。
总结
通过将扁平化数组转换为一个临时的树状结构，并结合 Map 进行高效查找、递归排序以及深度优先遍历展平，我们能够可靠地实现根据父子关系和显示优先级对数组对象进行排序的需求。这种方法结构清晰、逻辑严谨，能够有效应对复杂的层级和多重排序条件，是处理此类数据排序问题的通用且健壮的解决方案。
