按特定值嵌套对象数组排序 Javascript

Question

我正在做排序算法练习，但卡住了。我有一个对象数组，其中可能包含嵌套在其上的第一个嵌套对象。

我需要对包含一个或多个节点的所有“元素”数组进行排序，其中“val”属性 === targetValue 被移到数组的前面。

我需要创建一个 sortObject(object, targetValue) 函数来执行此操作。

例如：

const object = {
  val: 1,
  elements: [
    {
      val: 2,
      children: [
        {
          val: 7,
          elements: [
            {val: 2},
            {val: 18},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 4,
      elements: [
        {val: 5},
        {
          val: 6,
          elements: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      elements: [
        {val: 15}
      ]
    },
    {
      val: 17,
      elements: [
        {val: 16},
        {
          val: 2,
          elements: [
            {val: 14},
            {val: 11},
            {
              val: 18,
              elements: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 27},
            {val: 18},
            {val: 29},
          ]
        }
      ]
    }
  ]
};

如果我调用 sortObject(object, 18)，这将变成（具有下面提到的更改）

sortedObject = {
  val: 1,
  elements: [
    {
      val: 2,
      elements: [
        {
          val: 7,
          elements: [
            {val: 18}, // <-- this moved up
            {val: 2},
            {val: 12}
          ]
        }
      ]
    },
    {
      val: 17, // <-- this moved up
      elements: [
        {
          val: 2, // <-- this moved up
          elements: [
            {
              val: 18, // <-- this moved up
              elements: [
                {val: 4},
                {val: 11},
                {val: 7}
              ]
            },
            {val: 18}, // <-- this moved up
            {val: 14},
            {val: 11},
            {val: 27},
            {val: 29},
          ]
        },
        {val: 16}
      ]
    },
    {
      val: 4,
      elements: [
        {val: 5},
        {
          val: 6,
          elements: [
            {val: 12},
            {val: 11},
            {val: 10},
            {val: 9},
          ]
        },
        {val: 13}
      ]
    },
    {
      val: 3,
      elements: [
        {val: 15}
      ]
    }
  ]
};

我开始为它创建一个排序算法，但我无法通过第一个“元素”递归..并意识到我尝试这样做的方式永远行不通（我正在创建一个新数组，使用 targetValue 获取子对象的索引，并推送到一个新数组..但这不适用于递归）我被困住了有人可以帮忙吗？

Answer 1

您可以使用 breadth-first search 并查找所需的值并在找到该值时存储该对象。如果集合包含对象，则按布尔值对数组进行排序。

const
    sortObject = (object, value) => {
        const
            hasValue = new Set,
            sort = object => {
                let found = object.val === value;
                if (object.elements) {
                    object.elements.forEach(o => found = sort(o) || found);
                    object.elements.sort((a, b) => hasValue.has(b) - hasValue.has(a));
                }
                if (found) hasValue.add(object);
                return found;
            };

        sort(object);
        return object;
    },
    object = { val: 1, elements: [{ val: 2, elements: [{ val: 7, elements: [{ val: 2 }, { val: 18 }, { val: 12 }] }] }, { val: 4, elements: [{ val: 5 }, { val: 6, elements: [{ val: 12 }, { val: 11 }, { val: 10 }, { val: 9 }] }, { val: 13 }] }, { val: 3, elements: [{ val: 15 }] }, { val: 17, elements: [{ val: 16 }, { val: 2, elements: [{ val: 14 }, { val: 11 }, { val: 18, elements: [{ val: 4 }, { val: 11 }, { val: 7 }] }, { val: 27 }, { val: 18 }, { val: 29 }] }] }] };

console.log(sortObject(object, 18));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

如果排序顺序是由 18 的出现深度定义的，那么它出现的深度越小，它就应该在数组中出现得越早，那么我会建议一种桶排序，其中出现在相同深度的 18 个元素将被放置在同一个桶中。然后将桶连接起来成为排序的 elements 数组：

function sortObject(obj, target) {
    const partition = {};
    let minDepth = 10000; // depth of object should not exceed this limit
    if (obj.elements?.length) {
        for (const child of obj.elements) {
            const depth = sortObject(child, target);
            (partition[depth] ??= []).push(child);
            minDepth = Math.min(minDepth, depth);
        }
        obj.elements = Object.values(partition).flat();
    }
    return obj.val === target ? 0 : minDepth + (minDepth < 10000);
}

const object = {val: 1,elements: [{val: 2,elements: [{val: 7,elements: [{val: 2},{val: 18},{val: 12}]}]},{val: 4,elements: [{val: 5},{val: 6,elements: [{val: 12},{val: 11},{val: 10},{val: 9},]},{val: 13}]},{val: 3,elements: [{val: 15}]},{val: 17,elements: [{val: 16},{val: 2,elements: [{val: 14},{val: 11},{val: 18,elements: [{val: 4},{val: 11},{val: 7}]},{val: 27},{val: 18},{val: 29},]}]}]};
sortObject(object, 18);
console.log(object);

按特定值嵌套对象数组排序 Javascript

Sort by specific value nested array of objects Javascript

javascript

node.js

arrays

tree

nested-object