如何按元素嵌套层级对数组排序并实现多级字母序排列？

我有一个数据数组，需要实现按父子嵌套层级排序，同时顶层元素和所有嵌套子元素都按字母顺序排列。但当前写的方法只处理了一级子元素，深层嵌套的元素没被正确处理。

初始数据 #

const arr = [
  {
    id: 0,
    name: 'A',
    parentId: null,
  },
  {
    id: 78,
    name: 'B',
    parentId: 77,
  },
  {
    id: 1715,
    name: 'C',
    parentId: 78,
  },
  {
    id: 77,
    name: 'D',
    parentId: null,
  },
  {
    id: 1716,
    name: 'E',
    parentId: 1715,
  },
  {
    id: 76,
    name: 'F',
    parentId: null,
  },
];

现有无效代码 #

这个方法只获取了顶层元素的直接子元素，没有递归处理深层嵌套，导致部分元素丢失：

function sortData() {
  const result = [];

  arr.sort((a, b) => {
    return a.name.localeCompare(b.name);
  });

  for (const element of arr) {
    if (!element.parentId) {
      const children = folders.filter((el) => el.parentId === element.id);

      result.push(element, ...children);
    }
  }

  return result;
}

期望结果 #

const arr = [
  {
    id: 0,
    name: 'A',
    parentId: null,
  },
  {
    id: 77,
    name: 'D',
    parentId: null,
  },
  {
    id: 78,
    name: 'B',
    parentId: 77,
  },
  {
    id: 1715,
    name: 'C',
    parentId: 78,
  },
  {
    id: 1716,
    name: 'E',
    parentId: 1715,
  },
  {
    id: 76,
    name: 'F',
    parentId: null,
  },
];

现有方法输出结果 #

const arr = [
  {
    id: 0,
    name: 'A',
    parentId: null,
  },
  {
    id: 77,
    name: 'D',
    parentId: null,
  },
  {
    id: 78,
    name: 'B',
    parentId: 77,
  },
  {
    id: 76,
    name: 'F',
    parentId: null,
  }
];

解决方案 #

要处理深层嵌套，需要通过递归遍历每个元素的子节点，同时保证每一层都按字母排序。实现步骤如下：

1. 先对整个数组按名称排序，确保同层级元素的字母顺序
2. 构建父ID到子元素的映射表，方便快速查找子节点
3. 递归遍历每个元素，先添加当前元素，再递归添加其所有子元素

代码实现 #

function sortData(arr) {
  // 复制原数组并按名称排序，避免修改原数组
  const sortedArr = [...arr].sort((a, b) => a.name.localeCompare(b.name));
  
  // 构建父ID与子元素的映射
  const parentMap = new Map();
  sortedArr.forEach(item => {
    const parentId = item.parentId ?? null;
    if (!parentMap.has(parentId)) {
      parentMap.set(parentId, []);
    }
    parentMap.get(parentId).push(item);
  });
  
  // 递归收集元素：当前元素在前，子元素紧跟其后
  function collectItems(parentId) {
    const items = parentMap.get(parentId) || [];
    const result = [];
    for (const item of items) {
      result.push(item);
      // 递归收集当前元素的所有子元素
      result.push(...collectItems(item.id));
    }
    return result;
  }
  
  // 从顶层元素（parentId为null）开始收集
  return collectItems(null);
}

// 测试调用
const arr = [
  { id: 0, name: 'A', parentId: null },
  { id: 78, name: 'B', parentId: 77 },
  { id: 1715, name: 'C', parentId: 78 },
  { id: 77, name: 'D', parentId: null },
  { id: 1716, name: 'E', parentId: 1715 },
  { id: 76, name: 'F', parentId: null },
];

console.log(sortData(arr));

代码说明 #

• 全局排序：先对整个数组按name排序，确保所有同层级的元素都符合字母顺序要求
• 映射表构建：用Map存储每个父ID对应的子元素数组，避免反复遍历原数组查找子节点，提升效率
• 递归收集：通过递归函数，将每个元素及其所有深层子元素按层级顺序加入结果数组，保证父子层级关系正确

内容的提问来源于stack exchange，提问作者Vladislav