引言：理解复杂数组重排序需求
在前端或后端开发中，我们经常会遇到需要对数据列表进行复杂排序的场景。其中一种常见的需求是，数据项之间存在层级关系（例如，父子关系），同时每个数据项还有自身的显示优先级。我们的目标是将子项紧随其父项之后显示，并且在同级（包括顶层父项和同一父项下的子项）之间，需要根据display_priority进行升序排列。
考虑以下原始数据结构，它是一个包含多个对象的数组，每个对象有id、name、reference_id和display_priority字段：
const rawData = [
{ 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 },
];我们期望的输出结果应遵循以下规则：
- 如果一个元素的reference_id为null，它是一个顶层父项。
- 如果一个元素的reference_id不为null，它是一个子项，其父项的id与reference_id匹配。
- 子项必须紧随其父项之后。
- 所有顶层父项之间，以及同一父项下的所有子项之间，都应根据display_priority进行升序排列。
根据上述规则，期望的输出如下：
[
{ id: 3, name: 'hello world', reference_id: null, display_priority: 10 }, // 父项
{ id: 5, name: 'hello world', reference_id: 3, display_priority: 110 }, // 子项，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}, // 子项，display_priority: 30
{ id: 1, name: 'hello world', reference_id: 2, display_priority: 40}, // 子项，display_priority: 40
]可以看到，id: 3是第一个父项（display_priority: 10），其子项id: 5（reference_id: 3）紧随其后。接着是id: 4（display_priority: 80）和id: 2（display_priority: 100）这两个顶层父项，它们之间按display_priority排序。最后是id: 2的子项id: 6和id: 1，它们也按display_priority排序。
核心挑战分析
要实现这种复杂的重排序，我们面临以下几个主要挑战：
- 父子关系的建立与维护： 需要高效地识别每个元素的父项或子项，并能够快速地找到特定父项的所有子项。
- 多维度排序： 既要考虑父子层级，又要考虑display_priority。简单的sort函数无法一次性解决。
- 动态插入： 在构建最终数组时，需要将子项动态插入到其父项之后，而不是简单地追加。
原始尝试的reduce方法虽然试图解决父子插入问题，但它存在局限性：它依赖于父项在数组中出现的顺序，如果父项在子项之后，则可能无法正确插入。更重要的是，它没有完全处理display_priority的排序逻辑。
分步解决方案
为了克服上述挑战，我们将采用一个结构化的分步方法：
Java注释规范Skills
下载
当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。
步骤一：构建数据索引与分类
首先，我们需要对原始数据进行预处理，以便快速查找元素及其子项，并将所有元素分为顶层父项和子项。
- 创建父项映射： 使用一个Map来存储所有父项（reference_id为null）的id到其完整对象的映射，以及一个列表来存储顶层父项。
- 创建子项映射： 使用另一个Map来存储每个父项id对应的所有子项列表。
// 示例数据
const rawData = [
{ 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 parents = []; // 存储所有顶层父项
const childrenMap = new Map(); // 存储父项ID到其子项列表的映射
rawData.forEach(item => {
if (item.reference_id === null) {
parents.push(item);
} else {
if (!childrenMap.has(item.reference_id)) {
childrenMap.set(item.reference_id, []);
}
childrenMap.get(item.reference_id).push(item);
}
});步骤二：应用显示优先级排序
在构建最终数组之前，我们需要确保所有顶层父项和每个父项下的子项都已根据display_priority进行排序。
- 排序顶层父项： 对parents数组进行display_priority升序排序。
- 排序子项列表： 遍历childrenMap中的每个子项列表，并对它们进行display_priority升序排序。
// 排序顶层父项
parents.sort((a, b) => a.display_priority - b.display_priority);
// 排序每个父项下的子项
childrenMap.forEach(childList => {
childList.sort((a, b) => a.display_priority - b.display_priority);
});步骤三：构建最终有序数组
现在我们有了排序好的顶层父项和每个父项下排序好的子项列表，可以开始构建最终的有序数组。
遍历排序后的parents数组。对于每个父项，将其添加到结果数组中，然后查找其在childrenMap中对应的子项列表，并将这些子项也依次添加到结果数组中。
const reorderedArray = [];
parents.forEach(parent => {
reorderedArray.push(parent); // 添加父项
if (childrenMap.has(parent.id)) {
const sortedChildren = childrenMap.get(parent.id);
reorderedArray.push(...sortedChildren); // 添加排序后的子项
}
});JavaScript 示例代码
将上述步骤整合到一个函数中，可以得到一个完整的解决方案：
/**
* 根据父子关系和显示优先级对数组进行重排序。
* 父项通过 reference_id: null 标识，子项通过 reference_id 关联父项 id。
* 所有同级元素（包括顶层父项和同一父项下的子项）按 display_priority 升序排列。
*
* @param {Array<Object>} data 原始数据数组，每个对象需包含 id, reference_id, display_priority。
* @returns {Array<Object>} 重排序后的数组。
*/
function reorderArrayByParentAndPriority(data) {
if (!data || data.length === 0) {
return [];
}
const parents = []; // 存储所有顶层父项
const childrenMap = new Map(); // 存储父项ID到其子项列表的映射
// 步骤一：构建数据索引与分类
data.forEach(item => {
// 确保 display_priority 存在且为数字，否则默认为一个大值以防排序异常
const priority = typeof item.display_priority === 'number' ? item.display_priority : Infinity;
const itemWithPriority = { ...item, display_priority: priority };
if (item.reference_id === null) {
parents.push(itemWithPriority);
} else {
if (!childrenMap.has(item.reference_id)) {
childrenMap.set(item.reference_id, []);
}
childrenMap.get(item.reference_id).push(itemWithPriority);
}
});
// 步骤二：应用显示优先级排序
// 排序顶层父项
parents.sort((a, b) => a.display_priority - b.display_priority);
// 排序每个父项下的子项
childrenMap.forEach(childList => {
childList.sort((a, b) => a.display_priority - b.display_priority);
});
// 步骤三：构建最终有序数组
const reorderedArray = [];
parents.forEach(parent => {
reorderedArray.push(parent); // 添加父项
if (childrenMap.has(parent.id)) {
const sortedChildren = childrenMap.get(parent.id);
reorderedArray.push(...sortedChildren); // 添加排序后的子项
}
});
return reorderedArray;
}
// 原始数据
const rawData = [
{ 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 result = reorderArrayByParentAndPriority(rawData);
console.log(result);
/*
期望输出：
[
{ 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 }
]
*/代码解析与注意事项
- 数据预处理与健壮性： 在forEach循环中，我们添加了对display_priority的类型检查。如果display_priority不存在或不是数字，我们将其视为Infinity。这确保了排序的健壮性，防止因数据不规范而导致程序崩溃，并将这些项推到排序结果的末尾。
- Map的优势： 使用Map (childrenMap) 来存储子项，可以实现 O(1) 的平均时间复杂度来查找特定父项的所有子项，这比每次遍历数组查找要高效得多，尤其是在数据量较大时。
- 分步排序的清晰性： 将分类、排序和重构三个逻辑步骤分开处理，使得代码逻辑更加清晰，易于理解和维护。
- push与spread操作符： reorderedArray.push(parent)用于添加单个父项，而reorderedArray.push(...sortedChildren)则利用展开运算符（spread operator）将一个数组的所有元素一次性添加到另一个数组中，这比循环push更简洁高效。
-
性能考虑：
- 时间复杂度： 初始遍历分类的时间复杂度是 O(N)。排序顶层父项和所有子项列表的总时间复杂度取决于子项的数量和分布，最坏情况下（所有元素都是顶层父项或所有子项都在一个父项下）接近 O(N log N)。最后重构数组的时间复杂度是 O(N)。因此，整体时间复杂度为 O(N log N)，对于大多数应用场景来说是高效的。
- 空间复杂度： parents数组、childrenMap以及最终的reorderedArray都需要额外的空间，空间复杂度为 O(N)。
总结
通过本教程，我们学习了如何处理一个常见的复杂数组重排序问题，即同时考虑父子关系和显示优先级。关键在于将问题分解为几个可管理的步骤：首先进行数据索引和分类，然后对各个层级的数据独立进行优先级排序，最后将这些排序好的数据结构化地组合起来。这种分步处理的方法不仅使代码逻辑清晰，而且在处理大规模数据时也能保持较好的性能。这种策略可以推广到更复杂的树形结构排序场景，只需递归地应用类似的分层排序思想。
