排序一個數組，將子女放在父母的下方

Question

所以我有一個PHP的項目數組，有些可能通過parent_id鍵鏈接到其他人。我正在尋找排序這個數組，以便任何父項在這個數組中的項目最終定位在父項的下方。

例如：（實際陣列具有更多的鍵）

some_array[0]['id'] = 15001; 
some_array[0]['parent_id'] = 14899; 

some_array[1]['id'] = 14723; 
some_array[1]['parent_id'] = 0; //parent_id of 0 means item has no parent of its own 

some_array[2]['id'] = 14899; 
some_array[2]['parent_id'] = 0; 

some_array[3]['id'] = 15000; 
some_array[3][parent_id'] = 14723; 

我希望讓他們在這個順序最終排序這些：

some_array[0]['id'] = 14723; 

some_array[1]['id'] = 15000; 

some_array[2]['id'] = 14899; 

some_array[3]['id'] = 15001; 

即。物品就在他們的父母下面。

在此先感謝！

Answer 1

只需使用usort()函數，並以您需要的方式比較'大陣列'中的兩個不同元素。這成爲一個關於「」的問題，我該如何真正決定哪個元素在哪個元素之前？'。

Answer 2

可以使用usort由用戶定義函數來進行排序：

function cmp($a, $b) 
{ 
    if ($a['id'] == $b['id']) { 
    return 0; 

    } else if ($a['parent_id']) { 
    if ($a['parent_id'] == $b['parent_id']) { 
     return ($a['id'] < $b['id'] ? -1 : 1); 
    } else { 
     return ($a['parent_id'] >= $b['id'] ? 1 : -1); 
    } 
    } else if ($b['parent_id']) { 
    return ($b['parent_id'] >= $a['id'] ? -1 : 1); 
    } else { 
    return ($a['id'] < $b['id'] ? -1 : 1); 
    } 
} 

usort($some_array, "cmp"); 

注：這隻會有樹是一個深層次（指無子女的兒童）工作。對於更復雜的樹，您可能想要將數據分類到圖中，然後將其平坦化。

編輯：固定爲編輯在那裏$b有父，但$a沒有的情況下。

Answer 3

如果你想支持多層兒童，簡單的usort將不起作用。沒有其他信息，根本無法知道兩個任意元素如何比較。

我沒有想太多，所以也許它不起作用。但是，這裏有一個排序類：

class TopSort 
{ 
    private $sorted, $unsorted; 
    private $history; 

    public function sort(array $unsorted) 
    { 
    $this->sorted = array(); 
    $this->unsorted = $unsorted; 
    $this->history = array(); 

    usort($this->unsorted, function($a, $b) 
    { 
     return $b['id'] - $a['id']; 
    }); 

    foreach ($this->unsorted as $i => $a) 
     if ($a['parent_id'] == 0) $this->visit($i); 

    return array_reverse($this->sorted); 
    } 

    private function visit($i) 
    { 
    if (!array_key_exists($i, $this->history)) 
    { 
     $this->history[$i] = true; 
     foreach ($this->unsorted as $j => $a) 
     if ($a['parent_id'] == $this->unsorted[$i]['id']) $this->visit($j); 

     $this->sorted[] = $this->unsorted[$i]; 
    } 
    } 
} 

$sorter = new TopSort(); 
$some_array = $sorter->sort($some_array); 

這裏的想法是首先按id逆向排序。然後通過首先插入最深的元素（那些沒有孩子的元素）來建立一個新的數組。由於我們最初通過反向ID對數組進行排序，因此它應該意味着整個事物是顛倒的。反轉陣列後，它應該完全像你想要的。 （當然，可以將項目移到陣列上以避免反向操作，但這可能會更慢......）

而且這是非常優化因爲它遍歷整個陣列很多次而未優化。稍加修改就不需要那麼做。

下面是一個替代的類更優化：

class TopSort 
{ 
    private $sorted; 

    public function sort(array $nodes) 
    { 
    $this->sorted = array(); 

    # sort by id 
    usort($nodes, function($a, $b) { 
     return $a['id'] - $b['id']; 
    }); 

    # build tree 
    $p = array(0 => array()); 
    foreach($nodes as $n) 
    { 
     $pid = $n['parent_id']; 
     $id = $n['id']; 

     if (!isset($p[$pid])) 
     $p[$pid] = array('child' => array()); 

     if (isset($p[$id])) 
     $child = &$p[$id]['child']; 
     else 
     $child = array(); 

      $p[$id] = $n; 
     $p[$id]['child'] = &$child; 
     unset($child); 

     $p[$pid]['child'][] = &$p[$id];  
    } 
    $nodes = $p['0']['child']; 
    unset($p); 

    # flatten array 
    foreach ($nodes as $node) 
     $this->flatten($node); 

    return $this->sorted; 
    } 

    private function flatten(array $node) 
    { 
    $children = $node['child']; 
    unset($node['child']); 
    $this->sorted[] = $node; 
    foreach ($children as $node) 
     $this->flatten($node); 
    } 
} 

$sorter = new TopSort(); 
$sorted = $sorter->sort($some_array); 

這是一個三步法：

1. 分類ID（usort）
2. 生成嵌套陣列結構。
3. 按預訂順序排列數組。

由於按ID預先排序，每組孩子都應該正確排序。

Answer 4

我懷疑你們是否仍然在尋找真正的答案，但它可能會幫助其他人解決同樣的問題。下面是一個遞歸函數，可以將一個數組放在父母的下方。

$initial = array(
    array(
     'name' => 'People', 
     'ID' => 2, 
     'parent' => 0 
     ), 
    array(
     'name' => 'Paul', 
     'ID' => 4, 
     'parent' => 2 
     ), 
    array(
     'name' => 'Liz', 
     'ID' => 5, 
     'parent' => 2 
     ), 
    array(
     'name' => 'Comus', 
     'ID' => 6, 
     'parent' => 3 
     ), 
    array(
     'name' => 'Mai', 
     'ID' => 7, 
     'parent' => 2 
     ), 
    array(
     'name' => 'Titus', 
     'ID' => 8, 
     'parent' => 3 
     ), 
    array(
     'name' => 'Adult', 
     'ID' => 9, 
     'parent' => 6 
     ), 
    array(
     'name' => 'Puppy', 
     'ID' => 10, 
     'parent' => 8 
     ), 
    array(
     'name' => 'Programmers', 
     'ID' => 11, 
     'parent' => 4 
     ) , 
    array(
     'name' => 'Animals', 
     'ID' => 3, 
     'parent' => 0 
     )       
    ); 


/*--------------------------------- 
function parentChildSort_r 
$idField  = The item's ID identifier (required) 
$parentField = The item's parent identifier (required) 
$els   = The array (required) 
$parentID  = The parent ID for which to sort (internal) 
$result  = The result set (internal) 
$depth   = The depth (internal) 
----------------------------------*/ 

function parentChildSort_r($idField, $parentField, $els, $parentID = 0, &$result = array(), &$depth = 0){ 
    foreach ($els as $key => $value): 
     if ($value[$parentField] == $parentID){ 
      $value['depth'] = $depth; 
      array_push($result, $value); 
      unset($els[$key]); 
      $oldParent = $parentID; 
      $parentID = $value[$idField]; 
      $depth++; 
      parentChildSort_r($idField,$parentField, $els, $parentID, $result, $depth); 
      $parentID = $oldParent; 
      $depth--; 
     } 
    endforeach; 
    return $result; 
} 

$result = parentChildSort_r('ID','parent',$initial); 

print '<pre>'; 
print_r($result); 
print '</pre>'; 

這是一個放鬆下來的方法，可以消除原來的數組元素，並將它們放入結果以適當的順序設置。我對它有點泛泛，所以它只是需要你告訴它你的'ID'字段和'父'字段被調用。頂級的項目都要求有0

Answer 5

一個PARENT_ID（但你的名字），我的短版mattwang的回答：

/** 
* sort parents before children 
* 
* @param array $objects input objects with attributes 'id' and 'parent' 
* @param array $result (optional, reference) internal 
* @param integer $parent (optional) internal 
* @param integer $depth (optional) internal 
* @return array   output 
*/ 
function parent_sort(array $objects, array &$result=array(), $parent=0, $depth=0) { 
    foreach ($objects as $key => $object) { 
     if ($object->parent == $parent) { 
      $object->depth = $depth; 
      array_push($result, $object); 
      unset($objects[$key]); 
      parent_sort($objects, $result, $object->id, $depth + 1); 
     } 
    } 
    return $result; 
} 

只有實際的區別在於，它按照對象的數組，而不是一個數組數組。