数组对象根据父子关系与显示优先级进行排序的通用方法-js教程-PHP中文网

数组对象根据父子关系与显示优先级进行排序的通用方法

本文介绍如何对包含父子关系（通过id和reference_id关联）及显示优先级 (display_priority) 的数组对象进行排序。我们将构建一个分层结构，先处理父子归属，再根据优先级对父节点和子节点进行排序，最终展平为符合预期顺序的数组。

问题背景与挑战

在前端或后端数据处理中，我们经常会遇到需要对具有层级关系的数据进行排序的场景。例如，一个产品列表可能包含主产品和其关联的子产品，同时每个产品都有一个显示优先级。我们的目标是根据以下规则对一个扁平化数组进行重排序：

父子关系优先： 具有 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）的递归方式实现：

Robovision AI

一个强大的视觉AI管理平台

查看详情

遍历排序后的顶层节点。
对于每个顶层节点，将其添加到结果数组中。
如果该节点有子节点，则递归地对这些子节点执行相同的操作（先添加子节点本身，再处理其子节点），确保父节点在前，子节点紧随其后。

完整实现代码

下面是使用 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 数组本身进行排序，以确定顶层项的最终顺序。
展平层级结构：
- 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: [] })。这意味着原始对象中的嵌套对象仍然是引用。如果需要修改嵌套对象而不影响原始数据，则需要进行深拷贝。