php - 根据父/子关系对数组值进行排序

Question

我正在尝试对数组进行排序，以确保数组中任何项目的父项始终存在于它之前。例如:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [2] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )

    [3] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )

    [4] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [5] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

在上面的数组中，这个“失败”是因为 [1][2] (Sam) 还不存在，[4][2] (Tom) 也不存在。

在这种情况下，正确的输出应该是，因为 Sam 和 Tom 的 parent 在他们出现在数组中之前就已经存在:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )


    [2] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [3] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )


    [4] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )


    [5] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

我找到了答案 https://stackoverflow.com/a/12961400/1278201这非常接近，但它似乎只深入一层(即只有一个父级)，而在我的情况下，层次结构中可能有 1 或 10 层深。

如何对数组进行排序，以便除非其父项之前已经存在，否则不会出现任何值？

Answer 1

这将对数组进行简单的排序(在 O(n) 中)首先放置所有没有父元素的元素，然后是其父元素已经在数组中的元素，迭代地，直到没有子元素将当前元素作为父元素。

# map the children by parent
$parents = ['' => []];
foreach ($array as $val) {
    $parents[$val[2]][] = $val;
}
# start with those with no parent
$sorted = $parents[''];
# add the children the current nodes are parent of until the array is empty
foreach ($sorted as &$val) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

此代码需要 PHP 7，在某些情况下它可能无法在 PHP 5 下工作。 - 为了 PHP 5 兼容性，您必须交换 foreach ($sorted as &$val)与 for ($val = reset($sorted); $val; $val = next($sorted)) :

# a bit slower loop which works in all versions
for ($val = reset($sorted); $val; $val = next($sorted)) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

现场演示:https://3v4l.org/Uk6Gs