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

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

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

我们期望的输出结果应遵循以下规则：

1. 如果一个元素的reference_id为null，它是一个顶层父项。
2. 如果一个元素的reference_id不为null，它是一个子项，其父项的id与reference_id匹配。
3. 子项必须紧随其父项之后。
4. 所有顶层父项之间，以及同一父项下的所有子项之间，都应根据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排序。

核心挑战分析

要实现这种复杂的重排序，我们面临以下几个主要挑战：

1. 父子关系的建立与维护： 需要高效地识别每个元素的父项或子项，并能够快速地找到特定父项的所有子项。
2. 多维度排序： 既要考虑父子层级，又要考虑display_priority。简单的sort函数无法一次性解决。
3. 动态插入： 在构建最终数组时，需要将子项动态插入到其父项之后，而不是简单地追加。

原始尝试的reduce方法虽然试图解决父子插入问题，但它存在局限性：它依赖于父项在数组中出现的顺序，如果父项在子项之后，则可能无法正确插入。更重要的是，它没有完全处理display_priority的排序逻辑。

分步解决方案

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

酷兔AI论文

专业原创高质量、低查重，免费论文大纲，在线AI生成原创论文，AI辅助生成论文的神器！

下载

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

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

1. 创建父项映射： 使用一个Map来存储所有父项（reference_id为null）的id到其完整对象的映射，以及一个列表来存储顶层父项。
2. 创建子项映射： 使用另一个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进行排序。

1. 排序顶层父项： 对parents数组进行display_priority升序排序。
2. 排序子项列表： 遍历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