高效重排数组：基于父子关系与显示优先级的复杂排序策略

本文旨在提供一个全面的教程，详细讲解如何根据元素的父子关系（id与reference_id）和显示优先级（display_priority）对复杂数组进行重排序。我们将通过构建数据索引、组织父子关系、分步应用排序规则，最终生成一个结构清晰、符合预期的有序数组。

引言：理解复杂数组重排序需求

在前端或后端开发中，我们经常会遇到需要对数据列表进行复杂排序的场景。其中一种常见的需求是，数据项之间存在层级关系（例如，父子关系），同时每个数据项还有自身的显示优先级。我们的目标是将子项紧随其父项之后显示，并且在同级（包括顶层父项和同一父项下的子项）之间，需要根据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的排序逻辑。

分步解决方案

为了克服上述挑战，我们将采用一个结构化的分步方法：

步骤一：构建数据索引与分类

首先，我们需要对原始数据进行预处理，以便快速查找元素及其子项，并将所有元素分为顶层父项和子项。

创建父项映射： 使用一个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