我有以下数据:

var data = [
    { index : 1, sort : 10, parent : 0 },
    { index : 2, sort : 7, parent : 0 },
    { index : 3, sort : 15, parent : 1 },
    { index : 4, sort : 4, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 6, sort : 20, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 8, sort : 6, parent : 5 },
];

我如何通过父 ID 和排序值对其进行高效排序，以便我最终得到:

var data = [
    { index : 4, sort : 4, parent : 0 },    
    { index : 2, sort : 7, parent : 0 },
    { index : 1, sort : 10, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 8, sort : 6, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 6, sort : 20, parent : 5 },   
    { index : 3, sort : 15, parent : 1 },
];

这是一个树结构。每个元素后面紧跟着任何子元素，同一分支上的所有元素都按排序值排序。

我能想到的最好办法是先按父级排序，然后在每个分支上进行第二次排序。这似乎效率低下。

编辑:示例排序顺序错误。我已经更正了。

编辑以澄清:每个嵌套分支都需要出现在父值的紧下方，而不是分支的末尾。

编辑:进一步修正数据。

最佳答案

这不是您最初的方法，但您可以根据您的数据构建一棵实际的树，如下所示:

function TreeNode(data) {
  this.data     = data;
  this.parent   = null;
  this.children = [];
}
TreeNode.comparer = function (a, b) { 
  return a.data.sort < b.data.sort ? 0 : 1; 
};
TreeNode.prototype.sortRecursive = function () {
  this.children.sort(TreeNode.comparer);
  for (var i=0, l=this.children.length; i<l; i++) {
    this.children[i].sortRecursive();
  }
  return this;
};

function toTree(data) {
  var nodeById = {}, i = 0, l = data.length, node;

  nodeById[0] = new TreeNode(); // that's the root node

  for (i=0; i<l; i++) {  // make TreeNode objects for each item
    nodeById[ data[i].index ] = new TreeNode(data[i]);
  }
  for (i=0; i<l; i++) {  // link all TreeNode objects
    node = nodeById[ data[i].index ];
    node.parent = nodeById[node.data.parent];
    node.parent.children.push(node);
  }
  return nodeById[0].sortRecursive();
}

通过此设置，您可以通过简单的调用将节点整齐地嵌套:

var tree = toTree(data);

TreeNode:0
  parent  -> null
  data    -> undefined
  childen -> Array[
    TreeNode:1
      parent  -> TreeNode:0
      data    -> { index : 4, sort :  4, parent : 0 }
      childen -> Array[]
    TreeNode:2
      parent  -> TreeNode:0
      data    -> { index : 2, sort :  7, parent : 0 }
      childen -> Array[]
    TreeNode:3
      parent  -> TreeNode:0
      data    -> { index : 1, sort : 10, parent : 0 }
      childen -> Array[
        TreeNode:4
          parent  -> TreeNode:3
          data    -> { index : 5, sort : 13, parent : 1 }
          childen -> Array[
          ]
        TreeNode:5
          parent  -> TreeNode:3
          data    -> { index : 3, sort : 15, parent : 1 }
          childen -> Array[
            ... and so on ...
          ]
      ]
  ]

Once you have that tree object, you can do a number of things with it, including traversing it recursively in the expected order.

To do this, you could add a helper function that does depth-first traversal and executes a payload function f for every node:

TreeNode.prototype.walk = function(f, recursive) {
  for (var i=0, l=this.children.length; i<l; i++) {
    var child = this.children[i];
    f.apply(child, Array.prototype.slice.call(arguments, 2));
    if (recursive) child.walk.apply(child, arguments);
  }
}

并这样调用它:

tree.walk(function () { console.log(this.data) }, true);

这会产生:

{ index: 4, sort:  4, parent: 0}
{ index: 2, sort:  7, parent: 0}
{ index: 1, sort: 10, parent: 0}
{ index: 5, sort: 13, parent: 1}
{ index: 8, sort:  6, parent: 5}
{ index: 7, sort:  2, parent: 8}
{ index: 6, sort: 20, parent: 5}
{ index: 3, sort: 15, parent: 1}

使用更复杂的有效负载函数来实现其他效果，例如使用 jQuery 在表中添加表行或将项目添加到 <select>盒子。

关于javascript - 将数据排序成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8241342/