Sắp xếp mảng các đối tượng với hệ thống cấp bậc của hệ thống cấp bậc và tên

Question

Tôi có một mảng các đối tượng lồng nhau:

[ 
    {_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'} 
] 

tôi cần phải sắp xếp chúng theo cách cho các nút ở cùng cấp sẽ được sắp xếp theo thứ tự chữ cái (asc/desc configurable) và tất cả các nút con phải sau cha mẹ của chúng và trước nút anh chị em của bố mẹ chúng cũng được sắp xếp theo thứ tự bảng chữ cái.

Ví dụ, nếu sắp xếp theo asc, sản lượng nên được

[ 
    { _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' } 
] 

Trong đầu ra, 4 là trước ngày 1 vì A < Z. 5 và 6 đều được sắp xếp theo thứ tự abc dưới 4 và trước 1. trường hợp tương tự 8 và 7 dưới 2 và trước 3.

và nếu desc, sản lượng nên là:

[ 
    { _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' } 
] 

tôi đã cố gắng để thực hiện một chức năng như dưới đây.

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; 
} 

Giả sử Array.Sort() lấy f(n) lượng thời gian khi sắp xếp bởi asc cha mẹ cho một mảng có độ dài n, tôi đang làm một số phân tích hiệu suất cho việc thực hiện như dưới đây.

trường hợp xuất sắc nhất: f (n) + x * n + y * sum (1 đến n/2) * n

Trường hợp xấu nhất: f (n) + x * n + y * sum (1 đến n) * n;

x - yếu tố trong việc xử lý bất kỳ phần tử đã cho nào trong arr.

y - yếu tố trong việc xử lý bất kỳ phần tử đã cho nào trong mảng đối với bất kỳ phần tử nào trong arr2.

Như bạn có thể thấy, trong cả hai trường hợp, thời gian thực hiện sẽ tăng theo cấp số nhân khi số n tăng lên, vì vậy tôi tự hỏi liệu tôi có thể làm điều gì đó để cải thiện điều này không.

Answer 1

Bạn có thể sử dụng một thuật toán đệ quy và đối tượng băm, tôi tin rằng hiệu suất của thuật toán này sẽ mất khoảng O (n log n):

<script> 

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]); 

</script> 

Kết quả:

{_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"} 

Nếu bạn muốn để thay đổi thứ tự sắp xếp, vui lòng thay đổi heirarchySortFunc():

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