Сортировать массив, размещая дочерние элементы под родительскими

Я сомневаюсь, что вы, ребята, все еще ищете реальный ответ на этот вопрос, но это может помочь другим с той же проблемой. Ниже приведена рекурсивная функция для создания массива, помещающего дочерние элементы под родительские.

$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» и «родительские» поля. Элементы верхнего уровня должны иметь parent_id (как бы вы его ни назвали) равным 0.

Моя более короткая версия ответа Маттванга:

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

Единственное фактическое отличие состоит в том, что он сортирует массив объектов, а не массив массивов.

Вы можете использовать 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 — нет.

Просто используйте функцию usort() и сравните два разных элемента ' большой массив' так, как вам нужно. Тогда это становится вопросом о том, «как мне действительно решить, какой элемент находится перед каким элементом?».

Простой 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);

Идея здесь состоит в том, чтобы сначала отсортировать в обратном порядке по идентификатору. Затем создайте новый массив, сначала вставив самые глубокие элементы (без дочерних элементов). Поскольку мы изначально отсортировали массив по обратному идентификатору, это должно означать, что все это перевернуто. После реверсирования массива он должен быть именно таким, как вы хотите. (Конечно, можно вернуть элементы в массив, чтобы избежать обратной операции, но это может быть медленнее...)

И это очень неоптимизировано, так как он перебирает весь массив много-много раз. С небольшой доработкой этого делать не нужно.

Вот альтернативный класс, который более оптимизирован:

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. Сортировать по идентификатору (usort)
2. Построить вложенную структуру массива.
3. Flatten массив в предзаказе.

В силу предварительной сортировки по id каждая группа дочерних элементов должна быть отсортирована правильно.