JavaScript数组复杂排序：实现父子层级与优先级双重排序

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

在前端开发中，我们经常会遇到需要对从后端获取的扁平数据进行复杂排序和结构化展示的场景。一个典型的例子是，数据项之间存在父子层级关系，同时每个数据项还有自己的显示优先级。本教程将以一个具体的案例为例，展示如何根据id、reference_id和display_priority这三个字段，对一个包含商品sku信息的数组进行重排序。

我们的目标是将一个初始的扁平数组：

[
  { 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 的子项
]

重排规则如下：

1. 父子层级关系：如果一个项目的 reference_id 字段不为 null，则它是一个子项，其父项是 id 字段与之匹配的项目。子项必须紧随其父项之后。
2. 优先级排序：
   • 所有顶级父项（reference_id 为 null 的项目）应根据其 display_priority 字段进行升序排序。
   • 每个父项的子项，也应根据其自身的 display_priority 字段进行升序排序，并整体插入到父项之后。

原尝试的局限性分析

在处理这类问题时，开发者可能会尝试使用 Array.prototype.reduce() 方法来迭代构建新数组。例如，原始问题中提供了一个尝试：

立即学习“Java免费学习笔记（深入）”；

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;
}, []);

这种方法存在几个主要局限性：

1. 依赖原始数组顺序：它假设在处理子项时，其父项已经存在于累加器 acc 中，或者在处理父项时，其子项（如果子项在原始数组中排在父项之前）能被正确插入。如果父项在原始数组中位于其子项之后，或子项在父项之前且父项尚未处理，则可能导致子项被错误地放置或直接追加到末尾。
2. 未全面考虑优先级：该方法只关注了父子关系的插入位置，但并未对父项之间以及同一父项下的多个子项之间的 display_priority 进行明确的排序。例如，如果有多个子项属于同一个父项，它们被插入的顺序将取决于它们在原始数组中的顺序，而非 display_priority。
3. 复杂性与可读性：在 reduce 回调中同时处理两种情况（父项和子项）并进行 splice 操作，会使逻辑变得复杂且难以维护。

为了克服这些局限性，我们需要一个更结构化、分阶段处理的策略。

分步实现策略

一个更健壮的方法是首先识别所有父项和子项，构建它们之间的关系，然后根据优先级进行排序，最后将它们组装成最终的有序数组。

AdsGo AI

全自动 AI 广告专家，助您在数分钟内完成广告搭建、优化及扩量

下载

步骤1：数据分类与预处理

首先，我们需要遍历原始数组，将所有项目区分为顶级父项和子项。同时，为了方便查找，我们可以将子项按其 reference_id（即父项的 id）进行分组。

1. 初始化：创建两个数据结构：一个数组用于存储所有顶级父项 (parents)，一个 Map 用于存储子项 (childrenMap)，其中键是父项的 id，值是该父项的所有子项组成的数组。
2. 遍历与分类：遍历原始数据数组。如果一个项目的 reference_id 为 null，则将其添加到 parents 数组中。否则，它是一个子项，将其添加到 childrenMap 中对应父项 id 的数组中。

步骤2：父节点排序

在将所有项目组合起来之前，我们首先需要确保顶级父项之间的顺序是正确的。根据需求，顶级父项应根据它们的 display_priority 字段进行升序排序。

步骤3：构建最终有序数组

这是将所有排序好的父项和子项组合在一起的最后一步。

1. 初始化：创建一个空数组 reorderedArray，用于存放最终的排序结果。
2. 遍历排序后的父项：按照步骤2中排序好的 parents 数组进行遍历。
3. 插入父项及其子项：对于每个父项：
   • 首先，将该父项添加到 reorderedArray 中。
   • 然后，检查 childrenMap 是否包含该父项的子项。
   • 如果存在子项，获取这些子项，并根据它们的 display_priority 字段进行升序排序。
   • 最后，将排序后的子项逐一添加到 reorderedArray 中，紧随其父项之后。

完整代码示例

/**
 * 根据 reference_id 和 display_priority 重排数组。
 *
 * @param {Array