按层次结构和名称对具有层次结构的对象数组进行排序

Question

我有一个嵌套对象数组：

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

我需要对它们进行排序，因为同一级别的节点将按字母顺序排序（asc/desc 可配置）并且所有子节点都应在其父节点之后且在其父节点的兄弟节点之前也按以下顺序排序按字母顺序排列。

例如，如果按asc排序，输出应该是

[ 
    { _id: 4, parent: 0, name: 'A' },
    { _id: 5, parent: 4, name: 'M' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 3, parent: 1, name: 'Z' } 
]

在输出中，4 在 1 之前，因为 A < Z。5 和 6 按字母顺序排序在 4 之下和 1 之前。8 和 7 在 2 之下和 3 之前的情况类似。

如果 desc，输出应该是：

[ 
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 3, parent: 1, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 4, parent: 0, name: 'A' },
    { _id: 5, parent: 4, name: 'M' },
    { _id: 6, parent: 4, name: 'N' } 
]

我尝试实现如下功能。

function sortByHierarchyAndName(arr, sort) {
    var i = 0; 
        j = 0;
        t = 0; 
        parentFound = false; 
        x = arr.length;
        arr2 = []; 

    //Sort by parent asc first 
    arr = arr.sort(function(a, b) {
        if(a.parent < b.parent) return -1; 
        if(a.parent > b.parent) return 1; 
        return 0; 
    }); 
    
    for(; i < x; i += 1) {
        t = arr2.length;
        if(t === 0)  arr2.push(arr[i]);
        else if(arr[i].parent === 0) {
            for(j = 0; j < t; j += 1) {
                if(sort === -1) {
                    if(arr[i].name >= arr2[j].name) arr2.splice(j, 0, arr[i]);
                } else {
                    if(arr[i].name <= arr2[j].name) arr2.splice(j, 0, arr[i]);
                }
            }
            if(arr2.length === t) arr2.push(arr[i]);
        }
        else {
            parentFound = false;
            for(j = 0; j < t; j += 1) {
                if(arr[i].parent === arr2[j]._id) {
                    if(j === t - 1) {
                        arr2.push(arr[i]); 
                    }
                    parentFound = true; 
                } else if(arr[i].parent === arr2[j].parent) {
                    if(sort === -1) {
                        if(j === t - 1) arr2.push(arr[i]); 
                        else if(arr[i].name >= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t; 
                        }
                    } else {
                        if(j === t - 1) arr2.push(arr[i]); 
                        else if(arr[i].name <= arr2[j].name) {
                            arr2.splice(j, 0, arr[i]);
                            j = t; 
                        }
                    }
                } else if(arr[i].parent > arr2[j].parent && parentFound) {
                    arr2.splice(j, 0, arr[i]);
                    j = t; 
                }
            }
        }
    }
    return arr2; 
}

假设 array.sort() 在按父 asc 对长度为 n 的数组进行排序时花费 f(n) 时间量，我正在对实现进行一些性能分析，如下所示.

Best case: f(n) + x * n + y * sum(1 to n/2)*n

Worst case: f(n) + x * n + y * sum(1 to n)*n;

x - factor in processing any given element in arr.

y - factor in processing any given element in arr against any element in arr2.

如您所见，在这两种情况下，执行的持续时间都会随着 n 的增长而呈指数增长，所以我想知道我是否可以做些什么来改善这一点。

Answer 1

你可以使用递归算法和哈希对象，我相信这个算法的性能大约需要 O(n log n):

    function hierarchySortFunc(a,b ) {
      return a.name > b.name;
    }
    
    function hierarhySort(hashArr, key, result) {
    
      if (hashArr[key] == undefined) return;
      var arr = hashArr[key].sort(hierarchySortFunc);
      for (var i=0; i<arr.length; i++) {
        result.push(arr[i]);
        hierarhySort(hashArr, arr[i]._id, result);
      }
    
      return result;
    }
    
    var arr = [ 
        { _id: 4, parent: 0, name: 'A' },
        { _id: 5, parent: 4, name: 'M' },
        { _id: 6, parent: 4, name: 'N' },
        { _id: 1, parent: 0, name: 'Z' },
        { _id: 2, parent: 1, name: 'H' },
        { _id: 8, parent: 2, name: 'G' },
        { _id: 7, parent: 2, name: 'L' },
        { _id: 3, parent: 1, name: 'Z' } 
    ]
    
    var hashArr = {};
    
    for (var i=0; i<arr.length; i++) {
      if (hashArr[arr[i].parent] == undefined) hashArr[arr[i].parent] = [];
      hashArr[arr[i].parent].push(arr[i]);
    }
    
    var result = hierarhySort(hashArr, 0, []);
    
    for (var i=0; i<result.length; i++) console.log(result[i]);

结果：

{_id: 4, parent: 0, name: "A"}
{_id: 5, parent: 4, name: "M"}
{_id: 6, parent: 4, name: "N"}
{_id: 1, parent: 0, name: "Z"}
{_id: 2, parent: 1, name: "H"}
{_id: 8, parent: 2, name: "G"}
{_id: 7, parent: 2, name: "L"}
{_id: 3, parent: 1, name: "Z"}

如果要更改排序顺序，请更改heirarchySortFunc():

function hierarchySortFunc(a,b ) {
  return a.name < b.name;
}

Answer 2

仅组合项目名称并按字母顺序排序可能更简单。

        var array = [
            {_id:1, parent:0, name:'Z'},
            {_id:4, parent:0, name:'A'},
            {_id:2, parent:1, name:'H'},    
            {_id:8, parent:2, name:'G'},        
            {_id:5, parent:4, name:'M'},
            {_id:6, parent:4, name:'N'},
            {_id:3, parent:1, name:'Z'},
            {_id:7, parent:2, name:'L'}
        ]
        
        var getItemFromID = function(id) {
          return array.filter(function(item){
            return item._id === id;
          })[0]
        }
        
        var getCombinedName = function(item) {
          var parent = getItemFromID(item.parent);
          if (parent) {
            return getCombinedName(parent) + item.name;
          } else {
            return item.name;
          }
        }
        
        array.forEach(function(item){
          item.combinedName = getCombinedName(item);
        })
        
        var sortedArray = array.sort(function(a,b) {
          return a.combinedName > b.combinedName;
        });

结果：

{_id: 4, parent: 0, name: "A", combinedName: "A"}
{_id: 5, parent: 4, name: "M", combinedName: "AM"}
{_id: 6, parent: 4, name: "N", combinedName: "AN"}
{_id: 1, parent: 0, name: "Z", combinedName: "Z"}
{_id: 2, parent: 1, name: "H", combinedName: "ZH"}
{_id: 8, parent: 2, name: "G", combinedName: "ZHG"}
{_id: 7, parent: 2, name: "L", combinedName: "ZHL"}
{_id: 3, parent: 1, name: "Z", combinedName: "ZZ"}

按层次结构和名称对具有层次结构的对象数组进行排序

Sort array of objects with hierarchy by hierarchy and name

javascript

arrays

sorting

algorithm

quicksort