logo标签列表

基于父子关系对数组值进行排序

phparrayssorting
13

我正在尝试对数组进行排序，以确保任何项的父项始终出现在它之前。例如：

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的父母已经存在：
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个级别。

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

请更清楚地解释您的问题。在每个数组的索引0和2中，整数值所指代的内容不清楚，因为它们太大了，无法指向任何现有的索引。 - Sayed
索引0是每个员工的ID，索引2是该员工的经理的ID，这是经理ID的查找。因此，在上面的示例中，John的ID为199714，他的经理是207306，即Bob，因为Bob的ID是207306（索引0）。 - bhttoan
我正在考虑将此问题投票关闭，因为这更像是一个编码挑战而不是一个真正的问题。你没有发布任何个人尝试解决问题的方法，只是简单地发布了一些数据和一个链接指向已经给出的实际有效的解决方案。根据 Stack Overflow 的严格标准，这不是一个好问题。在提出下一个问题之前，请考虑重新阅读 http://stackoverflow.com/help/how-to-ask。 - maxhb
1
这种存储关系的特定方式被称为邻接表，并且有明确定义的遍历方法。 - bishop
6个回答
5

这将轻松地对数组进行排序（在 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;
        }
    }
}

Live demo: https://3v4l.org/Uk6Gs

我在$sorted[]=$next这一行遇到了内存不足的错误。 - bhttoan
@bhttoan 抱歉，我在测试数据时使用了错误的索引。将2替换为0；现在可以工作吗？ - bwoebi
@bhttoan 包含了一个实时演示（https://3v4l.org/Uk6Gs），以确保它能正常工作 :-/ 对于一开始给您的有点错误的代码，我很抱歉。 - bwoebi
是的，这似乎工作得很好 - 我遇到了一种边缘情况，即有几个条目的父项根本不在数组中，并且它们被完全排除在外，因此我需要尝试理解一下。 - bhttoan
@bhttoan 嗯，这在问题中没有指定（即问题表明 '' 是根）- 那么您需要一个包含子数组的映射，检查是否有任何节点没有父节点，并用它来初始化数组；也就是说，不是 $sorted = $parents['']; 而是 $sorted = $children = []; foreach ($array as $val) { $children[$val[0]] = $val; } foreach ($array as $val) { if (!isset($children[$val[2]])) { $sorted[] = $val; } }。 - bwoebi
显示剩余5条评论
2
我有两个不同的版本供您选择。
a) 使用“遍历树”方法，采用递归和引用来最小化内存消耗。
$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

$list = [];
generateList($data, '', $list);

var_dump($list);

function generateList($data, $id, &$list) {
    foreach($data as $d) {
        if($d[2] == $id) {          
            $list[] = $d; // Child found, add it to list            
            generateList($data, $d[0], $list); // Now search for childs of this child
        }
    }
}
b) 使用 PHP 内置的 usort() 函数（在 PHP 5.x 版本中运行良好，但在 PHP 7+ 版本中不可用） 
$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

usort($data, 'cmp');

var_dump($data);

function cmp($a, $b) {  
    if($a[2] == '' || $a[0] == $b[2]) return -1; //$a is root element or $b is child of $a
    if($b[2] == '' || $b[0] == $a[2]) return 1; //$b is root element or $a is child of $b
    return 0; // both elements have no direct relation
}
1
尝试使用PHP 7运行usort()示例，它将不会给出预期的结果[由于算法更改]。usort()仅适用于完全排序（即每个元素都与彼此具有明确定义的关系，显示明确定义的顺序）。让我们取$a、$b和$c；然后如果$a == $b并且$b == $c，则假定$a == $c。您的代码在PHP 5中对此输入有效，但对于不同的输入，在PHP 5上也会失败。 - bwoebi
感谢您的反馈。您能提供一个输入数据的例子，其中 usort() 方法无法正常工作（使用 php5）吗？ - maxhb
感谢您的反馈，我们没有意识到 usort() 函数从 PHP5 到 PHP7 的行为发生了变化。 - maxhb
1

我检查了这个在PHP 5.6和PHP 7中可用

示例数组：

$array = 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,
    ),
); 



echo "<pre>";
$emp = array();

//form the array with parent and child
foreach ($array as $val) {
    $manager = ($val[2] == '') ? 0 : $val[2];
    $exist = array_search_key($val[2], $emp);
    if ($exist)
        $emp[$exist[0]][$val[0]] = $val;
    else
    //print_R(array_search_key(199714,$emp));
        $emp[$manager][$val[0]] = $val;
}

$u_emp = $emp[0];
unset($emp[0]);

//associate the correct child/emp after the manager
foreach ($emp as $k => $val) {
    $exist = array_search_key($k, $u_emp);
    $pos = array_search($k, array_keys($u_emp));

    $u_emp = array_slice($u_emp, 0, $pos+1, true) +
            $val +
            array_slice($u_emp, $pos-1, count($u_emp) - 1, true);

}
print_R($u_emp); //print the final result

// key search function from the array
function array_search_key($needle_key, $array, $parent = array())
{
    foreach ($array AS $key => $value) {
        $parent = array();
        if ($key == $needle_key)
            return $parent;
        if (is_array($value)) {
            array_push($parent, $key);
            if (($result = array_search_key($needle_key, $value, $parent)) !== false)
                return $parent;
        }
    }
    return false;
}
1

以下代码可能有所帮助。因此，您的输出存储在$sortedarray中。

$a=array(array(207306,'Bob',''),
array (199730,'Sam',199714),
array(199728,'Simon',207306),
array(199714,'John',207306),
array(199716,'Tom',199718),
array(199718,'Phillip',207306),
array(199720,'James',207306));

$sortedarray=$a;
foreach($a as $key=>$value){
    $checkvalue=$value[2];
    $checkkey=$key;
foreach($a as $key2=>$value2){
    if($key<$key2){
            if ($value2[0]===$checkvalue){
                $sortedarray[$key]=$value2;
                $sortedarray[$key2]=$value;
        }else{
            }
    }
  }
 }

 print_r($sortedarray);
0

这种方法怎么样：

创建一个空数组result。

循环遍历数组，并仅取出其中[2]为空的项目并将其插入result中。

当此循环完成后，您使用一个foreach-Loop嵌套在一个while-loop中。使用foreach-Loop从您的数组中取出每个已经是result一部分的[2]项目，只要您的数组包含任何内容，就这样做。

$result = array();
$result[''] = 'root';

while(!empty($yourArray)){
  foreach($yourArray as $i=>$value){
    if(isset($result[$value[2]])){
      // use the next line only to show old order
      $value['oldIndex'] = $i;
      $result[$value[0]] = $value;
      unset($yourArray[$i]);
    }
  }
}

unset($result['']);

提示：在遍历数组时删除其中的部分可能会导致问题。如果您这样做了...请尝试解决这个问题 :)

另外，如果您的数组存在未解决的循环或没有父级的子项，请考虑设置中断条件。

0

你可以使用变量$arr中的数组，并使用以下代码，它将为您提供所需的输出。

function check($a, $b) {   
    return ($a[0] == $b[2]) ? -1 : 1;
}


uasort($arr, 'check');
echo '<pre>';
print_r(array_values($arr));
echo '</pre>';
与maxhb的答案相同的问题：https://dev59.com/p1kT5IYBdhLWcg3wELcl#W8_nnYgBc1ULPQZF7M3O - bwoebi
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接